php - PHP 验证中的 A* 实现

Question

这是我从网站 here 获得的代码我想知道这个 A* 的实现是否正确。我查看了它并将其与维基百科页面进行了比较，它似乎是有效的。我问的原因是因为在网站上它说这段代码中仍然存在错误，我试图找到它但找不到任何错误。不过我想更改它，以便将起点和终点作为输入参数

<?php

class AStarSolver
{
    function solve(&$s)
    {
        include_once('PQueue.class.php');
        $o = new PQueue();
        $l = array();
        $c = array();
        $p = array();
        $a = $s->getStartIndex();
        $z = $s->getGoalIndex();
        $d = $s->goalDistance($a);

        $n0 = array('g'=>0, 'h'=>$d, 'i'=>$a, 'p'=>NULL, 'f'=>$d);
        $o->push($n0, -$d);
        $l[$a] = TRUE;

        while (! $o->isEmpty())
        {
            $n = $o->pop();

            if ($n['i'] == $z)
            {
                while ($n)
                {
                    $p[] = $n['i'];
                    $n = $n['p'];
                }
                break;
            }

            foreach ($s->getNeighbors($n['i']) as $j => $w)
            {
                if ((isset($l[$j]) || isset($c[$j])) && isset($m) && $m['g'] <= $n['g']+$w)
                    continue;

                $d = $s->goalDistance($j);
                $m = array('g'=>$n['g']+$w, 'h'=>$d, 'i'=>$j, 'p'=>$n, 'f'=>$n['g']+$w+$d);

                if (isset($c[$j]))
                    unset($c[$j]);

                if (! isset($l[$j]))
                {
                    $o->push($m, -$m['f']);
                    $l[$j] = TRUE;
                }
            }
            $c[$n['i']] = $n;
        }
        return $p;
    }

}

?>

可以找到Pqueue的代码here

Answer 1

该站点表明该错误可能在 PQueue 中类。

在PQueue::pop这个

$j+1 < $m

是测试堆节点是否在$i有一个 child (在 $j )或两个(在 $j 和 $j+1 )。

但是$m这是 count($h)仅在循环的第一次迭代中，因为 --$m每次都会评估循环条件。

移动--$m在 array_pop 旁边它属于哪里，那将是一个少一个错误。

---

现在 AStarSolver .

变量是(相对于 Wikipedia pseudocode ):

• $o – 打开设置为优先队列；
• $l – 打开集合作为索引键控的映射；
• $c – 封闭集作为由索引键控的 map ；
• $n – 当前节点 (x);
• $m – 邻居节点 (y) ?;
• $j – 邻居节点索引。

我看到的问题:

• $n = $o->pop()后面没有 unset($l[$n['i']]) .由于两者 $o和 $l代表同一个集合，它们应该保持同步。

• 根据维基百科，闭集仅在启发式是单调(我认为距离启发式是单调的)时才使用，在这种情况下，一旦将节点添加到封闭集，它永远不会被再次访问。这段代码似乎实现了一些 other pseudocode ，它确实从封闭集中删除了节点。我认为这违背了闭集的目的，内循环中的第一个条件应该是

  if (isset($c[$j]) || isset($l[$j]) && isset($m) && $m['g'] <= $n['g']+$w)

  然后我们可以删除unset($c[$j]) .

• $m['g']在这种情况下应该是当前邻居的 g 分数，由 $j 索引.但是$m具有上一个循环遗留下来的任何值:对应于 $j 的节点在之前的迭代中。

  我们需要的是一种通过节点索引找到节点及其 g 分数的方法。我们可以将节点存储在 $l 中数组:而不是 $l[$j] = TRUE我们做$l[$j] = $m而上面的条件就变成了

  if (isset($c[$j]) || isset($l[$j]) && $l[$j]['g'] <= $n['g']+$w)

• 现在是棘手的一点。如果我们刚刚找到的节点不在开放集中，我们将其添加到那里(即 $o->push 和 $l[$j] = )。

  但是，如果它在开放集中，我们只是找到了更好的路径，所以我们必须更新它。代码没有这样做，而且它很棘手，因为优先级队列不提供增加元素优先级的例程。然而，我们可以完全重建优先级队列，内循环的最后一段代码变为

  if (! isset($l[$j])) {
   $o->push($m, -$m['f']);
   $l[$j] = $m; // add a new element
} else {
   $l[$j] = $m; // replace existing element
   $o = new PQueue();
   foreach ($l as $m)
      $o->push($m, -$m['f']);
}

  这不是非常有效，但它是一个起点。无论如何，更改优先级队列中的元素效率不高，因为您首先必须找到它。

---

即使没有这些更改，算法也会找到一条路径，只是不是最佳路径。你可以在提到的迷宫中看到它:

• 在crazy第三个内圈的迷宫:因为左边有障碍物，所以走的上面的路比下面的路稍微长一些。

• 在big路径右上角的迷宫有一个不必要的循环。

---

因为这是我的想法，所以我实现了我自己的算法版本并将其发布在对您的 previous question 的回答中。 .