私はいくつかの双方向 A* アルゴリズムに取り組んでいます。私は端から端まで、そして最初から最後まで探しています。最初のスレッドが他のスレッド (開いているリストまたは閉じているリスト) からのノードに遭遇すると、スレッドは停止し、パスを引き戻します。
しかし、スレッドが異なるパスをたどり、本来あるべき場所で交わらない場合に問題が発生します。
私はいくつかの双方向 A* アルゴリズムに取り組んでいます。私は端から端まで、そして最初から最後まで探しています。最初のスレッドが他のスレッド (開いているリストまたは閉じているリスト) からのノードに遭遇すると、スレッドは停止し、パスを引き戻します。
しかし、スレッドが異なるパスをたどり、本来あるべき場所で交わらない場合に問題が発生します。
これは、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で入手できます。