推奨されます, 2019

エディターズチョイス

インフォームド検索とインフォームド検索の違い

検索は、問題を解決するために必要な一連のステップを見つけるプロセスです。 インフォームド検索と非インフォームド検索の以前の違いは、インフォームド検索がどこでどのように解決策を見つけるかについてのガイダンスを提供することです。 逆に、情報なし検索では、その指定以外に問題に関する追加情報はありません。

ただし、インフォームド検索手法と非インフォームド検索手法の両方で、インフォームド検索はより効率的で費用対効果に優れています。

比較表

比較基準インフォームド検索情報のない検索
基本
解決策へのステップを見つけるために知識を使用します。知識を使わない
効率
時間と費用が少なくてすむので非常に効率的です。効率は瞑想的です
コスト低い比較的高い
パフォーマンスより迅速に解決策を見つける情報検索より速度が遅い
アルゴリズム
深さ優先探索、幅優先探索、最低コスト優先の探索ヒューリスティックな深さ優先および幅優先探索、およびA *検索

インフォームド検索の定義

インフォームドサーチ技術は、問題の解決への手がかりを与えるために問題固有の知識を利用する。 この種の検索戦略は、実際にはアルゴリズムが目標や解決策への方向性について悩むのを防ぎます。 インフォームドサーチは、より低いサーチコストで最適性が達成されるコストの点で有利であり得る。

情報に基づく検索戦略を実行することによってグラフ内で最適な経路コストを検索するために、最も有望なノードnが発見的関数h(n)に挿入される。 次に、関数は、ノードnからターゲットノードまで計算された近似パスコストである負でない実数を返します。

ここで、情報に基づいた技術の最も重要な部分は、問題についての追加の知識をアルゴリズムに伝えるのを容易にする発見的関数です。 その結果、さまざまな隣接ノードを介して目標への道を見つけるのに役立ちます。 ヒューリスティックな深さ優先探索、ヒューリスティックな幅優先探索、A *探索など、インフォームドサーチに基づくさまざまなアルゴリズムがあります。 ヒューリスティックな深さ優先探索を理解しましょう。

ヒューリスティックデプスファーストサーチ

以下に与えられる深さ優先探索方法と同様に、発見的深さ優先探索は経路を選択するが、他の経路を選択する前に選択された経路から全ての経路を横断する。 ただし、それはローカルで最良のパスを選択します。 最小のヒューリスティック値がフロンティアの優先順位である場合は、それが最良優先検索として知られています。

他のインフォームドサーチアルゴリズムは、最も低コストのファーストサーチとベストファーストサーチの概念を併合するA *サーチである。 この方法は、拡大されるべき経路を探索し選択する過程において、経路コストと発見的情報の両方を考慮する。 開始ノードからターゲットノードまでのフロンティアにある各パスに使用される推定総パスコスト。 したがって、同時に2つの関数を使用します。cost(p)は検出されたパスのコスト、h(p)は開始ノードからゴールノードへのパスコストの推定値です。

情報なし検索の定義

情報なし検索は情報付き検索とは異なり、問題定義を提供するだけで問題の解決策を見つけるためのステップはありません。 情報なし検索の主な目的は、ターゲット状態と非ターゲット状態を区別することであり、目標を発見して後継者を報告するまでは、パス内の目的地を完全に無視します。 この戦略はブラインド検索とも呼ばれます。

このカテゴリの下には、深さ優先探索、均一コスト検索、幅優先探索など、さまざまな検索アルゴリズムがあります。 深さ優先探索の助けを借りて、無情報検索の背後にある概念を理解しましょう。

深さ優先探索

深さ優先探索では、後入れ先出しスタックを使用してノードを追加および削除します。 一度に1つのノードだけが追加または削除され、スタックのフロンティアから最初に削除された要素がスタックに追加された最後の要素になります。 フロンティアでスタックを使用することにより、パスの検索は深さ優先の方法で進められる。 深さ優先探索を用いて最短で最適な経路が探索されるとき、それが所望の経路でなくても、隣接するノードによって作成された経路が最初に完成される。 次に、代替経路がバックトラッキングによって検索されます。

言い換えれば、アルゴリズムは各ノードで最初の選択肢を選択し、次に最初の選択肢からすべてのパスを通過するまで別の選択肢に戻ります。 これはまた、グラフに無限ループ(サイクル)が存在するために検索が停止しなくなる可能性があるという問題を引き起こします。

インフォームド検索とインフォームド検索の主な違い

  1. 前者の情報に基づく検索技術は解決策を見つけるために知識を使用します。 一方、後者の情報なし検索手法は知識を使用しません。 簡単に言えば、このソリューションについてこれ以上の情報はありません。
  2. インフォームド検索の効率は、インフォームド検索よりも優れています。
  3. 情報に基づく検索は、情報に基づく検索と比較して解決策についての手がかりがないため、より多くの時間とコストを消費します。
  4. 深さ優先探索、幅優先探索、および最低コスト優先探索は、情報のない探索の範疇に入るアルゴリズムである。 反対に、インフォームドサーチは、ヒューリスティックな深さ優先探索、ヒューリスティックな幅優先探索、A *検索などのアルゴリズムを網羅しています。

結論

情報に基づく検索は解決策に関する指示を提供しますが、情報に基づかない検索では解決策に関する示唆は与えられません。 これにより、アルゴリズムが実装されている場合に、情報のない検索がさらに長くなります。

Top