14.4 ���H������

(defclass maze-node (node)
  ((pos :initarg :pos :accessor node-pos)))

(defun convert-to-string (n)
  (format nil "~s" n))

(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
          (make-instance 'maze-node
            :name (convert-to-string (incf i))
            :pos (list x y))
          res))))
    (reverse res)
    )
  )

(defmethod add-neighbor
    ((self node) n &key (test #'equal))
  (let ((ns (node-neighbors self)))
    (when (not (member n ns :test test))
      (setf (node-neighbors self) (cons n ns))
      (add-neighbor n self :test test)
      )
    ns))

(defun put-arc (graph
                name1 name2 &key (test #'equal))
  (add-neighbor (find-node graph name1)
                (find-node graph name2)
                ))

(defun init-maze ()
  (setq *maze-graph*
    (make-instance 'graph
      :nodes (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)))
      (put-arc *maze-graph*
               (convert-to-string n1)
               (convert-to-string n2))))
  *maze-graph*)

�������Cadd-neighbor���C�������m�[�h��������neighbors���o�^���������C �����������m�[�h��������neighbors�������o�^�����������s�������������D ���������C����������maze-test�����`�������s���������������������������D

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

<cl> (maze-test)
DEPTH-FIRST Search from 21 to 13:
  (21 22 23 24 19 20 15 14 9 8 7 12 13)
BREADTH-FIRST Search from 21 to 13:
  (21 22 17 16 11 12 13)
NIL

�} 3: ����������