早稲田大学 創造理工学研究科 経営システム工学専攻 2016年7月実施 知識情報処理 問題15

标签：

• Waseda-University
• Best-First-Search
• A-Star-Algorithm

Author

祭音Myyura

Description

初期状態を S、ゴール状態を G とし、辺の数字を移動コスト、ノードの括弧内の数字をヒューリスティック値 とする。

1. 最良優先探索により S から G へ至る経路を求め、オープンリストとクローズドリストの変化を示せ。
2. A* アルゴリズムにより S から G へ至る経路を求め、両リストの変化を示せ。
3. 深さ優先探索、幅優先探索、最良優先探索、A* のオープンリスト管理方法を、指定語句「キュー、スタック、ソート、スタートからある状態までのコストの推定値、ある状態からゴールまでのコストの推定値」をすべて用いて比較せよ。

Kai

同じ評価値の場合には「ヒューリスティック値が小さい状態、さらに同値ならアルファベット順」を優先するものとする。ゴールはオープンリストから取り出した時点で判定する。

[小問 1]

最良優先探索では、オープンリストを の昇順にソートする。表中の括弧内は である。

展開した状態	展開後のオープンリスト	クローズドリスト
S	B(3), A(5)	S
B	F(0), E(2), A(5)	S, B
F	E(2), A(5)	S, B, F
E	G(0), D(2), C(4), A(5)	S, B, F, E
G	D(2), C(4), A(5)	S, B, F, E, G

各状態を初めて生成した状態を親とすると、得られる経路は

であり、経路コストは

である。最良優先探索は だけで選ぶため、この経路は最短とは限らない。

[小問 2]

A* では

を評価値とする。ここで は S から までに判明している最小コストである。表中の括弧内は である。

展開した状態	展開後のオープンリスト	クローズドリスト
S	A(7), B(9)	S
A	B(7), C(7)	S, A
B	C(7), F(8), E(11)	S, A, B
C	E(7), F(8), D(10)	S, A, B, C
E	F(8), D(8), G(10)	S, A, B, C, E
F	D(8), G(10)	S, A, B, C, E, F
D	G(7)	S, A, B, C, E, F, D
G	-	S, A, B, C, E, F, D, G

更新された主要なコストは

したがって得られる経路は

で、経路コストは

なお、この問題では が D から G への実コスト を上回るため、ヒューリスティック関数は許容的ではない。したがって A* の一般的な最適性保証は直接には使えないが、この問題で得られたコスト7の経路は、全単純経路を比較しても最短である。

[小問 3]

探索法	オープンリストの管理
深さ優先探索	後から生成した状態を先に取り出すスタックを用いる。コストの推定値によるソートは行わない。
幅優先探索	先に生成した状態を先に取り出すキューを用いる。コストの推定値によるソートは行わない。
最良優先探索	ある状態からゴールまでのコストの推定値 が小さい順にオープンリストをソートする優先度付きキューを用いる。
A*	スタートからある状態までのコストの推定値 と、ある状態からゴールまでのコストの推定値 の和 が小さい順にソートする優先度付きキューを用いる。

深さ優先探索と幅優先探索は生成順序だけを使うのに対し、最良優先探索と A* はコスト推定値に基づいて探索順序を変える。A* は到達済みコストと残りコストの両方を考慮する点が最良優先探索と異なる。