广度优先搜索 找到迷宫中的最短路径

2744557306

clear all
, s, j1 S0 C. y  j, g* V3 Oclc
maze=[0,0,0,0,0,0,0,0;
      0,1,1,1,1,0,1,0;
+ C, K7 `/ ?4 k1 Q& b5 H      0,0,0,0,1,0,1,0;
8 d6 P. c7 Q+ _      0,1,0,0,0,0,1,0;
      0,1,0,1,1,0,1,0;
9 G+ _6 x$ f1 O" Q      0,1,0,0,0,0,1,1;
      0,1,0,0,1,0,0,0;
& a" n, O- h6 v: y2 r/ U( j9 F      0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
) v/ H+ g. I" dfx(1:4)=[1,-1,0,0];
fy(1:4)=[0,0,-1,1];
sq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);
qh=0;%队头指针
- o2 ~7 r1 r5 {; Aqe=1;%队尾指针
; N- H1 g4 e' p. ^1 p+ Q$ ?maze(1,1)=-1;
4 |4 b% e. S% [" f, Y%第一个元素入队
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;
- j* G) `: }& H4 c& n
) Q6 |3 @3 T8 B9 zwhile qh-qe~=0
qh=qh+1;
bb=0;
9 `# q3 v, k4 u; h, x$ |9 a) [for k=1:4
6 v4 P1 n5 X* ^4 @# K9 `4 ji=sq.x(qh)+fx(k);
j=sq.y(qh)+fy(k);
8 W1 W9 N9 G; q+ b5 p0 yif check(i,j,maze)==1
  Z2 D  y; M  W) G+ mqe=qe+1;%入队
sq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
maze(i,j)=-1;

if i==8&j==8%如果为图最后一个点
  I$ q2 f% K0 O  p- a1 ?while qe~=0
sq.x(qe)
3 a  o7 q- V/ }sq.y(qe)   
0 F/ Q/ L1 H" T7 r: dqe=sq.pre(qe);
end
- L( `% V+ e1 L  h/ {- S& pbb=1;
9 j# n( ~% x6 V- Vbreak;
end %if
) o, b' _: i& O: n+ N/ oend %if
( [0 ]8 P2 L. f$ D* bend
, s  W- E# t8 x3 Kif bb==1
break
end
end%while
5 j9 z, F4 M; U

3 A, Z- G& ?1 z5 D! m8 b这段代码实现了一个广度优先搜索（BFS）算法，用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
以下是代码的详细解释：
4 g; n7 [9 u$ W5 R
1.迷宫定义：
2.maze 是一个8x8的矩阵，其中 0 表示可通行的路径，1 表示墙，-1 表示已经遍历过的路径。
3 `1 G" m4 ~2 S- E) W  g3.方向定义：
4 ]1 X9 X/ P$ ]4.fx 和 fy 定义了四个方向，即上、下、左、右的偏移量。
5.队列定义：
; T( a' ?: z- d" E6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
4 V  c0 _  J# o$ H7.qh 和 qe 分别是队列的头和尾的指针。
0 S/ N; `& M+ w. e$ t! @3 J8.初始设置
9.起点 (1,1) 被标记为 -1（已遍历），并加入队列。
10.广度优先搜索：
11.使用一个 while 循环来进行搜索，直到队列为空。
( w4 @* f0 W4 U- n" i1 K  I1 N- ?12.在每一轮中，取出队头的点 (sq.x(qh), sq.y(qh))，然后尝试向四个方向移动。
13.对于每个方向，如果新的坐标 (i, j) 是有效的（即在迷宫范围内且没有被遍历过），则将其标记为 -1（已遍历）并加入队列。
14.如果新的坐标是终点 (8,8)，则从队列的尾部开始，回溯找到从终点到起点的路径。
1 t- F8 N3 [5 l( E9 U  F15.回溯路径：
  a# K* B& u2 ?( @16.如果找到终点，那么从 qe 开始，通过 sq.pre 数组回溯每个点的前一个点，直到回到起点。
" a, h" Y2 H3 t$ K这样，当代码执行完成后，sq.x 和 sq.y 的值将表示从起点到终点的最短路径。