AI-人気のある検索アルゴリズム

検索は、AIにおける問題解決の普遍的な手法です。タイルゲーム、数独、クロスワードなどのシングルプレイヤーゲームがいくつかあります。検索アルゴリズムは、そのようなゲームの特定の位置を検索するのに役立ちます。

シングルエージェントパスファインディングの問題

3X3 8タイル、4X4 15タイル、5X5 24タイルパズルなどのゲームは、シングルエージェントパス検索の課題です。それらは、空白のタイルを持つタイルのマトリックスで構成されています。プレイヤーは、ある目的を達成するために、タイルを垂直または水平に空白のスペースにスライドさせてタイルを配置する必要があります。

単一エージェントの経路探索問題の他の例は、巡回セールスマン問題、ルービックキューブ、および定理証明です。

検索用語

Problem Space−検索が行われる環境です。（状態のセットとそれらの状態を変更するための演算子のセット）
Problem Instance −初期状態＋目標状態です。
Problem Space Graph−問題の状態を表します。状態はノードで示され、演算子はエッジで示されます。
Depth of a problem −初期状態から目標状態までの最短パスまたは演算子の最短シーケンスの長さ。
Space Complexity −メモリに保存されるノードの最大数。
Time Complexity −作成されるノードの最大数。
Admissibility −常に最適解を見つけるアルゴリズムの特性。
Branching Factor −問題空間グラフの子ノードの平均数。
Depth −初期状態から目標状態までの最短経路の長さ。

ブルートフォース検索戦略

ドメイン固有の知識を必要としないため、最も単純です。それらは、少数の可能な状態で正常に機能します。

要件-

状態の説明
有効な演算子のセット
初期状態
目標状態の説明

幅優先探索

ルートノードから開始し、最初に隣接ノードを探索して、次のレベルの隣接ノードに向かって移動します。解が見つかるまで、一度に1つのツリーを生成します。FIFOキューデータ構造を使用して実装できます。この方法は、ソリューションへの最短経路を提供します。

場合 branching factor次いで、（所与のノードの子ノードの平均数）= Bと深さ= D、レベルD = B用のノードの数^D。

最悪の場合に作成されるノードの総数は、b + b ² + b ³ +…+ ^bdです。

Disadvantage−ノードの各レベルは次のノードを作成するために保存されるため、多くのメモリスペースを消費します。ノードを格納するためのスペース要件は指数関数的です。

その複雑さはノードの数に依存します。重複ノードをチェックできます。

深さ優先探索

これは、LIFOスタックデータ構造を使用して再帰的に実装されます。幅優先法と同じノードのセットを、順序が異なるだけで作成します。

単一パス上のノードはルートノードからリーフノードまでの各反復で格納されるため、ノードを格納するためのスペース要件は線形です。分岐係数bと深さmの場合、ストレージスペースはbmです。

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

その複雑さは、パスの数によって異なります。重複ノードはチェックできません。

双方向検索

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

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

均一コスト検索

ソートは、ノードへのパスのコストを増加させることで行われます。常に最小コストのノードを拡張します。各遷移のコストが同じである場合、幅優先探索と同じです。

コストの昇順でパスを探索します。

Disadvantage−コストがC *以下の長いパスが複数存在する可能性があります。均一コスト検索では、それらすべてを調査する必要があります。

反復深化深さ-最初の検索

レベル1まで深さ優先探索を実行し、最初からやり直して、レベル2まで完全な深さ優先探索を実行し、解決策が見つかるまでこのように続行します。

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

さまざまなアルゴリズムの複雑さの比較

さまざまな基準に基づいたアルゴリズムのパフォーマンスを見てみましょう-

基準	幅優先	深さ優先	双方向	均一なコスト	インタラクティブな深化
時間	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
スペース	b ^d	b ^m	b ^{d / 2}	b ^d	b ^d
最適性	はい	番号	はい	はい	はい
完全	はい	番号	はい	はい	はい

情報に基づく（ヒューリスティック）検索戦略

考えられる状態が多数ある大きな問題を解決するには、問題固有の知識を追加して、検索アルゴリズムの効率を高める必要があります。

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

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

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

ヒューリスティック値の順序でノードを展開します。すでに展開されているノードのクローズドリストと、作成されているが展開されていないノードのオープンリストの2つのリストが作成されます。

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

検索

これは、最良優先探索の最もよく知られた形式です。すでに高価なパスの拡張を回避しますが、最も有望なパスを最初に拡張します。

f（n）= g（n）+ h（n）、ここで

g（n）ノードに到達するための（これまでの）コスト
h（n）ノードからゴールに到達するための推定コスト
f（n）nから目標までのパスの推定総コスト。f（n）を増やすことにより、優先度付きキューを使用して実装されます。

貪欲な最良優先探索

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

Disadvantage−ループに陥る可能性があります。最適ではありません。

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

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

山登り検索

これは、問題の任意の解決策から始まり、解決策の1つの要素を段階的に変更することによって、より良い解決策を見つけようとする反復アルゴリズムです。変更によってより良いソリューションが生成される場合は、増分変更が新しいソリューションと見なされます。このプロセスは、それ以上の改善がなくなるまで繰り返されます。

関数Hill-Climbing（problem）は、極大値である状態を返します。

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage −このアルゴリズムは完全でも、最適でもありません。

ローカルビーム検索

このアルゴリズムでは、任意の時点でk個の状態を保持します。最初に、これらの状態はランダムに生成されます。これらのk状態の後続は、目的関数の助けを借りて計算されます。これらの後継者のいずれかが目的関数の最大値である場合、アルゴリズムは停止します。

それ以外の場合、（初期のk個の状態と状態の後続のk個= 2k）状態がプールに配置されます。次に、プールは数値でソートされます。最高のk状態が新しい初期状態として選択されます。このプロセスは、最大値に達するまで続きます。

関数BeamSearch（problem、k）は、解の状態を返します。

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

焼き鈍し法

アニーリングは、金属を加熱および冷却して内部構造を変更し、その物理的特性を変更するプロセスです。金属が冷えると、その新しい構造が押収され、金属は新しく得られた特性を保持します。シミュレーテッドアニーリングプロセスでは、温度は可変に保たれます。

最初に温度を高く設定し、アルゴリズムが進むにつれてゆっくりと「冷却」します。温度が高い場合、アルゴリズムはより悪い解を高頻度で受け入れることができます。

開始

k = 0を初期化します。L =変数の整数。
i→jから性能差Δを求めます。
Δ<= 0の場合は受け入れ、exp（-Δ/ T（k））> random（0,1）の場合は受け入れます。
L（k）ステップについて、ステップ1と2を繰り返します。
k = k + 1;

基準が満たされるまで、手順1〜4を繰り返します。

終わり

巡回セールスマン問題

このアルゴリズムの目的は、都市から始まり、途中のすべての都市を1回だけ訪問し、同じ開始都市で終わる低コストのツアーを見つけることです。

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end