9.1 頂点の座標空間

Next: 9.2 頂点間の距離とパスの長さ Up: 9 見込み探索 Previous: 9 見込み探索

9.1 頂点の座標空間

物理的な意味を考えやすくするために，それぞれの頂点に２次元の座標を設定し各頂点間の距離を計算で求めるという方法を考える．図 9のような座標を各状態でもつと考える．このようにすると，各頂点の位置が変わった場合でも隣接点との距離を変えるのは容易になる．ただ，探索の途中で辺の距離が必要になる度ごとに計算で距離を求めることになる．たとえば，以下のように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は座標点を与える関数である．以下で座標間の距離を求める関数が必要となるので，関連した関数群が下のようになっているとしておく．

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

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