3.1 頂点の座標空間

Next: 3.2 頂点間の距離とパスの長さ Up: 3 ヒューリスティックな探索法 Previous: 3 ヒューリスティックな探索法

3.1 頂点の座標空間

物理的な意味を考えやすくするために，それぞれの頂点に２次元の座標を設定し各頂点間の距離を計算で求めるという方法を考えます．図 3のような座標を各状態でもつと考えます．このようにすると，各頂点の位置が変わった場合でも隣接点との距離を変えるのは容易になります．ただ，探索の途中で辺の距離が必要になる度ごとに計算で距離を求めることになってしまいます．たとえば，以下のようにcoordinates属性に登録します．


(defun point (x y) (float-vector x y))

(defun init-coordinates-property nil
  (put 's 'coordinates (point  0 3))
  (put 'a 'coordinates (point  4 6))
  (put 'b 'coordinates (point  7 6))
  (put 'c 'coordinates (point 11 6))
  (put 'd 'coordinates (point  3 0))
  (put 'e 'coordinates (point  6 0))
  (put 'f 'coordinates (point 11 3)))

pointは座標点を与える関数です．以下で座標間の距離を求める関数が必要となるので，関連した関数群が下のようになっているとしておきます．

**図 3:** 各状態の位置がわかっている場合
$\includegraphics[width=8cm]{/home/inaba/eps/lecture/fig/possearchspace.eps}$

generated through LaTeX2HTML. M.Inaba 平成18年5月6日