1. 序章

このチュートリアルでは、双方向検索(BiS)について説明します。 これは、グラフの開始ノードと終了ノードの間の最短(または最低コスト)のパスを見つけるためのアルゴリズムです。

2. 探す

従来のAI検索アルゴリズムは、手元のグラフ上に検索ツリーを成長させます。ツリールートは開始ノードであり、検索アルゴリズムが他の頂点にアクセスするにつれて成長します。 アルゴリズムは、ターゲットノードに到達し、それをツリーに含めた後に停止します。 幅優先探索(BFS)深さ優先探索均一コスト探索(UCS) A*は例です。そのようなアルゴリズムの。 これらはすべて最良優先探索のインスタンスであり、単方向です。検索は単一ノードから波状に広がり、ツリーを形成します。

2.1. 双方向検索(BiS)の動機

これは簡単ですが、必ずしも最適なパスを検索するための最良の方法ではありません。 BFSを見てみましょう。 そのツリーのようなバージョンには、最悪の場合の時間と空間の複雑さがあります。ここで、は分岐係数の上限であり、は最も浅いゴールノードの深さです。 ただし、ゴールノードからも検索を開始すると、ノードが少なくなる可能性のある2つのツリーが作成されます。

双方向BFSの2つのツリーは、反対方向に同時に成長します。前方探索木は、前と同じように、開始ノードから成長し、ゴールノードに到達しようとします。 しかし、逆検索ツリーは、そのルートとしての目標から成長し、開始に到達しようとします。 2つのツリーが出会うと、開始頂点と目標頂点の間の最短経路が得られます(特定の条件下で)。 ただし、ツリー内のノードの総数は、開始ノードから単一のツリーを成長させた場合よりも少なくなると予想されます。

その理由を理解するために、スタートからゴールまでのパスの中央のノードで木が出会うと想像してみましょう。 次に、ツリーは一緒に最大でノードを含みます。 一定の分岐係数とを使用すると、最悪のシナリオでは、単方向BFSはノードを含むツリーを成長させますが、BiBFSのツリーにはノードが一緒に含まれます。 これは、ノードの50億分の1です。

2.2. 双方向検索の基本アルゴリズム

BiSは一般的な検索手法です。 任意の単方向アルゴリズムを使用して順方向検索を実行し、それを逆方向検索用の任意の単一ソースアルゴリズムと組み合わせることができます。これらは同じである必要はありませんが、同じである必要はありません。 つまり、BiSは、順方向検索と逆方向検索のさまざまな基本アルゴリズムを組み合わせて取得する多数のメソッドを記述しています。

3. リバースエッジ

からの有向エッジは、AIエージェントがからに取得するために実行する必要のあるアクションを表します。 ただし、逆検索は反対方向に行われるため、グラフのすべてのエッジを逆にする必要があります。 したがって、 BiSを実行するには、グラフを両方向にトラバースする必要があります

元の前縁とは異なり、それらの逆の対応物はアクションを示すことができますが、必ずしもそうする必要はありません。 からの逆エッジは、からにつながるアクションがあることを意味します。 逆アークが存在するために、からにつながる実際のアクションは必要ありません。 反転は計算上のみ可能である必要があります。

たとえば、時間がノードの機能であり、各順方向アクションの期間がゼロ以外の場合、逆方向アクションは不可能になります(タイムマシンがない限り)。 それでも、それらを計算で定義できれば、BiSを使用できます。

4. 双方向UCS

双方向検索の場合、グラフのどこかで一致するように順方向検索と逆方向検索を目指していると言いました。 これは、両方が同じノードに到達したことを意味します。 ただし、双方向アルゴリズムを実装するために知っておくべきことが他にもあります。

  • 検索を交互に行う必要がありますか? はいの場合、どのように?
  • 最適なパスは必ずミーティングポイントを通過しますか?

双方向UCS(BiUCS)の例で両方の質問に答えます。

4.1. 交替

概念的には、2つの検索を並行して実行しています。 ただし、実際には、同じCPUで両方を同時に実行することはできません。 私たちにできることは、順方向検索と逆方向検索をインターリーブすることです。

検索ステップをメインの単方向UCSループの本体として定義しましょう。 BiUCSには、メインループも1つありますが、各反復で、どの検索を進めるかを選択します。 1つの戦略は、検索を交互に行うことです。つまり、順方向に実行し、次に逆方向に実行し、次に再度順方向に実行し、次に再び逆方向に実行します。 もう1つの方法は、フロンティアの最上位ノードがそのソース(開始または目標)に近い検索のステップを実行することです。 どちらの方がよいですか?

後者の戦略は、単方向UCSの精神とより一致しており、ソースに最も近いフロンティアノードを拡張することです。 BiUCSには2つのフロンティアがあるため、フロンティアのソースに近いノードを選択します。 ただし、戦略は一方向にのみ検索を実行するように退化する可能性があります。 たとえば、エッジのコストがゴールに近づくにつれて指数関数的に増加する場合、逆のステップを実行しない可能性があります。 このシナリオを回避するために、各順方向ステップを逆方向にたどり、各逆方向ステップを順方向にたどることによって、検索を交互に行うことができます。 それでも、両方の戦略は、次に説明する停止基準の下で機能します。

4.2. 停止状態

双方向検索の目的は、順方向検索と逆方向検索がいくつかのノードで出会うことであると言いました。 アルゴリズム的には、それは、他の検索で展開した後、一方向に到達するポイントです。 しかし、その時点でアルゴリズム全体を停止し、(を介して)最適なパスを見つけたと主張する必要がありますか?

フロンティアにゴールノードを追加した後に単方向UCSを停止するべきではないのと同様に、ノードが一方の検索で拡張され、もう一方の検索でフロンティアに配置された場合、双方向バリアントを終了するべきではありません。 その理由は、追加された2番目のフロンティアのソースからの低コストのパスが存在する可能性があるためです。

では、正しい停止条件は何ですか?これが、これまでに見つけた最良のパスのコストであるとしましょう(最初はに設定しました)。 他の検索で展開したノードに到達するたびに、より適切なパスがノードを通過するかどうかを更新します。 スタートからの現在の距離とゴールノードからの現在の距離とします。 フォワードフロンティアキューとリバースフロンティアキューの最上位ノードまでの距離をそれぞれとします。 次に、次の場合にアルゴリズムを停止できます。

   

4.3. 停止条件の正確さ

停止条件が得られたとしましょう。 前方検索で展開されていないノードの場合、それは次のように保持されます。ここで、は開始からの実際の距離です。 逆検索で展開されていない場合も同様に当てはまります。ここで、はゴールからの実際の距離です。

ここで、後続の順方向ステップでノードを展開し、その後続ノードが逆検索ですでに展開されていると仮定します。 通過するパスとコストは次のとおりです。

   

なぜなら、私たちはフォワードフロンティアに追加し、後でそれを拡張するからです。

   

停止状態の後に拡張したためです。 したがって、パスのコストはになります。

他のケースでは、停止条件が取得される前に逆検索で拡張したため、それを結論付けることはできません。 ただし、まだ逆展開されていないので、それはわかっています。 パスのコストもであるため、次のようになります。

   

したがって、は最適パスのコストであり、停止条件の正しさを証明します。

4.4. 双方向検索の擬似コード

最後に、BiUCSの擬似コードは次のとおりです。

この関数は、グラフの検索を進め、を更新する役割を果たします。 仕組みは次のとおりです。

5. 討論

BiSは、明示的な目標ノードがある場合にのみ可能です。目標テストしかない場合、逆検索を実行することはできません。 リバースエッジが計算上扱いにくい場合も同様です。

複数のゴールノードがあることは、それらがすべて明示的である限り、問題ではありません。 逆検索のソースとしてどちらを選択しますか? ない。 人工的なゴールノードを構築し、それをゼロコストエッジで実際のゴールにリンクし、それをリバースソースとして設定します。

BiSは、単方向検索よりも高速に最適なパスを見つけることが期待されていますが、実装とデバッグが困難です。 可能ではありますが、順方向検索と逆方向検索に異なるアルゴリズムを組み合わせるのは正当化されない場合があります。 すべてのエッジのコストが一定である場合、両方の検索でBFSまたは反復深化を選択するのが最善です。 エッジコストが異なる場合は、UCSまたはA*を双方向化する必要があります。

最後に、停止条件は、定式化および証明が難しい場合があります。正しく設計すれば、BiSは最適かつ完全になる可能性があります。 前者は、次善のパスを返すことができないことを意味しますが、後者は、パスまたは失敗の通知のいずれかを返すことを常に終了することを意味します。 停止条件は基本アルゴリズムによって異なります。

6. 結論

この記事では、一般的な双方向検索(BiS)と双方向UCS(BiUCS)を紹介しました。 BiSは、2つの単方向アルゴリズムを並行して実行する汎用検索アルゴリズムです。1つは検索ツリーを開始から目標まで成長させ、もう1つは目標から開始まで成長させます。一般的に、 BiSが単一ソースアルゴリズムよりも速く最適なパスを見つけることを期待します。 ただし、特に停止基準に関しては注意深い設計が必要であり、実装とデバッグが困難です。