Loading article…
ベストファースト検索は、指定されたルールに従って選択された最も有望なノードを拡張することで グラフを探索する検索アルゴリズムのクラスです。
ジューディア・パールは、ベスト・ファースト探索を「一般的には、nの説明、目標の説明、その時点までの探索で収集された情報、そして最も重要な問題領域に関する追加知識に依存するヒューリスティック評価関数」によってノードnの見込みを推定するものと説明しました。[ 1] [2]
一部の著者は、「最良優先探索」という言葉を、パスの終点がソリューション（または目標）にどれだけ近いかを予測するヒューリスティックを用いた探索を指して使用しており、ソリューション（または目標）に近いと判断されたパスが最初に拡張されます。この特定のタイプの探索は、貪欲最良優先探索[2]または純粋なヒューリスティック探索と呼ばれます。[3]
拡張の現在の最適な候補を効率的に選択するには、通常、優先キューを使用します。
A * 検索アルゴリズムは、 B*と同様に、最良優先検索アルゴリズムの例です。最良優先アルゴリズムは、組み合わせ検索でのパス検索によく使用されます。A* も B* も、ゴールまでの推定距離に加えて開始からの距離も考慮するため、貪欲な最良優先検索ではありません。
貪欲なBeFS
貪欲アルゴリズムを使用して、親の最初の後継者を展開します。後継者が生成された後: [4]
- 後続のヒューリスティックが親よりも優れている場合、後続はキューの先頭に設定され (親はその後にすぐ再挿入されます)、ループが再開されます。
- それ以外の場合、後続処理はキューに挿入されます (ヒューリスティック値によって決定される場所)。この手順では、親の残りの後続処理 (存在する場合) が評価されます。
以下はこのアルゴリズムの擬似コードの例です。ここで、 queue は、ゴールからのヒューリスティックな距離に基づいてノードを順序付ける優先キューを表します。この実装は、訪問したノードを追跡するため、無向グラフに使用できます。パスを取得するように変更できます。
手順GBS(start, target)は次のとおりです。
開始を訪問済みとしてマークする
キューに開始を追加
キューが 空でないときは以下を実行します:
current_node ← ターゲットまでの距離が最小のキューの頂点
キューからcurrent_nodeを削除します
current_node の各隣接ノード n に対して、
次の操作を実行します。nが訪問済みでない場合は、
次の操作を実行します。nがターゲット
の場合は、 n
を返します。それ以外の場合は、次の操作を実行します。
n を訪問済みとしてマークする
キューにnを追加
返品失敗
参照
参考文献
- ^ Pearl, J. Heuristics: コンピュータ問題解決のためのインテリジェントな検索戦略。Addison-Wesley、1984年、p. 48。
- ^ ab ラッセル、スチュアート J. ;ノーヴィグ、ピーター。 (2021)。人工知能：現代的アプローチ（第4版）。ホーボーケン：ピアソン。pp. 73–74。ISBN 9780134610993. LCCN 20190474.
- ^ Korf, Richard E. (1999)。「人工知能検索アルゴリズム」。Atallah, Mikhail J. (編)。アルゴリズムと計算理論のハンドブック。CRC Press。ISBN 0849326494。
- ^ https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume28/coles07a-html/node11.html#modifiedbestfs EHC が失敗した場合の貪欲な最良優先探索、カーネギーメロン
外部リンク
- Wikibooks: 人工知能: 最良優先探索