4

私はいくつかの双方向 A* アルゴリズムに取り組んでいます。私は端から端まで、そして最初から最後まで探しています。最初のスレッドが他のスレッド (開いているリストまたは閉じているリスト) からのノードに遭遇すると、スレッドは停止し、パスを引き戻します。

しかし、スレッドが異なるパスをたどり、本来あるべき場所で交わらない場合に問題が発生します。

例: http://i.imgur.com/ittIAlI.png

4

1 に答える 1

6

これは、Kaindl & Kainzが 1997年に不要であると証明するまで、双方向検索の研究を思いとどまらせる一般的な問題でした。問題。

最初に、 Yet Another Bidirectional Algorithm for Shortest Pathsを読むことをお勧めします。それが説明する (シリアル) NBA*アルゴリズムは、最初の論文で広く参照されています。

ここにあるオープン ソースの Hexgrid PathFinding ユーティリティを PNBA* のシリアル バージョンを使用するように適応させることに成功しました。(実際には NBA* と PNBA* のほぼ中間です) これは 1 日か 2 日以内にアップロードされます。

Making the Shortest Path Even Quickerでは、Bidirectional A* と前処理を使用して Bing Maps パス ファインダーを開発する方法の概要を説明しています。前処理作業の詳細な説明、および関連するアルゴリズムの使用は、Reach for A* and Better Landscape Within Reachで入手できます。

于 2013-07-03T01:01:57.927 に答える