Artificial-intelligence-popular-search-algorithms

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

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

単一エージェントのパス検索の問題

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

シングルエージェントパス検索の問題の他の例は、巡回セールスマン問題、ルービックキューブ、定理証明です。

検索用語

• 問題スペース-検索が行われる環境です。 （これらの状態を変更するための一連の状態と一連の演算子）
• 問題インスタンス-初期状態＆plus;目標の状態。
• 問題空間グラフ-問題の状態を表します。 状態はノードで表示され、演算子はエッジで表示されます。
• 問題の深さ-初期状態から目標状態までの最短経路またはオペレーターの最短シーケンスの長さ。
• スペースの複雑さ-メモリに保存されるノードの最大数。
• 時間の複雑さ-作成されるノードの最大数。
• 許容-常に最適なソリューションを見つけるためのアルゴリズムのプロパティ。
• 分岐係数-問題空間グラフの子ノードの平均数。
• 深さ-初期状態から目標状態までの最短経路の長さ。

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

ドメイン固有の知識を必要としないため、最も簡単です。 少数の可能な状態で正常に動作します。

要件-

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

幅優先検索

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

分岐係数（特定のノードの子ノードの平均数）= bおよび深さ= dの場合、レベルd = b ^ d ^のノード数。

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

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

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

幅優先検索

深さ優先検索

LIFOスタックデータ構造を使用して再帰的に実装されます。 Breadth-Firstメソッドと同じノードのセットを、異なる順序でのみ作成します。

単一パス上のノードはルートノードからリーフノードへの各反復で保存されるため、ノードを保存するためのスペース要件は線形です。 分岐係数_b_および深さ_m_を使用すると、ストレージスペースは_bm._

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

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

深さ優先検索

双方向検索

初期状態から順方向に、目標状態から逆方向に検索して、両方が一致するまで共通の状態を特定します。

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

均一コスト検索

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

コストの増加順にパスを探索します。

欠点-コスト≤C *の長いパスが複数存在する可能性があります。 Uniform Cost検索では、すべてを調査する必要があります。

反復深化深さ優先検索

レベル1に対して深さ優先検索を実行し、最初からやり直し、レベル2に対して完全な深さ優先検索を実行し、ソリューションが見つかるまでこのような方法で続行します。

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

インタラクティブディープニングDF検索

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

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

Criterion	Breadth First	Depth First	Bidirectional	Uniform Cost	Interactive Deepening
Time	bd	bm	bd/2	bd	bd
Space	bd	bm	bd/2	bd	bd
Optimality	Yes	No	Yes	Yes	Yes
Completeness	Yes	No	Yes	Yes	Yes

インフォームド（ヒューリスティック）検索戦略

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

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

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

純粋な発見的検索

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

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

検索

これは、ベストファースト検索の最も有名な形式です。 すでに高価なパスを拡張することは避けますが、最も有望なパスを最初に拡張します。

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

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

貪欲な最高の最初の検索

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

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

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

彼らは将来の解決策から始めて、次に隣の解決策に移ります。 終了する前に中断された場合でも、有効なソリューションを返すことができます。

登山検索

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

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

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

欠点-このアルゴリズムは完全でも最適でもありません。

ローカルビーム検索

このアルゴリズムでは、任意の時点で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）の場合はelseを受け入れ、受け入れます。
• L（k）ステップについて、ステップ1と2を繰り返します。
• k = k＆plus; 1;

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

End

巡回セールスマン問題

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

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

旅行セールスマンの問題