情報に基づく対。情報に基づいていない検索アルゴリズム
1. 序章
このチュートリアルでは、情報に基づいていない検索戦略と情報に基づいた検索戦略について説明します。 これらは、検索問題を解決するために使用するアルゴリズムの2つの広いカテゴリです。
特に、いわゆるヒューリスティックは情報に基づいた戦略の重要な要素を表すため、適切に説明することに特に注意を払います。
2. 探索問題
非公式に、検索問題を解決するために、目標を達成する一連のアクションを探しています、いくつかの基準によって最適なシーケンスに関心があります。 たとえば、ポイントからポイントへ移動する方法はたくさんありますが、最短経路をたどりたいと考えています。
探索問題を正式に定義するには、そのコンポーネントを指定する必要があります。
- 開始する初期状態。 状態は、私たちが操作する現実の正式な数学的モデルです。2Dマップ上の点、チェス盤上のピースの配置などです。
- 「このポイントから次のポイントに移動する」または「クイーンを2マス垂直に移動する」などの状態で実行できるアクション。
- ある状態でアクションを適用すると、それがどのように変換されるかを示す遷移モデル。
- 状態が目標状態であるかどうかを確認する目標テスト。 目標状態は1つしかない場合もありますが、多く存在する場合もあります。
- 2つの状態間の各パスに数値コストを割り当てるコスト関数。 たとえば、チェスゲームの移動回数やゴール位置に到達するまでの推定時間などです。
コンポーネントが何であれ、開始状態と目標状態の間の最低コストのパスに対応する一連のアクションを常に探しています。
3. 情報に基づいていない検索
情報なしまたはブラインド検索戦略は、問題定義で提供するコンポーネントのみを使用する戦略です。したがって、目標状態と非目標状態のみを区別し、状態の内部構造を検査して推定することはできません。目標にどれだけ近いか。
たとえば、8パズルを解いているとしましょう。 これは、1から8までの数字と、隣接する数字と交換できる空のセルを含むグリッドです。 これが目標状態であるとしましょう。
情報に基づいていない戦略は、目標テストのみを適用でき、グリッドを検査できないため、次の2つの状態の間に違いはありません。
ただし、後者は前者よりも目標状態にはるかに近いです。 さらに、2つの状態のどちらかを選択すると、情報のないアルゴリズムがすべての子孫を探索する可能性があります。これは、目標が1つのアクションから離れているだけで、最初に探索する必要があることを認識できないためです。
幅優先探索、均一コスト探索、深さ優先探索、深さ制限探索、
4. インフォームドサーチ
対照的に、情報に基づく検索戦略では、問題定義で提供するもの以外の追加の知識を使用します。追加の知識は、ヒューリスティックと呼ばれる機能を通じて利用できます。 入力で状態を受け取り、目標にどれだけ近いかを推定します。
より正確に言うと、ヒューリスティックは、特定のノードの状態と目標状態（または、さらにある場合は最も近い目標状態）の間の最短経路のコストを推定する関数であると言えます。 1つより）。
たとえば、8パズルの問題のヒューリスティックとして、置き忘れたシンボルの数を使用できます。 目標状態に近いことを正しく検出します。 前者のヒューリスティック推定は8ですが、後者の推定は2です。
A *アルゴリズムは、情報に基づく検索戦略の古典的でおそらく最も有名な例です。 適切なヒューリスティックが与えられると、A *は開始ノードと目標ノードの間の最適なパスを見つけることが保証され（そのようなパスが存在する場合）、その実装は通常実際には非常に効率的です。 情報に基づくアルゴリズムの他の例は、最良優先探索、再帰的最良優先探索、および簡略化されたメモリ制限A*です。
5. 経験則
情報に基づくアルゴリズムはヒューリスティックに大きく依存しているため、それらを適切に定義することが重要です。 しかし、ヒューリスティックをどのように特徴付けて比較し、どれを使用するかを決定するにはどうすればよいでしょうか。 優れたヒューリスティック関数の特性は何ですか？また、ヒューリスティックを設計するときに注意する必要があるのは何ですか？ このセクションでは、これらのトピックについて説明します。
5.1. 精度と計算の複雑さの間のトレードオフ
ヒューリスティックを評価するための明白な基準は、その精度です。 ヒューリスティックな見積もりが実際のコストを反映するほど、ヒューリスティックはより有用になります。状態から目標までのパスの実際のコストが理想的なヒューリスティックであるように見える場合があります。
ただし、このような高精度には代償があります。 このようなヒューリスティックを使用する唯一の方法は、元の問題のインスタンスである、とゴールの間の最短経路を見つけることです。
高精度のヒューリスティックは通常、より多くの計算を必要とし、検索が遅くなります。 したがって、優れたヒューリスティックは、その精度と計算の複雑さのバランスを取り、前者を後者のためにある程度犠牲にします。
5.2. 効果的な分岐係数
ヒューリスティックを使用する情報に基づくアルゴリズムが、深さで目標状態を見つける前に、ノード（開始ノード以外）を含む検索ツリーを生成したとしましょう。
によって誘発される実効分岐係数（EBF）は、ノードを含めるために均一な深さのツリーが持つ必要のある分岐係数です。 そう：
とを知っているので、を計算できます。 ただし、アルゴリズムを1回だけ実行して、のEBFを決定することはできません。 これは、問題のインスタンスが変化し、との値が変化するためです。 さらに、アルゴリズム自体をランダム化することができる。
たとえば、ノードの子が目標に対して同じ推定コストを持っている場合、ランダムな順序でノードの子を探索する場合があります。または、ヒューリスティックが非決定的である場合があります。
これらの問題を克服するには、インスタンスのランダムな代表サンプルでEBFを計算する必要があります。 次に、平均スコアまたは中央値スコアを計算して、統計的不確かさを信頼区間または信頼区間で定量化できます。効率的なヒューリスティックは1に近いEBFを持ちます。
5.3. ドミナンス
EBFは、ヒューリスティックを特徴付けて比較する唯一の方法ではありません。 2つのヒューリスティックについて、すべての状態に対してそれが保持される場合、それがを支配すると言います。
ドミナンスは、少なくともA *アルゴリズムに関しては、パフォーマンスに直接影響します。 A * withは、を支配する場合にA * withよりも多くのノードを拡張することはありません（および両方のヒューリスティックは一貫しているか許容されます）。
-puzzle問題の2つのヒューリスティックを定義しましょう。これは、8パズルバージョンと同じですが、グリッドを使用します。
- 置き忘れたシンボルの数
- シンボルのゴール位置までのマンハッタン距離の合計
シンボルの置き忘れ（数字または空のセル）ごとに、ゴール位置までのマンハッタンの最小距離は1であることがわかります。 A *とランダムインスタンスを試してみると、の平均EBFがの平均EBFよりも小さいことがわかります。
6. ヒューリスティックの作成
効率的なヒューリスティックを考案するのは簡単ではないかもしれません。 幸いなことに、私たちが従うことができるいくつかのアプローチがあり、このセクションではそれらのうちの3つに言及します。
6.1. リラクゼーションを使用したヒューリスティックの作成
まず、元の問題を緩和することができます。 これを行うには、定義から特定の制限を削除して、元々隣接していなかった状態間に追加のエッジを作成します。
緩和された問題は状態空間により多くのエッジがあるため、解決が容易です。 緩和されたコストは、元の問題のヒューリスティックとして機能します。
6.2. サブ問題からのヒューリスティックの生成
解決が容易なサブ問題に焦点を当て、その解決策のコストをヒューリスティック関数として使用できます。
たとえば、8パズルゲームでは1〜4の数字にしか焦点を当てることができません。 これらの4つの数字だけをゴール位置に置く最短の一連の動きの長さをヒューリスティックとして使用してみましょう。
ヒューリスティックは、問題全体に対する最適なソリューションのコストを過小評価していますが、状態が目標からどれだけ離れているかを示唆しています。
6.3. データからヒューリスティックを学習する
3番目のオプションは、データからヒューリスティックを学習することです。 ペアのリストを想像してみましょう。ここで、は状態であり、はゴールまでの最適なパスのコストです。 このようなデータセットを収集するには、開始状態に設定し、情報に基づいていない検索戦略を実行します。 統計的変動を説明するために、いくつかの問題インスタンスをランダムに選択し、それらの検索スペースからいくつかの状態をサンプリングします。
その後、これらの入力に対して情報に基づいていない検索を実行し、最適なソリューションのコストを収集します。
データセットを作成したら、それを回帰問題として扱い、機械学習アルゴリズムを適用して、コストを概算するモデルを見つけることができます。 次に、そのモデルをヒューリスティックとして使用します。
状態表現が機械学習に適さない場合があります。 これは、状態が、ベクトルデータを期待する従来のアルゴリズムでは処理が難しい構造化オブジェクトである場合に発生する可能性があります。 この問題を克服するために、手動で選択した機能または自動的に設計された機能によって状態を表すことができます。
たとえば、パズルの問題の1つの特徴は、誤って配置された記号の数である可能性があります。これは、最初に使用したヒューリスティックです。 別の特徴を、ゴール状態で互いに隣接していない隣接するペアの数として定義できます。 次に、からへのマッピングを学習し、ヒューリスティックとして使用します。
7. 概要
最後に、これは情報に基づく対の要約です。 情報に基づいていない検索戦略：
8. 結論
この記事では、情報に基づいていない検索戦略と情報に基づいた検索戦略について説明しました。 情報に基づいていないアルゴリズムは問題の定義のみを使用しますが、情報に基づいた戦略では、目標状態への最適なパスのコストを推定するヒューリスティックを通じて利用可能な追加の知識を使用することもできます。.
ヒューリスティック推定が計算しやすい場合、情報に基づいた検索アルゴリズムは、情報に基づいていない検索アルゴリズムよりも高速になります。 これは、ヒューリスティックにより、検索ツリーの有望な部分に焦点を当てることができるためです。。 ただし、効率的なヒューリスティックを作成するのは簡単ではありません。
