.


:




:

































 

 

 

 





, . , , . . , . , , . . , :

#####

#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.)





:


: 2015-10-01; !; : 460 |


:

:

, .
==> ...

811 - | 734 -


© 2015-2024 lektsii.org - -

: 0.066 .