人工知能.com

深さ優先検索

これは、LIFOスタックデータ構造を持つ再帰で実装されています。 これは、幅広い優先メソッドと同じノードセットを、異なる順序でのみ作成します。

単一パス上のノードは、ルートからリーフノードまでの各繰り返しに格納されるため、ノードを格納するためのスペース要件は線形です。 分岐ファクタbおよび深さをmとすると、記憶空間はbmである。

欠点 - このアルゴリズムは終了せず、1つの経路上で無限に進むことができます。 この問題の解決策は、カットオフの深さを選択することです。 理想的なカットオフがdであり、選択されたカットオフがdより小さい場合、このアルゴリズムは失敗する可能性がある。 選択されたカットオフがdより大きい場合、実行時間が長くなります。

その複雑さはパスの数に依存します。 重複したノードをチェックすることはできません。

双方向検索

初期状態から目標状態から前方に検索し、両方が一致して共通状態を識別する。

初期状態からの経路は、目標状態からの逆経路と連結される。 各検索は、全パスの半分までしか行われません。

統一コスト検索

ソートは、ノードへのパスのコストが高まることで行われます。 常に最小コストのノードを展開します。 各遷移に同じコストがある場合は、幅優先検索と同じです。

コストの高い順に経路を探索します。

短所 - コストがC *以下の複数の長いパスが存在する可能性があります。 統一原価検索はそれらすべてを探索する必要があります。

反復深度深度優先探索

それは、レベル1への深さ優先探索を行い、最初から始めてレベル2への完全な検索を実行し、解決が見つかるまでそのように継続します。

すべての下位ノードが生成されるまでノードを作成しません。 ノードのスタックを保存するだけです。 アルゴリズムは、深さdの解を見つけると終了する。 深さdで作成されるノードの数はb dであり、深さd-1でのノードの数はb d-1である。

ヒューリスティック評価関数

彼らは、2つの状態間の最適経路のコストを計算する。 スライディングタイルゲームのヒューリスティック関数は、各タイルが目標状態から作る移動回数をカウントし、これらの移動回数をすべてのタイルに加算することによって計算されます。

純ヒューリスティック検索

ノードはヒューリスティックな値の順に展開されます。 すでに展開されているノードの閉じたリストと、作成されているが展開されていないノードの開いたリストの2つのリストが作成されます。

各反復では、最小ヒューリスティック値を持つノードが展開され、そのすべての子ノードが作成され、閉じられたリストに配置されます。 次に、ヒューリスティック関数が子ノードに適用され、それらはヒューリスティックな値に従ってオープンリストに置かれます。 短いパスは保存され、長いパスは保存されます。

A *検索

これは、ベストファースト検索の最もよく知られている形式です。 すでに高価なパスを拡張するのを防ぎますが、最も有望なパスを最初に拡張します。

f（n）= g（n）＆plus; h（n）、ここで

• g（n）ノードに到達するためのコスト（これまでのところ）

• h（n）ノードからゴールまでの推定コスト

• f（n）nから目標までのパスの推定総コスト。 これは、f（n）を増やすことによって優先度キューを使用して実装されます。

欲張りのベストファーストサーチ

それは、目標に最も近いと推定されるノードを拡張する。 f（n）= h（n）に基づいてノードを展開する。 優先度キューを使用して実装されます。

短所 - ループに詰まる可能性があります。 最適ではありません。

ローカル検索アルゴリズム

それらは将来のソリューションから開始し、次に近隣のソリューションに移動します。 彼らは終了する前にいつでも中断されても、有効な解決策を返すことができます。

ヒルクライミング検索

これは反復的アルゴリズムであり、問​​題の任意の解で始まり、解の単一要素を徐々に変更することによってより良い解を見つけようとします。 変更によってより良い解決策が生まれる場合は、新しい解決策として漸進的な変更が行われます。 このプロセスは、それ以上の改善がなくなるまで繰り返されます。