Next: 5.3.2 積み木の問題解決
Up: 5.3 探索手続き
Previous: 5.3 探索手続き
図2での４つの点A,B,C,Dはそれぞれ，1, 13, 21, 25という
座標になる．
> (setq a 1 b 13 c 21 d 25)
25
> (depth-first *maze-graph* a d)
(1 2 3 4 9 8 7 12 11 16 17 22 23 24 19 20 25)
> (breadth-first *maze-graph* a d)
(1 2 3 4 9 14 15 20 25)
> (depth-first *maze-graph* d a)
(25 20 15 14 9 4 3 2 1)
> (breadth-first *maze-graph* d a)
(25 20 15 14 9 4 3 2 1)
> (depth-first *maze-graph* a c)
(1 2 3 4 9 8 7 12 11 16 17 22 21)
> (breadth-first *maze-graph* a c)
(1 2 3 4 9 8 7 12 11 16 17 22 21)
> (depth-first *maze-graph* c d)
(21 22 23 24 19 20 25)
> (breadth-first *maze-graph* c d)
(21 22 23 24 19 20 25)
という具合に，A点からD点まで縦型探索した場合と，横型探索した場合ではパス
が異なってくる．横型の方が短いパスを返している．また，逆にD点からA点へ戻
るという場合には，縦型でも横型でも同じパスを返していることが分かる．数に
よるこのような番地の付け方では物理的な位置情報を付加することが難しいため，
それぞれをシンボルにしてその属性値に座標を入れてみる．
(setq *maze-graph2*
'((p1 p2) (p2 p3) (p3 p4) (p4 p9) (p9 p14) (p9 p8)
(p8 p7) (p7 p12) (p12 p13) (p12 p11) (p11 p6)
(p11 p16) (p14 p15) (p16 p17) (p17 p22)
(p21 p22) (p22 p23) (p23 p18) (p23 p24)
(p24 p19) (p19 p20) (p20 p15) (p15 p10)
(p10 p5) (p20 p25)))
(defun maze-init nil
(let (p (i 1))
(setq *maze-points* nil)
(dotimes (x 5)
(dotimes (y 5)
(setq p (intern (concat "p" (number-to-string i))))
(setf (get p 'coordinates) (point x y))
(setq *maze-points* (cons p *maze-points*))
(setq i (1+ i))))
(dolist
(x *maze-points*)
(dolist
(y *maze-points*)
(put x y
(distance (get x 'coordinates)
(get y 'coordinates))))))
)
このようにすると，評価関数としてこのcoordinatesを用いる，shorterpや
closerpなどを用いることで，分岐限定法，山登り，最良優先法などが使える
ようになる．
ここで，internという関数は，文字列からシンボルを作るための関数である．
> (intern "inaba")
inaba
> (get 'p1 'coordinates)
(0.0 0.0)
> (get 'p13 'coordinates)
(2.0 2.0)
> (get 'p25 'coordinates)
(4.0 4.0)
> (get 'p1 'p25)
4.47213595499958
> (get 'p1 'p13)
2.449489742783178
> (get 'p1 'p1)
0.0
> (get 'p1 'p21)
4.0
> (depth-first *maze-graph2* 'p1 'p25)
(p1 p2 p3 p4 p9 p8 p7 p12 p11 p16 p17
p22 p23 p24 p19 p20 p25)
> (breadth-first *maze-graph2* 'p1 'p25)
(p1 p2 p3 p4 p9 p14 p15 p20 p25)
> (depth-first *maze-graph2* 'p25 'p1)
(p25 p20 p19 p24 p23 p22 p17 p16 p11
p12 p7 p8 p9 p4 p3 p2 p1)
> (breadth-first *maze-graph2* 'p25 'p1)
(p25 p20 p15 p14 p9 p4 p3 p2 p1)
> (depth-first *maze-graph2* 'p1 'p21)
(p1 p2 p3 p4 p9 p8 p7 p12 p11 p16 p17 p22 p21)
> (hill-climb *maze-graph2* 'p1 'p25)
(p1 p2 p3 p4 p9 p14 p15 p20 p25)
> (branch-and-bound *maze-graph2* 'p1 'p25)
(p1 p2 p3 p4 p9 p14 p15 p20 p25)
> (best-first *maze-graph2* 'p1 'p25)
(p1 p2 p3 p4 p9 p14 p15 p20 p25)
> (best-first *maze-graph2* 'p25 'p1)
(p25 p20 p15 p14 p9 p4 p3 p2 p1)
> (hill-climb *maze-graph2* 'p25 'p1)
(p25 p20 p15 p14 p9 p4 p3 p2 p1)
> (branch-and-bound *maze-graph2* 'p25 'p1)
(p25 p20 p15 p14 p9 p4 p3 p2 p1)
generated through LaTeX2HTML. M.Inaba 平成18年5月7日