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

2744557306

clear all
clc
1 S6 u/ `. e; [7 c6 \maze=[0,0,0,0,0,0,0,0;
5 k, k. l, I1 S& L' y      0,1,1,1,1,0,1,0;
      0,0,0,0,1,0,1,0;
+ T/ w3 k9 g4 h' @$ E2 l8 _! d      0,1,0,0,0,0,1,0;
0 y1 f( c9 A8 p$ J) G0 B4 w% a      0,1,0,1,1,0,1,0;
      0,1,0,0,0,0,1,1;
      0,1,0,0,1,0,0,0;
      0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
* K4 g* c( u) Wfx(1:4)=[1,-1,0,0];
0 N/ I# @: |7 W( e3 Hfy(1:4)=[0,0,-1,1];
sq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);
qh=0;%队头指针
qe=1;%队尾指针
% U& D3 y" a! D5 |1 jmaze(1,1)=-1;
%第一个元素入队
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;

' y, M1 s1 j# c6 e( V2 Wwhile qh-qe~=0
4 y2 F- c+ L: w6 q/ B# O, sqh=qh+1;
1 h7 y. g; i4 Y9 \& P, q0 i1 jbb=0;
for k=1:4
& o6 d6 H; O4 F) i/ F+ v% R$ K+ \i=sq.x(qh)+fx(k);
j=sq.y(qh)+fy(k);
if check(i,j,maze)==1
qe=qe+1;%入队
9 Q; @7 ]3 Z, a. o1 o1 |sq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
maze(i,j)=-1;

: o# s/ k, s, B3 T$ f* S+ {" Rif i==8&j==8%如果为图最后一个点
while qe~=0
sq.x(qe)
7 M0 ]" B" B7 n0 f" S! ssq.y(qe)   
qe=sq.pre(qe);
end
" F% \; t& r- v( V7 Vbb=1;
break;
end %if
4 ?) G2 N$ H8 x5 B/ h  G: _  {end %if
end
  C2 Y( M8 s% e' @7 Fif bb==1
break
end
end%while

" Q: V5 t$ t' a/ y# {  V0 ]
这段代码实现了一个广度优先搜索（BFS）算法，用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
以下是代码的详细解释：

; c6 P. l8 G* G5 s  ?1.迷宫定义：
2.maze 是一个8x8的矩阵，其中 0 表示可通行的路径，1 表示墙，-1 表示已经遍历过的路径。
: ^6 a6 t  i: d& N! X+ i# v3.方向定义：
4.fx 和 fy 定义了四个方向，即上、下、左、右的偏移量。
+ B* P% ?7 G5 o, `5.队列定义：
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
7.qh 和 qe 分别是队列的头和尾的指针。
" C6 l! Z# G7 P6 y3 h2 \- X8.初始设置
9.起点 (1,1) 被标记为 -1（已遍历），并加入队列。
9 z. A* G1 t* b10.广度优先搜索：
+ V3 U7 D" b) z3 H11.使用一个 while 循环来进行搜索，直到队列为空。
12.在每一轮中，取出队头的点 (sq.x(qh), sq.y(qh))，然后尝试向四个方向移动。
13.对于每个方向，如果新的坐标 (i, j) 是有效的（即在迷宫范围内且没有被遍历过），则将其标记为 -1（已遍历）并加入队列。
14.如果新的坐标是终点 (8,8)，则从队列的尾部开始，回溯找到从终点到起点的路径。
15.回溯路径：
16.如果找到终点，那么从 qe 开始，通过 sq.pre 数组回溯每个点的前一个点，直到回到起点。
0 ^/ C* l3 Q1 ~6 q. t) T这样，当代码执行完成后，sq.x 和 sq.y 的值将表示从起点到终点的最短路径。