グラフ検索とツリーのような検索
1. 序章
このチュートリアルでは、AIの検索問題を解決するための、グラフ検索（GS）戦略とツリーライク検索（TLS）戦略の2つの手法について説明します。
2. 探索問題と状態グラフ
検索問題とは、AIエージェントが、エージェントを開始状態から目標状態の1つに導く最適な一連のアクションを見つけることを目的とする問題です。エージェントが存在する可能性のあるすべての状態とどのアクションが1つの状態を別の状態に変換するかを示すリンクは、状態グラフを構成します。
状態は、問題に応じて、2Dマップ上のポイント、製品の駒を組み立てる順序、ボード上のチェスの駒の配置など、どのようなものでもかまいません。
3. 探索木
検索アルゴリズムは、状態グラフ内の状態にアクセス（到達）する順序が異なります。一部のアルゴリズムでは、その順序により、状態グラフに重ねられたツリーが作成され、そのルートは開始状態。 そのツリーを検索ツリーと呼び、それを成長させるアルゴリズムのみを検討します。
しかし、これらのアルゴリズムで検索ツリーをどのように成長させるのでしょうか。 状態に達するたびに、その状態でマークするノードを作成します。 後で、ノードを、その状態に到達したノードの子としてツリーに挿入します。
状態グラフの状態と検索ツリーのノードの違いがわかります。
ツリーのような検索戦略とグラフ検索戦略には違いがあります。 後者は、検索ツリーで状態を繰り返すことを回避します。
3.1. フロンティア
グラフ検索戦略がそれをどのように行うかを確認するには、最初に状態に到達することと状態を拡張することを区別する必要があります。
したがって、検索は一連の拡張と考えることもでき、拡張する前にまず状態に到達する必要があります。したがって、拡張できるため、到達したが拡張されていない状態を追跡する必要があります。それらだけ。 このような状態のセットをフロンティアと呼びます。 しかし、注意する必要があります。 一般に、どの状態にも複数のパスが存在する可能性があるため、状態に複数回到達する可能性があります。 これを行うたびに、ツリーの新しい候補ノードを取得します。
これらの理由から、検索戦略には2つのコンポーネントがあると結論付けます。
- ノードをフロンティアに配置するかどうかを決定するルール
- 拡張する次のフロンティアノードを選択するルール
4. グラフ検索（GS）
GSには、フロンティアに関する1つのルールがあります。
状態がすでに展開されている場合、または同じ状態を指すノードがすでにフロンティアにある場合は、ノードを追加しないでください。
それに準拠するすべてのアルゴリズムは、グラフ検索メソッドのクラスに属します。 GSの一般的な擬似コードは次のとおりです。
にノードを追加するためのアルゴリズム固有の条件がない場合があることに注意してください。 その場合、は常にを返す関数です。
4.1. 実装の詳細
アルゴリズム1から、ノード用の特別なデータ構造が必要であることがわかります。ノードはその状態へのパスを表すため、少なくとも問題のパス上の状態の先行ノードへのポインターを含める必要があります。 したがって、ノードは次の属性を持つオブジェクトである必要があります。
- 状態
- ノードの親へのポインタ：状態の先行ノードを含むノード
さらに、これらの情報も含めることでメリットが得られます。
- 親からノードにジャンプするために適用されるアクション
- パスの総コスト
実装方法は、GSの汎用形式を「サブクラス化」するアルゴリズムによって異なります。 UCS では、最小優先度キューですが、DFSではLIFOキュー。 の実装はと互換性がある必要があります。
実装する方法は複数あります。状態をキーとして、対応するノードを値として持つセットまたはキー値構造を使用できます。 選択するものが何であれ、高速なルックアップと挿入（およびUCSのような場合の削除と更新）をサポートする必要があります。
ゴールテストを適用するポイントを変更することもできます。ここでは、拡張するフロンティアノードを選択した後に変更します。 これはUCSと互換性があります。 ただし、ノードをフロンティアに追加する前にノードをテストすることもできます。 後者のアプローチはUCSでは機能しませんが、DFSとBFSでは機能します。 とにかく、私たちが目標テストを実施する時点では、アルゴリズムがGSタイプかTLSタイプかは判断されません。 したがって、テストをアルゴリズム1の内側のforループに移動しても、汎用GSを使用できます。
4.2. しかし、検索ツリーはどこにありますか？
状態グラフに重ね合わせる検索ツリーを使用して、GSおよびTLS戦略を導入しました。 ただし、GSの一般的な形式のツリーへの参照はありません。 なんで？
これは、検索ツリーが暗黙的であるためです。 ノードがツリーの新しいリーフになっていると見なすため、ノードを展開するたびに暗黙的にツリーを成長させます。 したがって、 GSの検索ツリーは、には存在するが存在しないノードで構成されます。
5. ツリーのような検索（TLS）
汎用GSアルゴリズムからへのすべての参照を削除することにより、TLSの汎用擬似コードを取得します。
for GSの機能と実装の詳細に関するすべてのコメントは、TLSにも当てはまります。 同じことが検索ツリーの暗黙性にも当てはまります。
TLSは繰り返される状態をチェックしないため、同じ状態を複数回拡張する可能性があります。 これにより、実行時間が長くなり、状態グラフにサイクルが含まれている場合は無限のループが発生する可能性があります。
6. 例
このセクションでは、DFSのGSバージョンとTLSバージョンを実装する方法を示します。 また、同じアルゴリズムの2つのバージョンが実際には異なる動作をすることも示します。 例として、次のグラフを使用します。
その中で、は開始状態ですが、どの状態も目標ではありません。
6.1. 深さ優先探索（DFS）
深さ優先探索の背後にある考え方は、最後に到達した状態のノードを拡張することです。したがって、フロンティアとしてLIFOキューを使用します。 追加するノードがなくなるか、目標状態に到達するまで、検索ツリーの深さを可能な限り増やします。
DFSでは、通常、フロンティアからノードを選択した後ではなく、状態に達した後に目標テストを実行します。 このようにして、アルゴリズムをより効率的にしますが、拡張するノードを選択した後にノードをテストすることは誤りではありません。
6.2. ツリーのようなDFS
TLSDFSの擬似コードは次のとおりです。
アルファベット順にノードを返すとしましょう。 これは、TLSDFSがこの例を処理する方法です。
ご覧のとおり、状態グラフが有限で小さい場合でも、TLS DFSはループに陥り、無期限に実行されます。
6.3. グラフ検索DFS
到達したすべての状態を記憶し、繰り返しをテストすると、GSDFSを取得できます。
ご覧のとおり、GS DFSは、ループに陥ることを回避します。
7. 討論
どちらの戦略が優れていますか？ TLSのようにループにとらわれることができないため、GSは常にTLSよりも優れているように見えるかもしれません。 ただし、答えは見た目ほど簡単ではありません。 GSは、到達するすべての状態を記憶する必要があるため、大きなメモリ要件を持つ可能性があります。
さらに、状態グラフが実際にツリーであり、サイクルが含まれていない場合は、GSではなくTLSアルゴリズムを使用する必要があります。 後者は不必要なメモリを必要とします。 成長することしかできないため、 RAM には大きくなりすぎて、ゴミ箱に入れて実行時間に負担をかける可能性があります。
ただし、GSとTLSの間の妥協点を見つけることができます。一般に、ループは冗長パスの特殊なケースです。 ノードによって表されるパスがノードによって表されるパスよりも長いかコストがかかる場合、前者のパスを冗長と呼びます。 すべてのアクションに負でないコストがある場合、すべてのループは冗長です。
妥協案は、ループのみをチェックすることであり、他のタイプの冗長パスはチェックしません。 ループ耐性のあるアルゴリズムを取得するためにTLSに追加する必要があるのは、内側のforループで表されるパスのどこかにあるかどうかを確認することだけです。
たとえば、ループ耐性のあるDFSは、TLS DFSがスタックするサイクルを回避しますが、それでも2回拡張します。
8. 結論
この記事では、グラフ検索とツリーのような検索戦略を紹介しました。 前者はループを回避しますが、後者よりもメモリを必要とします。 どちらのアプローチが適切かは、目前の探索問題によって異なります。
