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

2744557306

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

当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：

5 M& D1 \; w: f4 L! b# K1.function [total,maze]=search(i,j,maze,total);


2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
* a1 o+ c5 ], }+ [; t0 ~8 @9 A

: B! A" d8 C; z. R0 x: ]3.fx(1:4)=[0,1,-1,0];
; t3 x! g; J4 e) M# n' {  b

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


5.fy(1:4)=[1,0,0,-1];


2 d; t! _, l( n: W/ k0 m6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。

+ x, ]4 i2 j. |  `  ]2 d3 a
7 N. J( X7 a. ~8 E8 l# d8 a% v7 X/ c; [6 J7.for k=1:4
0 f7 O1 D: M( B0 b- y0 q* [0 _* Y
' O4 q# \' |- A  v5 t; t
' j/ f, \3 r. n5 U5 @& _# J  f8.开始一个循环，遍历四个可能的移动方向。
' f! h3 V, a( j0 D5 s& P, R* i( {
; f" _4 R; o( L8 X1 G) Z
* l7 [5 ~' Y4 `; q9 G9 k9.newi=i+fx(k);


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

9 [6 g% X7 t" I' j( e
) l- w: m& ^' P) g11.newj=j+fy(k);
* g( U: k5 c- b% }
: R) e( _" O: r+ N8 n4 [* ^
# C; s* \; C" ~12.根据当前位置(i, j)和移动方向计算新的列坐标newj。
: u; B/ u- M( ^& `
2 J3 X* X/ L) r& r
1 U- o: ~: `2 t4 f13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
$ V8 M; b  L! [% |1 f1 O
5 }+ Y1 M$ s! _& f' A
5 P% R# b3 `2 U* z/ f! p/ |& s3 s! W14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
4 Z; i( Y# C' ~; m8 Q% c
/ h' K( K) `5 W+ _, j/ V: f
15.maze(newi,newj)=3;
$ o. ^+ ~. k9 z  Y

# ?  Z% h# h  [( R, Y# i16.将迷宫中新的位置标记为3，表示已经走过。
6 S6 D& w% P" ?  k

17.if newi==8&newj==8
& j9 I9 i6 \2 a$ y+ h) k  O0 f, @) ~% Q

8 A  M+ L5 p% M& a) Z9 t18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。

- j) _7 f5 H4 |9 ]
4 r* |! c0 [% C: g19.total=total+1
% t6 |  d! h5 Q* }+ U
20.增加解的数量。
21.maze

4 V5 p" V/ a. y" g5 X2 o" |2 T  H22.显示当前的迷宫状态。
7 E# [3 c" \4 _$ ]4 H3 t23.else

24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);
1 ]9 e7 }( I8 N9 V  k0 C* A+ I
26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
- \( ?5 U, g4 |27.end
' g' M% A5 B$ Z: n6 B
28.结束if语句。
" l# m! T; s( G& p! w4 c$ Y29.end
  g; }* V* U; x6 L: g5 f
30.结束for循环。
# L! G" B; A' S31.maze(i,j)=2;

5 b" c3 m; ~& _9 X/ k3 K% ^32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
$ C% ]7 t( ^- i9 x0 X* L33.end

34.结束search函数。
1 r  e8 q  s! @3 T3 Z4 g35.clear all

36.清除工作区中的所有变量。
37.clc

38.清空命令窗口。
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
40.total=0;
3 |; s" a7 v" f2 e, A
41.初始化解的数量。
, k1 z3 X; K2 }) R$ S42.maze(1,1)=3;

43.将起始位置标记为3，表示已经走过。
& X! A% W+ p. r/ }1 k3 y44.[total,maze]=search(1,1,maze,total);
. n5 v% _9 r4 t3 t! Y
2 i& a. q7 K) C, i; M5 t& y45.调用search函数开始深度优先搜索。
. Q5 v' Y# W% v3 j; o
& ^5 K2 e7 L7 ^" T% \整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。
4 H9 Z# p: F  x$ W. P



. F( P% d$ u  O" x# Z