最良優先探索
Best-First Search
最良優先探索アルゴリズム
探索木の最先端のノードに対して基本操作を1回適用して到達できる全て のノードの中からh'値の最も小さいものを選択する．
L ← <初期ノードリスト> ;
while
L ≠[ ]
do
begin
n ← <Lの中のh'値が最小のノード>;
if
P(n)
then exit
(<成功:初期ノードからn までの経路>);
<Lからnを取り除く>;
<nの全ての子供を求め，Lに追加し，各子供に初期ノードからの経路を対応付ける>;
end
ルーマニアの地図
特徴
選択した経路のコストの見積もりが悪くなると，まったく別の経路にジャ ンプ出来る(よって山登り法よりは柔軟)．
山登り法より多くの記憶容量を必要とする．
完全性: no
最適性: no
...Return
講義の詳細
...Return