将函数从递归转换为迭代

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;
        }
    }
}

- Eric Conner

---

你尝试过在for循环体中添加某种调试/打印语句，显示递归发生的时间和数量吗？从检查代码来看，它对我来说有点奇怪。在转换为迭代使用之前，我会先检查一下这个问题。 - DaveC

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

- Kristopher Ives

---

这给了我一个好的开始，但我在弄清楚回溯步骤时遇到了麻烦。我需要设置 $this->locationsVisited[$curLoc] = true，然后迭代它为真，然后再将其关闭。 - Eric Conner

Answer 2

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

- Ignacio Vazquez-Abrams

Answer 3

乍一看，我不认为递归是你的问题，虽然在PHP中它很慢，但看起来你比需要更多地遍历值，在堆栈或几个堆栈中放置值并处理它们可能会很好。

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

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

uasort($locationsVisited,'sort_by_visited');

这将把所有未访问的位置优先放在堆栈顶部。

- Fire Crow

Answer 4

这似乎是您正在寻找在图中遍历一系列节点的最优路径。

我猜想您没有学过计算机科学，因为“旅行商”问题是人工智能的典型范例。当然，它有自己的维基百科页面：

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

抱歉 - 但仅仅从递归函数转换为迭代函数并不能让它运行更快（“php 不擅长处理递归。”- 您能提供此断言的参考资料吗）。 如果您需要更快的解决方案，则需要考虑非穷举/模糊方法。

C.

- symcbean

---

【1999年8月7日下午12:25 UTC】[e-mail] 4.0（Zend）使用堆栈来处理大量数据，而不是使用堆。这意味着它对递归函数的容忍度比其他语言低得多。相对容易地告诉Zend不要使用堆栈来处理此数据，而是使用堆 - 这将极大地增加可能的递归函数数量 - 以减慢速度为代价。如果您对这样的设置感兴趣，请告诉我，我们可以添加编译时开关。我应该只是转换到C或其他什么东西... - Eric Conner

它只涉及到“容忍度”，而没有提及性能或可靠性 - 我认为你会发现这种说法的意味是递归因此受堆栈大小限制（在大多数设置中，默认情况下堆比栈要小得多）。将你的开发转换成C并不会降低算法的级别，它仍然是N!。C. - symcbean