, . , , . . , . , , . . , :
#####
#O#X#
# #
#####
, 'O' ; , 'X' . '#' . , , . :
, :
, :
- ;
- ;
- .
, , .
, ( ), . (depth-firth search). , (s) (n), . n n1. n1 , n1. n , . . , , :
######
## #
#O #X#
## #
######
, , : , , , . . . . :
######
## #
# O#X#
## #
######
. :
######
##O #
# #X#
## #
######
.
, (breadth-first search) k, k+1. . :
######
## #
# O#X#
## #
######
. :
|
|
######
##O #
# #X#
## #
######
, . :
######
## #
# #X#
##O #
######
, . :
######
## O #
# #X#
## #
######
. . , k , , - , k+1.
. :
1. , .
2. , , .
3. . ( ).
4. .
5. 1.
tree-search :
states ;
is-goal is-goal . , is-goal NIL. , NIL.
expand-state - . , , . ( , , ).
combine-states combine-states . . expand-state . . , , , .
is-goal, expand-state, combine-states , .
.
(defun tree-search
(states is-goal expand-state combine-states)
(cond ((null states) nil)
((funcall is-goal (first states))
(first states))
(t (tree-search
(funcall combine-states (rest states)
(funcall expand-state (first states)))
is-goal
expand-state
combine-states))))
, states, , is-goal NIL. expand-state , . combine-states . .
tree-search .
depth-first-search :
(defun depth-first-search
(state is-goal expand-state tree-searcher)
(funcall tree-searcher
(list state) is-goal expand-state
#'(lambda (old-states new-states)
(append new-states old-states)))
)
depth-first-search , state, , . expand-state . tree-searcher .
|
|
. : , . , .
(defstruct maze
start-row; .
start-column; .
goal-row; .
goal-column; .
grid;
; NIL,
; , NIL - .
; - , - .
; .
;, ,
; - (1, 2).
)
. . , , .
maze-print : :
(defun maze-print (maze positions)
...
)
:
- '#' ;
- 'O' ;
- 'X' .
. , . positions ( ). '.'.
maze-is-goal NIL, , . ., .
(defun maze-is-goal (maze-state)
(let ((maze (second maze-state)))
(and
(= (maze-start-row maze) (maze-goal-row maze))
(= (maze-start-column maze)
(maze-goal-column maze))))
)
maze-expand , . , , , .
(defun maze-expand (maze-state)
(let ((maze (second maze-state)))
(labels ((is-empty (row column)
; -NIL
; (row column)
(not (aref (maze-grid maze) row column)))
(new-maze-if-legal (row column)
; ,
; , maze-state
; ,
; NIL,
(and (array-in-bounds-p (maze-grid maze)
row column)
(is-empty row column)
(not (member (list row column)
(first maze-state)
:test #'equal))
(list
;
;
(cons (list row column)
(first maze-state))
; ,
;
(make-maze:start-row row
:start-column column
:goal-row
(maze-goal-row maze)
:goal-column
(maze-goal-column maze)
:grid
(maze-grid maze))))))
(let ((row (maze-start-row maze))
(column (maze-start-column maze)))
(remove nil
; .
; NIL,
;
(mapcar #'new-maze-if-legal
(list (1- row)
(1+ row)
row
row)
(list column
column
(1- column)
(1+ column)))))))
)
: labels let, , . :
(labels ((factorial (n)
(if (= n 0) 1
(* n (factorial (- n 1))))))
(factorial 3))
maze-solve , . , . :
|
|
(defun maze-solve
(maze search-strategy tree-searcher)
(format t Attempting to solve the following
maze:~%)
(maze-print maze nil)
(terpri)
(let ((solution (funcall search-strategy
(list
(list
(list (maze-start-row maze)
(maze-start-column
maze))) maze)
#'maze-is-goal
#'maze-expand
tree-searcher)))
(if solution
(progn
(format t Solution:~%)
(maze-print (second solution)
(first solution))
)
(format t No solution exists.~%)) solution))
.
.
>(maze-solve complex-maze #'breadth-first-search
#'iterative-tree-search)
Attempting to solve the following maze:
##########
# # #
## # ### #
# # # #
# ## # #
# ## #####
# # 0
# ## ###
# # ## #
X ########
Solution:
##########
# # #
## # ### #
# # # #
# ## # #
# ## #####
# #.......
#...## ###
#.# ## #
..########
(((9 0) (9 1) (8 1) (7 1) (7 2) (7 3) (6 3) (6 4)
(6 5) (6 6) (6 7) (6 8) (6 9))
#S(MAZE START-ROW 9 START-COLUMN 0 GOAL-ROW 9
GOAL-COLUMN 0 GRID
#2A((T T T T T T T T T T)
(T NIL NIL T NIL NIL NIL NIL NIL T)
(T T NIL T NIL T T T NIL T)
(T NIL NIL NIL NIL T NIL T NIL T)
(T NIL T T NIL T NIL NIL NIL T)
(T NIL T T NIL T T T T T)
(T NIL T NIL NIL NIL NIL NIL NIL NIL)
(T NIL NIL NIL T T NIL T T T)
(T NIL T NIL T T NIL NIL NIL T)
(NIL NIL T T T T T T T T))))
, :
(defconstant simple-maze
(make-maze:start-row 0
:start-column 0
:goal-row 2
:goal-column 2
:grid #2A((nil nil t)
(nil t t)
(nil nil nil)))
A very simple maze.)
(defconstant complex-maze
(make-maze:start-row 6
:start-column 9
:goal-row 9
:goal-column 0
:grid #2A(
(t t t t t t t t t t)
(t nil nil t nil nil nil nil nil t)
(t t nil t nil t t t nil t)
(t nil nil nil nil t nil t nil t)
(t nil t t nil t nil nil nil t)
(t nil t t nil t t t t t)
(t nil t nil nil nil nil nil nil nil)
(t nil nil nil t t nil t t t)
(t nil t nil t t nil nil nil t)
(nil nil t t t t t t t t)))
A more complex maze.)