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

のヒープノードに$i子が1つ（at $j）または2つ（at$jおよび$j+1）あるかどうかのテストです。

ただし、ループ内の条件は毎回評価されるため、これはループの最初の反復のみ$mです。count($h)--$m

--$mそれが属する場所の隣に移動するarray_popと、バグが1つ少なくなります。

今のために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']);
    }

    これはそれほど効率的ではありませんが、出発点です。優先キュー内の要素を変更することは、最初にそれを見つけなければならないため、とにかく効率的ではありません。

これらの変更がなくても、アルゴリズムはパスを検出しますが、最適なパスではありません。あなたは言及された迷路でそれを見ることができます：

  • 3番目の内部回路のcrazy迷路では、左側の障害物のために、周りの上部のパスが下部のパスよりもわずかに長くなっています。

  • bigパスの右上部分の迷路には、不要なループがあります。

これが私の頭の中にあったので、私は自分のバージョンのアルゴリズムを実装し、それをあなたの前の質問への回答に投稿しました。

于 2011-03-01T21:03:06.340 に答える