均一コスト探索と最良優先探索
1. 序章
このチュートリアルでは、2つの検索アルゴリズムを提示して比較します。 それらは、均一コスト探索（UCS）と最良優先探索です。
2. 探す
探索問題では、開始状態を目標状態に変換するアクションの最短シーケンスを見つけたいと考えています。 状態は何でもかまいません。 たとえば、地図上のポイントやチェス盤上の駒の配置などです。
ノードが状態を表す抽象的なグラフで開始と目標の間の最短経路を見つけることによってシーケンスを決定します。有向エッジは、ある状態から別の状態につながるアクションです。 グラフを検索して、検索ツリーを作成します。 そのノードは、さまざまな状態へのパスを表します。 複数のノードが同じ状態を参照する可能性があるため、ツリー内の状態とノードの区別は非常に重要です。
通常、ノードは、ノードが表すパスの終了状態で示されます。
検索グラフのノードを接続するエッジには、コストとも呼ばれる重みがある場合があります。 そのような場合、スタートとゴールの間のエッジが最も少ないパスには関心がありません。 しかし、最も低コストのもので.
複数の目標の状態がある場合は、任意の目標につながるすべてのパスの中で最良のものが必要です。
3. 均一コスト検索
均一コスト検索（UCS）を使用して、開始状態と目標状態を表すノード間の最低コストのパスを見つけます。
UCSは、幅優先探索と非常によく似ています。 すべてのエッジのコストが等しい場合、幅優先探索が最適なソリューションを見つけます。 ただし、コストが異なる場合は、次の最適なパスが返される可能性があります。
3.1. 幅優先探索からのUCSの導出
UCSは、3つの変更を導入することにより、幅優先探索を改善しています。
まず、優先キューをフロンティアとして使用します。 フロンティアノードを、開始ノードからフロンティアノードへのパスのコストの順に並べ替えます。 拡張するノードを選択するとき、UCSはフロンティアから最小値のノード、つまりコストが最も低いノードを選択します。
ただし、フロンティアにノードを追加した後は、ノードの状態への最適なパスのコストがわかっているわけではありません。 ノードを展開して、隣接ノードへのパスのコストが、未満であることがわかった場合、はと同じ状態を表すフロンティアノードです。フロンティアから削除して、に置き換える必要があります。 このキュー更新ステップは2番目の変更です。
三つ目はノードをフロンティアに置いたときではなく、ノードを拡張した後にゴールテストを適用します。
幅優先探索によって返される次善のパスの例を見てみましょう。 展開してゴールノードが隣接ノードであることに気付いた直後に検索を停止すると、を通過する最適なパスを見逃します。
3.2. 擬似コード
したがって、これが均一コスト検索の擬似コードです。
ここに示すバージョンは、ノードを追加する前にノードの状態がすでにフロンティアにあるかどうかをチェックするため、アルゴリズムのグラフ検索バージョンです。 ツリーのような検索は、繰り返される状態をテストせず、ツリーに最適です。 ただし、実行時間が長くなったり、サイクルが原因で無限に実行されたりするリスクがある場合は、一般的にグラフで使用できます。
呼び出しが生成する各ノードは、その親としてへのポインターを含む構造体であると想定しています。 したがって、UCSがノードを返すと、アクションのパスを簡単にトレースできます。
3.3. 例
次に、UCSの動作例を示します。 以前と同じグラフを使用します。 最初は、開始ノードのみがフロンティアにあり、その値は0です。
開始ノードを展開した後、フロンティアに2つのノードがあり、関連する値がそれぞれ1とである。
は値が低いため、値を拡張すると、後続ノードのコストがノードよりも低く、フロンティアでも表されていることがわかります。 したがって、フロンティアを’後継者に置き換えます。
を展開すると、目標テストに合格することがわかります。したがって、最適なパスはであると結論付けます。
4. UCSの分析
通常、検索アルゴリズムについて4つの質問をします。
- 完了しましたか？いずれかの入力で終了すると、アルゴリズムは完了します。
- それは最適ですか？開始状態から少なくとも1つの目標状態に到達可能であれば、アルゴリズムが目標への最適なパスを返す場合に最適であると言います。 複数の州が目標テストに合格した場合、任意の目標につながるすべてのパスの中で最も低コストのパスが必要です。
- アルゴリズムの時間計算量はどれくらいですか？
- そのスペースの複雑さは何ですか？
このセクションでは、UCSに関するこれらの質問に回答します。
4.1. UCSの完全性
検索グラフが有限である場合、UCSのグラフ検索バージョンは完了です。 グラフが無限であるが、ノードの数が無限であり、すべてのエッジに正のコストがある場合、グラフ検索UCSも完了します。 エッジコストが厳密に正であるという条件は、ノードUCSが永久に拡張し続けるゼロコストエッジを持つ無限のパスが存在しないことを保証します。
ただし、グラフが有限であっても、ツリーのようなUCSがループに陥る可能性があります。 たとえば、サイクルがある場合に発生する可能性があります。
4.2. UCSの最適性
UCSの最適性を証明するために、最初に次のプロパティを証明しましょう。
UCSがノードを展開すると、開始ノードからへの最適なパスが見つかりました。
言い換えると、展開の時点で、はで表される状態への最適なパスのコストです。 （技術的には、検索ツリーのノードはフルパスを表しますが、ノードはそれらのパスのエンドノードを表すかのように話すのが一般的です。）
拡張されたノードのセットのカーディナリティを誘導することによってこのプロパティを証明します。フロンティア内の任意のノードに対してその事実を利用します。 それが成り立つ理由を理解するために、フロンティア状態へのより良いパスが見つかった場合は、フロンティア状態の優先度を更新することを忘れないでください。 つまり、はの上限です。 誘導では、UCSがノードをフロンティアからポップして拡張する時点で同等性が維持されることを証明します。
4.3. 基本ステップと帰納的仮説
ベースステップには、があります。 これは、UCSがキューから開始ノードをポップする場合です。 定義上、、、およびこれは、エッジをトラバースする必要がないため、開始状態からそれ自体への最適なパスのコストです。
ここで、このプロパティが次のようなものに対して成り立つという帰納的仮説を立てます。 帰納的ステップでは、それがどのにでも当てはまることを証明したいと思います。
帰納的仮説により、プロパティはに当てはまるので、それが同様に当てはまることを証明する必要があるだけです。 矛盾してやります。
4.4. 帰納的ステップ
つまり、これがこの時点でのUCSの状態です。 私たちはそれをフロンティアからポップして拡張することを選択しました、そして私たちはそのコストが次のようなものへの道を持っています：
現在、フロンティアは拡張されたノードを拡張されていないノードから分離しています。 したがって、開始ノードから拡張されていないノードへのパスはすべて、フロンティアの頂点を通過します。 それを念頭に置いて、次の代替パスを想像してみましょう。
そして、それがへの最適なパスであると仮定すると、青いパスはそうではありません。 次に、それは成り立ちます：
(1)
代替パスで最後に展開されたノードは、であり、通過する最初のフロンティアノードはです。 からへのパスの一部には、任意の数のエッジを含めることができます。 したがって、エッジに負でないコストがある場合、代替パスのコストは少なくとも次のようになります。
(2)
4.5. 矛盾
エッジは最適なパス上にあり、拡張されており、隣接しているため、ポップしたときの-valueは次のようになります。
(3)
また、UCSが拡張を選択したため、これは、を含むフロンティア内のすべてのノードの中で最小値を持つことを意味します。 そう：
(4)
式を連鎖させると、次のようになります。
(5)
これは矛盾です。 したがって、を展開すると、その状態への他のパスのコストが。より低くなることはありません。 したがって、 。 しかし、条件はすべてのエッジに負でないコストがあることです。
4.6. 複数のゴールノードがある場合
これは、UCSがゴールノードを拡張すると、その状態への最適なパスが見つかることを意味します。 ただし、複数の目標状態が存在する場合があります。 エッジコストは負ではなく、UCSはフロンティアノードを値の順に拡張するため、最初のゴールノードの後に拡張されたゴールノードは、少なくとも最初のゴールと同じコストのパス上にあります。
したがって、実際、UCSは最適であり、状態の最適なパスコストの順にノードを拡張します。
4.7. UCSの時間と空間の複雑さ
検索グラフのエッジの最小コストをとして示しましょう。 また、任意のゴールノードへの最適なパスのコストとします。 UCSを完成させるために、次のことを前提としています。
次に、UCSが最も近いゴールノードを見つける検索ツリーの深さは最大でです。 が分岐係数の上限である場合、ツリーのようなUCSの時間計算量はです。
スペースの複雑さについても同じことが言えます。 フロンティアは最も近いゴールの深さですべてのノードを保持する可能性があるため、スペースの複雑さもです。
グラフ検索UCSに関しては、時間計算量はグラフのサイズによって制限されます。 がノードを示し、がエッジのセットである場合、グラフ検索UCSの最悪の場合の時間計算量はです。 スペースの複雑さもです。
5. 最良優先探索
最良優先探索（BeFS）は、一般的な検索アルゴリズムです。 UCSのすべての入力引数と、さらに1つの引数があります。 追加の引数は評価関数です。 BeFSはこれを使用して、優先キューとして実装されているフロンティアを順序付けます。
BeFSは、評価関数を変更することで検索戦略を変更できるため、汎用アルゴリズムです。
5.1. BeFSと冗長パス
アルゴリズム2に示されている定式化は、繰り返される状態をチェックするため、BeFSのグラフ検索バージョンです。 そうすることで、BeFSは冗長なパスの探索を回避します。 たとえば、ノードがと同じ状態を示している場合、ノードへのパスは冗長ですが、へのパスは短くなります。 ただし、冗長パスを回避するために、グラフ検索BeFSは大量のメモリを必要とします。
すべてのノードをメモリに保存できない場合は、ツリーのようなBeFSを使用できます。 アルゴリズム2からへのすべての参照を削除することで取得します。 ただし、冗長パスの特殊なケースである無限サイクルでスタックするリスクがあります。
妥協案は、サイクルのみをチェックすることです。アルゴリズム2で拡張すると、それを行うことができます。 子ごとに、へのパスにが表示されるかどうかを確認する必要があります。 これは、開始ノードに到達するまでポインターをたどることによって実行できます。 したがって、ループに陥ることはありませんが、必要以上に多くのパスを探索する可能性があります。
5.2. BeFSから他のアルゴリズムを導出する
開始ノードからへのパスのコストとして定義すると、UCSが得られます。 検索ツリーの深さに設定すると、BeFSは幅優先探索になります。 深さ優先探索（DFS）を取得できますか？ はい、負の深さに設定すれば可能です。 ただし、DFSは通常、再帰的アルゴリズムとして実装されます。
BeFSで、情報に基づいた検索戦略をシミュレートすることもできます。 たとえば、目標までの距離のヒューリスティック推定として使用する場合、最適なアルゴリズムではない貪欲な最良優先探索（GBFS）が得られます。 しかし、UCSとGBFSを組み合わせると、有名なA*アルゴリズムが得られます。
5.3. BeFSの分析
BeFSの完全性、最適性、および複雑さは、評価関数の選択によって異なります。
たとえば、フロンティアの順序付けにヒューリスティックのみを使用すると、最適なアルゴリズムが得られません。 負の深さを使用すると、完全なアルゴリズムではないDFSが得られます。 ただし、ノードの深さを評価関数として使用すると、幅優先探索が得られます。これは、完全に特定の条件下にあります。
6. 討論
完全に指定された情報のないアルゴリズムであるUCSとは異なり、BeFSは一般的な形式の検索方法です。 BeFSは、さまざまな評価関数を使用して、情報に基づいたものと情報に基づいたものの両方で、多数の検索手法をシミュレートできます。 順序付け戦略を完全に指定しないと、BeFSを実行できません。
このような大きな違いを生むのは、まさにフロンティアの順序付けに使用される関数です。 BeFSでは、変更可能な入力パラメーターです。 対照的に、UCSがキューをソートする方法を変更することはできません。
どちらが良いですか？ いつBeFSを使用する必要があり、いつUCSを使用する必要がありますか？ まず、UCSはBeFSのインスタンスであるため、UCSを実行するときに技術的にBeFSを実行しています。 ただし、 UCSのBeFS定式化は実際には遅くなる可能性があります。フロンティア順序付け関数は、そのフレームを再帰スタックに追加する実際の関数であるためです。 別の方法は、BeFSを参照せずにUCSを最初から実装することです。
BeFSルーチンを呼び出さなくても、任意のBeFS戦略を実装できます。 さらに、フロンティアの注文には独自の関数の呼び出しが含まれないため、これらの実装はより高速になります。
ただし、アルゴリズム全体をコーディングするのではなく、フロンティアの関数のみを指定する方がアルゴリズムの実装が簡単です。 ある検索戦略から別の検索戦略に切り替えたい場合は、確かにそうです。
7. 結論
この記事では、均一コスト探索（UCS）と最良優先探索（BeFS）について説明しました。 前者は完全に指定された情報に基づいていない検索戦略ですが、後者は情報に基づいたものと情報に基づいていないものの両方のさまざまな検索方法をシミュレートできる一般的なアルゴリズムです。 BeFSを使用してUCSをシミュレートすることはできますが、ネイティブのUCS実装は通常より高速に実行されます。
