4.1 迷路問題の記述

Next: 4.2 積木問題の記述 Up: 4 状態空間探索による問題解決 Previous: 4 状態空間探索による問題解決

4.1 迷路問題の記述

問題空間を表現するためにまず，迷路に座標を設けます．図6のように場所に順に番号をふった形で迷路を表現してみます．

**図 6:** 迷路の番地表現
$\includegraphics[height=6.0cm]{/home/inaba/eps/lecture/fig/mazerepresent.eps}$

このような形の座標で迷路を表現する形として，いろいろ考えられますが，隣あった地点同士の隣接関係を辺として，辺のリストで表現すると次のようになります．


  (setq *maze-graph*
        '((1 2) (2 3) (3 4) (4 9) (9 14) (9 8)
          (8 7) (7 12) (12 13) (12 11) (11 6)
          (11 16) (14 15) (16 17) (17 22)
          (21 22) (22 23) (23 18) (23 24)
          (24 19) (19 20) (20 15) (15 10)
          (10 5) (20 25)))

図4での４つの点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月6日