Next: 9.4 山登り法(hill-climb search)
Up: 9 見込み探索
Previous: 9.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月7日