У меня есть эта функция, которую я написал, которая ужасно медленна, поскольку php не справляется с рекурсией. Я пытаюсь преобразовать его в цикл while, но у меня возникают проблемы с тем, чтобы обмануть голову, как это сделать.
Может ли кто-нибудь дать мне несколько советов?
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; } } } Я не собираюсь преобразовывать ваш код, но вы можете преобразовать возвращающую функцию в итеративную, создав стек:
$stack= array();
И вместо того, чтобы $this->findroute() , $this->findroute() ваши параметры в этот стек:
$stack[] = array($i, $distanceSoFar + $this->distanceArray[$curLoc][$i], $expectedValue);
Теперь окружайте в основном все в вашей функции в цикл while, стекающий стек после его загрузки:
while ($stack) { // Do stuff you already do in your function here
Вы можете преобразовать рекурсивную функцию в итеративную функцию, используя стек для хранения текущего состояния. Посмотрите на array_push() и array_pop() .
С первого взгляда я не думаю, что рекурсия – это ваша проблема, да, она медленная в PHP, но похоже, что вы переходите значения выше, чем вам нужно, помещая значения в стек или несколько стеков и обрабатывая их, может быть приятно ,
пользовательские функции сортировки всегда помогали мне в подобных проблемах.
function sort_by_visited($x,$y) { return ($this->locationsVisited[$x] > $this->locationsVisited[$y]) ? -1 : 1; } uasort($locationsVisited,'sort_by_visited');
Это будет приоритетом для всех не посещаемых местоположений в верхней части стека.
Это похоже на попытку найти оптимальный маршрут для обхода ряда узлов в графе.
Я предполагаю, что вы не изучали информатику, поскольку проблема «Путешествующий продавец» – это архетип искусственного интеллекта. Конечно, как таковой, у него есть своя страница Википедии:
http://en.wikipedia.org/wiki/Travelling_salesman_problem
Извините, но просто переключение с рекурсивной на итеративную функцию не ускорит ее работу («php не справляется с рекурсией». – можете ли вы предоставить ссылку для этого утверждения). Если вам нужно более быстрое решение, вам нужно посмотреть на не исчерпывающие / нечеткие методы.
C.