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

2744557306

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题

" o: Y. L: x$ _/ Y& p/ d; l. ]0 n当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
# z, p8 b# A5 \. v
! x& U9 r) M! G% t1.function [total,maze]=search(i,j,maze,total);


, L  _1 A8 y) `/ A* X" c2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
, V# O7 X. w7 Y" A1 f$ `
' W4 K: @0 }  \, J" b
3.fx(1:4)=[0,1,-1,0];
% n* ]' W; y7 x$ d! Z1 O
6 u1 q% x1 X! @/ v/ P
4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
9 S( T, b' t- n9 h+ J5 B

8 ^* u+ z& U) O% P4 S1 y" Q. i* ]5.fy(1:4)=[1,0,0,-1];
' j! V" R; ^; \3 W

) n# ^" Y/ m  P1 ]  ^1 \, V6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
+ v3 i6 O: g: `! l7 [; V: \
9 [, O: X( m3 R, v# \
5 s/ Y2 a0 a# c! V) n; P2 H0 B5 g7.for k=1:4

9 o2 {) e, q( m5 k& I" L& h7 p
$ g* |* ~4 o2 h4 l8.开始一个循环，遍历四个可能的移动方向。

2 O" R3 N1 u% Y
9.newi=i+fx(k);


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


. l6 F- }( U' `* D' H* d11.newj=j+fy(k);

" Q- r5 \3 i6 n
- J* D+ t4 Q/ D4 U# W4 x12.根据当前位置(i, j)和移动方向计算新的列坐标newj。

& z5 X3 G  @2 D, J9 L. N
13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0


2 t7 H+ N+ ]- [! ?' v14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。


2 c# H8 r1 t; @6 D15.maze(newi,newj)=3;
6 X: s% n6 y5 r/ K1 L

16.将迷宫中新的位置标记为3，表示已经走过。


17.if newi==8&newj==8
% o+ U2 _3 |9 ?  Z* f) U8 H
* d8 ]5 l3 c) E4 F; q
" Y* ~$ {8 u* `- ^9 Q9 w& V% V18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。


* P' e! U- k1 c4 y" a% L) @% E19.total=total+1

* [4 b* x0 i% I  h0 |% O9 @20.增加解的数量。
21.maze
6 e+ O, x! V; ^( M
22.显示当前的迷宫状态。
0 r7 `# t4 s7 t' X% L8 T8 w1 X23.else

) [, A# l) g9 m% `6 h. ~: ^24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);

26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
6 M# ^( G3 O: h6 }4 b+ J27.end

28.结束if语句。
9 ~# E; B8 M3 {1 s29.end

' W$ b! Z" k9 }  U2 X% y& V! Q30.结束for循环。
2 c- F+ X9 p! K+ s4 r31.maze(i,j)=2;

- U6 n! A# a3 d7 c$ @, Y: F. t6 g% R32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
$ T0 D* v4 [/ v$ o33.end
' K/ ~" V. V8 w* A7 Y
34.结束search函数。
35.clear all
% R" x- C9 J6 Y
) U, i3 b$ K, d36.清除工作区中的所有变量。
37.clc

1 s9 q% F- z6 Y! c* V7 }  r; [9 `38.清空命令窗口。
; B$ d- j5 x1 P9 s( e  C39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
8 o. N( D% F" j: q; K4 `40.total=0;
- D. A% y: N/ }8 T0 R! O1 s& g
41.初始化解的数量。
# W& J% A9 i+ t5 q, G42.maze(1,1)=3;

2 ~7 B8 R+ k5 }& F43.将起始位置标记为3，表示已经走过。
9 h% r5 [1 m0 }6 U; x44.[total,maze]=search(1,1,maze,total);

- I" q; _0 ^' k# c45.调用search函数开始深度优先搜索。
+ }7 ^4 Z, j% C. J8 u4 x& q
) Z# b( C7 v- ]5 u; P, q整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。

8 O6 I5 _0 u! B4 m! B  P
0 W7 y- m& t# [) g9 O6 S+ @( t
# A; r# v' z" |  w