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

标签：

Author

祭音Myyura

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

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

在给定状态图中，初始状态为 S，目标状态为 G；边上的数字表示移动成本，节点括号内的数字表示启发式值 $h$ 。各节点的启发式值为

h(S)=5,\ h(A)=5,\ h(B)=3,\ h(C)=4,\ h(D)=2,\ h(E)=2,\ h(F)=0,\ h(G)=0.

图中的边及其移动成本为

\begin{gathered} S\!-\!A:2,\quad S\!-\!B:6,\quad A\!-\!B:2,\quad A\!-\!C:1,\\ B\!-\!F:4,\quad B\!-\!E:5,\quad C\!-\!E:2,\quad C\!-\!D:5,\\ D\!-\!E:1,\quad D\!-\!G:1,\quad E\!-\!G:5. \end{gathered}

使用最佳优先搜索求出从 S 到 G 的路径，并展示开放列表与关闭列表的逐步变化。
使用 A* 算法求出从 S 到 G 的路径，并同样展示两个列表的逐步变化。
比较深度优先搜索、广度优先搜索、最佳优先搜索和 A* 管理开放列表的方法。说明中必须全部使用以下指定词语：“队列”“栈”“排序”“从起点到某状态的成本估计值”“从某状态到目标的成本估计值”。

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

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

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

\boxed{\mathrm{S}\to\mathrm{B}\to\mathrm{E}\to\mathrm{G}}

であり、経路コストは

6+5+5=\boxed{16}

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

A* では

f(n)=g(n)+h(n)

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

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

\begin{aligned} g(B)&:6\to2+2=4,\\ g(E)&:4+5=9\to2+1+2=5,\\ g(D)&:2+1+5=8\to2+1+2+1=6,\\ g(G)&:5+5=10\to6+1=7. \end{aligned}

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

\boxed{ \mathrm{S}\to\mathrm{A}\to\mathrm{C}\to\mathrm{E} \to\mathrm{D}\to\mathrm{G} }

で、経路コストは

2+1+2+1+1=\boxed{7}.

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

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

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