A*探索
A*探索アルゴリズム
A*探索は最良優先探索と1点だけ異なる．それは，次のノードを選択する ときに，h'(n)を用いるのではなく，それにg(n)を加えた
f'(n) = g(n) + h'(n)
を用いることである．わずかな違いだが，もしも
ヒュー リスティック関数h'が
許容的
で あるなら，A*探索アルゴリズムの最適性が保証される
．(最適性に関 する証明は講義で話します)
L ← <初期ノードリスト> ;
while
L ≠[ ]
do
begin
n ←<Lの中で g(n)+h'(n)が最小のノード>;
if
P(n)
then exit
(<成功:初期ノードからn までの経路>);
<Lからnを取り除く>;
<nの全ての子供を求め，Lに追加し，各子供に初期ノードからの経路を対応付ける>;
end
ルーマニアの地図
特徴
完全性: yes
最適性: yes
空間計算量が大きい
A*探索の効率について
8パズルの例
...Return
講義の詳細
...Return
...Return