next up previous
Next: 18 積み木の問題 Up: ソフトウェア第三 講義資料 クロージャ,スコープ,遅延評価,オブジェクト,立体モデル Previous: 16.3 縦型,横型探索

17 迷路の問題

迷路の問題は,ノードクラスのサブクラスに迷路用ノードの クラスmaze-nodeを作ってみる.

(defclass maze-node
  :super node
  :slots
  (pos))
;;;
(defmethod maze-node
  (:init (&rest args &key ((:pos p)) &allow-other-keys)
         (send-super-lexpr :init args)
         (setq pos p)
         self)
  )

(defmethod maze-node
  (:pos (&optional p)
        (if p (setq pos p))
        pos)
  ;;
  (:distance (n)
             (distance pos (send n :pos)))
  ;;
  (:prin1 (strm)
          (send-super :prin1 strm 
                      (format nil ":pos ~A" pos))
          )
  )
maze-nodeは,2次元の場所をスロットとして持つ. ノードとノードの間の距離を:distanceで計算することが できる.

(defun init-maze-nodes (x-max y-max)
  (let ((res nil) (i 0))
    (do
     ((y 1 (1+ y)))
     ((> y y-max))
     (do
      ((x 1 (1+ x)))
      ((> x x-max))
      (setq res
            (cons
             (instance maze-node :init
                       :name (string (incf i))
                       :pos (float-vector x y))
             res))))
    (reverse res)
    )
  )


(defmethod node
  (:add-neighbor
   (n &key (test #'equal))
   (when (not (member n neighbors :test test))
         (send self :neighbors (cons n neighbors))
         (send n :add-neighbor self :test test)
         )
   neighbors)
  )
隣接関係にあるノード間には,互いにneighborsスロットに 相手ノードをリストにして蓄えてゆくためのメソッドが :add-neighborである.


(defun init-maze ()
  (setq *maze-graph*
    (instance graph
       :init (init-maze-nodes 5 5)))
  (dolist (path '((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)))
    (let ((n1 (car path))
          (n2 (cadr path)))
      (send (send *maze-graph* :find-node (string n1))
      :add-neighbor
            (send *maze-graph* :find-node (string n2)))))
  *maze-graph*)
たとえば,次のようにmaze-testを定義して実行すると以下のようになる.

(defun maze-test nil
  (init-maze)
  (setq dp (send *maze-graph* :find-route
         "21" "13" :depth-first))
  (setq bp (send *maze-graph* :find-route
         "21" "13" :breadth-first))
  nil)


eus$ (maze-test)
route length from 21 to 13 is 13 in :depth-first method.
  route path is (21 22 23 24 19 20 15 14 9 8 7 12 13).
route length from 21 to 13 is 7 in :breadth-first method.
  route path is (21 22 17 16 11 12 13).
nil


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