PHP验证中的*实现

Question

这是我从网站上得到了一个代码在这里,我想知道这个实现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的代码

Answer 1

该网站表明该错误可能在PQueue课堂上.

在PQueue::pop这

$j+1 < $m

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

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

移动--$m到array_pop它所属的位置旁边,这将减少一个bug.

现在为AStarSolver.

变量是(相对于Wikipedia伪代码):

• $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 -score $j.但是$m具有从前一个循环遗留下来的任何值:与$j前一次迭代相对应的节点.

  我们需要的是一种按节点索引查找节点及其g -score的方法.我们可以将节点存储在$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路径右上方的迷宫中,有一个不必要的循环.

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