16.3 縦型，横型探索

Next: 17 迷路の問題 Up: 16 探索プログラム例 Previous: 16.2 探索木の生成

16.3 縦型，横型探索

縦型探索は以下のように定義できる．


(defmethod graph
  (:depth-first
   (start goal &optional (path-queue (list (list start)))
          &aux (path (first path-queue)))
   (cond
    ((null path-queue) nil)
    ((eq goal (first path)) (reverse path))
    (t (send self :depth-first
             start goal
             (append
              (new-paths (new-nodes path) path)
              (rest path-queue))
             ))))
  )

横型探索は以下のようになる．


(defmethod graph
  (:breadth-first
   (start goal &optional (path-queue (list (list start)))
          &aux (path (first path-queue)))
   (cond
    ((null path-queue) nil)
    ((eq goal (first path)) (reverse path))
    (t (send self :breadth-first
             start goal
             (append
              (rest path-queue)
              (new-paths (new-nodes path) path))
             ))))
  ;;
  )

探索経路を表示し，パスを返すメソッドを:find-routeとして graphに追加する．


(defmethod graph
  (:find-route
   (s f &optional (method :depth-first))
   (let ((route (send self method
                      (send self :find-node s)
                      (send self :find-node f))))
     (format t "route length from ~A to ~A is ~A in ~A method.~%"
             s f (length route) method)
     (format t "  route path is ~A.~%"
             (mapcar #'(lambda (n) (send n :name)) route))
     route))
  )

実行例は以下のようになる．


eus$ (send *graph* :find-route "s" "f" :depth-first)
route length from s to f is 5 in :depth-first method.
  route path is (s a b e f).
(#<node #X104e5600 "s" >
 #<node #X104e596c "a" >
 #<node #X104e61ac "b" >
 #<node #X104e74cc "e" >
 #<node #X104e7c88 "f" >)

横型探索の実行例も同様に以下のようになる．


eus$ (send *graph* :find-route "s" "f" :breadth-first)
route length from s to f is 4 in :breadth-first method.
  route path is (s d e f).
(#<node #X104e5600 "s" >
 #<node #X104e72f8 "d" >
 #<node #X104e74cc "e" >
 #<node #X104e7c88 "f" >)

縦型と，横型で得られるパスが違うことがわかる．ここで引数としてメソッド名を渡すことで探索の方法を選ぶことができる点が特徴です．このようにメソッド名を引数で渡すと手続きを引数にとるのと同じことになる．オブジェクト指向の応用によるプログラミングでは，既存のクラスを継承して，応用問題用のクラスを定義することでなされてゆく．

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