【動画講座】CS 188 A* Search and Heuristics

動画リンク

https://www.youtube.com/watch?v=Mlwrx7hbKPs

画像

内容

ヒューリスティック

ヒューリスティックは各問題ごとの探索方針を教えてくれる関数。
パックマンだとユークリッド距離。

これがあることで、より高速に近似解を求めることができる。

A*は、Uniform Cost SearchとGreedy Searchを同時に使う探索アルゴリズム。

関数$g(v), h(v)$を使う。

$f(v)=g(v) + h(v)$のようになる。
$g$は、スタートから$v$までのコストを返す関数。
そして、$h(v)$は、頂点$v$からゴールまでのおよそのコストを返す。

$h$はおよそであるということが大事
(近似ですよ)

最適性

A*は、最適である場合と最適でない場合がある。

これは、Optimistic楽観的に最適であると示せるか、悲観的に準最適解が求まるか?
の違いである。

Optimisticの楽観的な条件は

$0{\leq}h(v){\leq}h^*(v)$

が成り立つと、必ず最適解が求まる。

$h^*$関数は、ゴールまでの正しい解である。
つまり、ゴールまでの正しい解よりも多くコストを見積もらず、小さめにコストを設定すれば
必ず正しい解が示せる。

これは証明で成り立つ。再帰的な証明である(画像参照)

直感的には

基本的には$g$で動き、そこからのゴールまでのコストよりも小さいヒューリスティックなので信用しても
問題はない、ゴールにつくまでにより良い解が出てくる、という証明。