Yineleme için özyineleme dan işlevi dönüştürmek

4 Cevap php

Ben php recursion iyi işlemez beri Cahilce yavaş yazdı bu işlevi var. Ben bir süre döngü dönüştürmek için çalışıyorum, ama bunu nasıl başımı sarma sorun yaşıyorum.

Herkes bana bazı ipuçları verebilir misiniz?

    public function findRoute($curLoc, $distanceSoFar, $expectedValue) {

    $this->locationsVisited[$curLoc] = true;
    $expectedValue += $this->locationsArray[$curLoc]*$distanceSoFar;

    $at_end = true;
    for($i = 1; $i < $this->numLocations; $i++) {
        if($this->locationsVisited[$i] == false) {
            $at_end = false;

            if($expectedValue < $this->bestEV)
                $this->findRoute($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);
        }
    }

    $this->locationsVisited[$curLoc] = false;

    if($at_end) {
        if($expectedValue < $this->bestEV) {
            $this->bestEV = $expectedValue;
        }
    }
}

4 Cevap

Ben kodu dönüştürmek için gitmiyorum, ama bir yığın oluşturarak iteratif bir birine recusive işlev dönüştürebilirsiniz:

$stack= array();

Ve yerine yürütmesini $this->findroute(), bu yığının üzerine parametreleri itin:

$stack[] = array($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);

Şimdi astarlanmalıdır sonra yığın drene bir süre döngü içine işlevi temelde her şeyi kuşatır:

while ($stack) { 
    // Do stuff you already do in your function here

Sen mevcut durumunu saklamak için bir yığın kullanarak tekrarlanan bir fonksiyon içine özyinelemeli işlev dönüştürebilirsiniz. array_push() içine bakmak ve array_pop().

Bir bakışta ben evet PHP yavaş, özyineleme senin sorunun olduğunu sanmıyorum, ama bu senin, daha size gereken daha değerler üzerinden gidiyor, bir yığını, ya da birkaç yığınlarının değerleri koyarak ve bunları işleme gibi görünüyor, güzel olabilir .

özel sıralama işlevleri her zaman bu tür sorunları ile bana yardımcı oldu.

function sort_by_visited($x,$y)
{
   return ($this->locationsVisited[$x] > $this->locationsVisited[$y]) ? -1 : 1;
}

uasort($locationsVisited,'sort_by_visited');

Bu yığının üstündeki tüm ziyaret değil yerleri öncelik verecektir.

Bu senin bir grafik düğümler bir dizi geçişi için en uygun yolu bulmak için çalışıyor gibi görünüyor.

Ben "Gezgin Satıcı" sorun Yapay Zeka bir prototip olduğu gibi Bilgisayar Bilimi okudu ettik olduğunu tahmin ediyorum. Tabii ki, böyle gibi, kendi Wikipedia sayfası vardır:

http://en.wikipedia.org/wiki/Travelling%5Fsalesman%5Fproblem

Üzgünüz - ama sadece bir yinelemeli işlevi bir recursive gelen takas herhangi bir hızlı gitmek yapmak için gitmiyor ("php de özyineleme işlemez." - Eğer bu iddia için referans sağlayabilir). Daha hızlı bir çözüm gerekiyorsa, o zaman non-exhaustive/fuzzy yöntemlere bakmak gerekir.

C.

etiketler