14.3 縦型，横型探索

Next: 14.4 迷路の問題 Up: 14 探索プログラムの実現 Previous: 14.2 探索木の生成

14.3 縦型，横型探索

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


(defmethod depth-first
    ((self graph) 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 (depth-first self
                   start goal
                   (append
                    (new-paths (new-nodes path) path)
                    (rest path-queue))
                   ))))

横型探索は以下のようになります．


(defmethod breadth-first
    ((self graph) 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 (breadth-first self
                     start goal
                     (append
                      (rest path-queue)
                      (new-paths (new-nodes path) path))
                     ))))

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


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

実行例は以下のようになります．


<cl> (find-route *graph* "s" "f" 'depth-first)
DEPTH-FIRST Search from s to f:
  (s a b e f)

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


<cl> (find-route *graph* "s" "f" 'breadth-first)
BREADTH-FIRST Search from s to f:
  (s d e f)
NIL

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

**図 2:** 迷路の例
$\includegraphics[width=4.5cm]{/home/inaba/eps/lecture/fig/maze.eps}$ $\includegraphics[height=4.5cm]{/home/inaba/eps/lecture/fig/mazerepresent.eps}$

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