将函数从递归转换为迭代

Question

我写的这个函数非常慢，因为 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;
        }
    }
}

Answer 1

我不会转换您的代码，但您可以通过创建堆栈将递归函数转换为迭代函数：

$stack= array();

并且不要调用 $this->findroute()，而是将参数推送到这个堆栈：

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

现在将函数中的所有内容基本上都包围到一个 while 循环中，在启动堆栈后耗尽堆栈：

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

Answer 2

您可以通过使用堆栈来存储当前状态，将递归函数转换为迭代函数。查看 array_push() 和 array_pop()。

Answer 3

乍一看，我不认为递归是你的问题，是的，它在 PHP 中很慢，但是看起来你对值的处理超出了你的需要，将值放入一个堆栈或多个堆栈中并处理它们，可能会很好。

自定义排序函数总是帮助我解决此类问题。

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

uasort($locationsVisited,'sort_by_visited');

这将优先考虑堆栈顶部所有未访问的位置。

Answer 4

这看起来就像您试图找到遍历图中一系列节点的最佳路线。

我猜你没有学过计算机科学，因为“旅行推销员”问题是人工智能的原型。当然，因此，它有自己的维基百科页面：

http://en.wikipedia.org/wiki /Travelling_salesman_problem

抱歉 - 但仅仅从递归函数切换到迭代函数并不会让它运行得更快（“php 不能很好地处理递归。” - 你能为这个断言提供参考吗）。如果您需要更快的解决方案，那么您需要查看非详尽/模糊方法。

C.