Next: 3.4 山登り法(hill-climb search)
Up: 3 ヒューリスティックな探索法
Previous: 3.2 頂点間の距離とパスの長さ
最終目標点までにかかりそうであるコストの見積りを行なう関数をヒューリス
ティック関数といいます．たとえば，現在の頂点から目標頂点までの直線距離
(straight-distance)などをそのまま使うことが考えられます．
> (straight-distance 'a 'f)
7.211102550927978
> (straight-distance 'd 'f)
8.18535277187245
たとえば，sからaまたは，dへ進む際に，aからfの方がdからfよりも
直線距離で近いので，aへ行ってみようというような判断に使うわけです．
> (straight-distance 's 'a)
4.358898943540674
> (straight-distance 's 'd)
3.4641016151377544
しかし，sからaまでとsからdまでの距離はaの方が長い．
どうしたらいいか．いろいろな判断方法が考えられることがわかります．
最終ゴールをtarget-nodeとして，ふたつのパスpath-1, path-2がtarget-node
に対してどちらの方がより有望かを調べる関数として，closerpという関数を
考えると以下のようになります．ただし，pathはリストで，先頭の要素に入っ
ているのが現在の探索頂点になります．
(defun closerp (path-1 path-2 target-node)
(< (straight-distance (first path-1) target-node)
(straight-distance (first path-2) target-node)))
closerpは以下のように最終ゴールまでの距離の予測を
行なって，どちらのパスが近そうかということを調べます．
> (closerp '(a s) '(d s) 'f)
t
> (shorterp '(a s) '(d s))
nil
このように，(a s)というパスと(d s)というパスをcloserp, shorterpで比較
すると，ゴールまでは(a s)の方が近そうですが，パスは長くなってしまうと
いうことがわかります．
ヒューリステック関数を使う探索として，山登り法，最良優先探索法が
あります．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日