-2

(A*) 経路探索

上下左右のみ

とにかく、よくわかりません。いくつかの例を確認しましたが、次のようになりますか?:

Point StartTile;
Point EndTile;
List<Point> CheckedPoints;
List<Point> UncheckedPoints;

そこで、StartTileをUncheckedPointsに追加します。

UncheckedPointsを循環し、(Up、Down、Left、Right) タイルをUncheckedPointsに追加します ( CheckedPointsにない場合)。チェックしたばかりのポイントを削除し、CheckedPointsに追加します。

UncheckedPointsのEndTileに到達するまで同じことを行います。

1 EndTile にアクセスできない場合はどうすればよいですか? どうすればこれを防ぐことができますか?

2 EndTile に到達できない場合、EndTile に最も近いタイルを取得する方法はありますか?

3 StartTile から EndTile までのタイルのリストを取得するにはどうすればよいですか? サイクルごとに長いリストを保持すると、大量のメモリが必要になりますよね?

4

1 に答える 1

1

1 EndTile にアクセスできない場合はどうすればよいですか? どうすればこれを防ぐことができますか?

いいえ、アルゴリズムは UncheckedPoints がある限り実行する必要があります。EndTile に到達したら中止できますが、それは必須ではありません。

また、CheckedPoints に既に含まれている UncheckedPoints にポイントを追加してはなりません。

2 EndTile に到達できない場合、EndTile に最も近いタイルを取得する方法はありますか?

はい、訪問したすべての ppint を CheckedPoints に保存するため、それらの中から最も近いポイントを選択できます。

3 StartTile から EndTile までのタイルのリストを取得するにはどうすればよいですか? サイクルごとに長いリストを保持すると、大量のメモリが必要になりますよね?

どのポイントからアクセスしたか、ポイントごとに保存できます。

これにより、必要なメモリが 2 倍になりますが、ループでの実行を避けるために、訪問したすべてのポイントを保存する必要があるため、「大量のメモリ」にはなりません。

--

ダイクストラのアルゴリズムを (グラフではなく) グリッドで見た方が簡単です。A* は、すべてのタイトルを一種のランダムな順序で探索するのではなく、最初に最後のタイルに最も近いタイトルを探索するための最適化です。

于 2013-02-18T18:19:28.930 に答える