6

这是我从这里的站点获得的代码，我想知道 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 的代码可以在这里找到

4

1 回答 1

9

该网站建议该错误可能在PQueue课堂上。

在PQueue::pop这个

$j+1 < $m

测试堆节点 at 是否$i有一个子节点 (at $j) 或两个子节点 (at $jand $j+1)。

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

将它移到它所属--$m的位置旁边array_pop，这将减少一个错误。

现在为AStarSolver.

变量是（相对于维基百科伪代码）：

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

我看到的问题：

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

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

    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->pushand $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路径右上角的迷宫中，有一个不必要的循环。

由于这是我的想法，我实现了我自己的算法版本并将其发布在对您之前问题的回答中。

于 2011-03-01T21:03:06.340 回答