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

3.1 頂点の座標空間

物理的な意味を考えやすくするために,それぞれの頂点に2次元の座標 を設定し各頂点間の距離を計算で求めるという方法を考えます.図 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日