深度优先搜索解决迷宫难题

2744557306

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
3 _# j/ r0 Y8 y- c$ b% g
3 }$ ]4 U! I% W) l& t当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：

1.function [total,maze]=search(i,j,maze,total);

8 N7 x0 |: ?* i
! N$ J+ x* h8 l6 k/ T( V/ |2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
* Y" v1 P' {3 X- B9 n! k/ c- I
4 {6 [3 ]# e5 a# B6 D( {
7 z- [6 E0 T* ~/ m1 q& D# k3.fx(1:4)=[0,1,-1,0];
6 O5 h& ~' ?: \9 P1 K. R. b& v  V

4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。

, p# |3 R  y, Y* y- w
& G# o$ o0 R# V7 V2 F" {# I5.fy(1:4)=[1,0,0,-1];


6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。


7.for k=1:4
% R9 C6 {  P. X6 b' I/ o

3 V+ h0 q# Q7 M" l8.开始一个循环，遍历四个可能的移动方向。
, a9 u+ N+ R! O( Y8 X9 C0 N0 \

9.newi=i+fx(k);
* `6 A" @+ y. V6 }; ^8 F

+ i4 q, }6 `+ [( X1 J10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
/ @" w7 X! Y2 Z$ N7 r
3 P  [6 g) _$ c. D$ G
3 p( j" N6 h' ?& d5 _2 i11.newj=j+fy(k);
4 T/ H) Z7 v' _' c$ k# V

12.根据当前位置(i, j)和移动方向计算新的列坐标newj。


7 f2 l6 ]6 e& ]7 E, J5 h* U/ N13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
9 y2 @5 J6 p. M! Q" q* i
# U; A6 [1 b; u  m
6 j5 U4 W2 \; w! b7 U0 Y6 m14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。


7 a5 K2 |' y2 Q: [15.maze(newi,newj)=3;
* e2 `3 I( g0 ]
; M8 @3 i8 j, e" \% j
16.将迷宫中新的位置标记为3，表示已经走过。


& k+ m1 u& O3 K1 A, k$ f17.if newi==8&newj==8
+ K- D6 i7 f2 T, U6 y( v
! X& @2 L4 F0 w9 j+ W
18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。
/ C# |3 T0 s# |# L9 I4 p, @* X
  X1 D+ |! q7 j& _  G) {( R
" a  a* Z1 n. h3 ^19.total=total+1

4 X$ _0 g2 L7 c7 z1 {# U, T% J20.增加解的数量。
21.maze
( Q, u; `- A' i. u6 N- n( x
- T, U6 @6 y) }# ~3 [3 D3 O22.显示当前的迷宫状态。
23.else

24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);
& A. E( \; H" I1 w: W3 d* P
! b" c4 k) y0 C5 X5 I  u- I26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
27.end
" Q0 M9 j8 \. O
3 M9 h) ?2 Z% i, F% \! E28.结束if语句。
5 R" N3 A  J0 I) }" W29.end

$ G/ a5 w* a/ p$ H+ g5 ]2 W30.结束for循环。
31.maze(i,j)=2;
! X) d7 r2 n. ~; L6 p' V# W
32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
2 P: Y( m' |. h33.end
# ~, b% k) m8 r4 l6 o
# R4 G: Q+ y) A0 n0 H34.结束search函数。
8 j2 i! l" n" b0 c5 z# ]  q35.clear all
' O# E/ Y2 F% P+ Z2 C" }- R' d
2 \- N" A% Y3 `- Y8 ~' y+ ^2 X36.清除工作区中的所有变量。
37.clc
- G+ H) i' r' i' H# _
38.清空命令窗口。
) |( L3 V. w& e, s/ K8 p39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
: m' U: n9 h$ Q$ k* X40.total=0;
4 i5 _% A0 w% M/ l
41.初始化解的数量。
7 I: \* ]$ j& o* Q42.maze(1,1)=3;

43.将起始位置标记为3，表示已经走过。
: ?' L9 H" [, u4 K: W3 M5 R44.[total,maze]=search(1,1,maze,total);
" C6 j" O7 G* O3 X0 W% J
45.调用search函数开始深度优先搜索。
% _: O1 q7 t& W
8 i' V% f+ I7 T4 }$ t* n整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。




; \/ |" V/ k7 |: l9 X

' Z( a. F, W3 B