数学建模社区-数学中国
标题:
广度优先搜索 找到迷宫中的最短路径
[打印本页]
作者:
2744557306
时间:
2023-12-22 15:52
标题:
广度优先搜索 找到迷宫中的最短路径
clear all
8 q; k, J( W& f4 H) ?
clc
8 f8 T0 l6 p; g: P
maze=[0,0,0,0,0,0,0,0;
6 z; Y2 n! f. B1 U, l, i2 \5 ?8 I
0,1,1,1,1,0,1,0;
/ E) R" V q; f, s& Z% C
0,0,0,0,1,0,1,0;
/ r: o# a4 W0 @8 l0 A4 `
0,1,0,0,0,0,1,0;
" _; C4 a1 I# x; Z
0,1,0,1,1,0,1,0;
/ p( D. S. g, ?
0,1,0,0,0,0,1,1;
4 B" E4 H0 f u/ M2 S
0,1,0,0,1,0,0,0;
7 p" U2 r: }/ n. i
0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
+ V# y/ W: L v/ Q
fx(1:4)=[1,-1,0,0];
4 c3 ?: _& K( [* R s$ e6 Q
fy(1:4)=[0,0,-1,1];
. U. G- y R1 z* q- h
sq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);
4 k) k* a- H* E0 \& U# B
qh=0;%队头指针
4 ?. I+ b* C" L# |4 q
qe=1;%队尾指针
) N- n0 ~$ U! C
maze(1,1)=-1;
$ b- I* H# G3 @9 O
%第一个元素入队
% @$ o$ P( e/ _5 {, y) x
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;
- m( g% a/ l( h3 b
, ~; |1 }# i3 T @7 S# _
while qh-qe~=0
, E8 h: k7 f/ g: F; C2 g L
qh=qh+1;
+ v2 H: q- P. ?
bb=0;
, K- l4 A" {# y& [
for k=1:4
% z) O$ w9 ^3 G
i=sq.x(qh)+fx(k);
& K. D2 h/ A, F) R W# d
j=sq.y(qh)+fy(k);
% ]1 H! |: T( v7 P
if check(i,j,maze)==1
4 r& K) P& U( v" S6 N
qe=qe+1;%入队
M5 t$ ~% I( O/ o" a, q. z- m) p# i* K
sq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
5 q# S, k" b ?8 b! C
maze(i,j)=-1;
2 r3 Z7 g; a, O' O' o, r, I5 l
0 E2 Z" c' [+ a7 j7 c7 V
if i==8&j==8%如果为图最后一个点
1 g6 a/ G$ F9 r' ?! V
while qe~=0
( ]; c/ H+ e3 }8 j+ L- C
sq.x(qe)
" n2 O# }7 c3 I; L7 O$ J9 G
sq.y(qe)
' c9 ^2 O1 m% W8 [
qe=sq.pre(qe);
7 c0 ?* N3 c4 X3 G
end
. ]4 n- G; h& M3 v/ \* I
bb=1;
9 c- X! O1 l8 {& W# U
break;
5 X1 L7 {( x g! b# c2 x8 c
end %if
) }' S1 @, }8 g) C
end %if
. H6 [, q" A" d; f) v
end
6 {( H$ N+ z$ D& ?5 h
if bb==1
+ D: v. [( L6 F( b! n
break
# j; c" P4 a: x. p8 D
end
$ O7 o* o. Q' G9 Q; g0 c; n# G7 H
end%while
. D# O9 u, i4 G. `6 [ U
* [" i& Z5 J, b# g
0 U9 ~% ?% g- S% K6 _
这段代码实现了一个广度优先搜索（BFS）算法，用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
) P+ N6 f/ A1 ?) J b
以下是代码的详细解释：
+ N# k4 |7 K: W" M( m0 T' T0 b
/ k1 a! b5 x+ c4 J0 p, x5 A6 o8 y
1.迷宫定义：
) e: P2 F- ^ t* \6 f5 F7 p r
2.maze 是一个8x8的矩阵，其中 0 表示可通行的路径，1 表示墙，-1 表示已经遍历过的路径。
: m5 V5 \9 E3 ?' I; `0 Y8 e
3.方向定义：
1 _5 Q/ R2 t* Y4 i; l
4.fx 和 fy 定义了四个方向，即上、下、左、右的偏移量。
0 ]8 |2 X- |8 m+ {$ b
5.队列定义：
8 s" x3 M) ^0 `' c& r+ f* k7 y2 n6 |
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
- O3 T- ?$ q) h: y7 N
7.qh 和 qe 分别是队列的头和尾的指针。
0 a5 o2 E* @1 f4 o* n' R7 g* H
8.初始设置
9 X# K( X$ L& c0 E8 M8 P
9.起点 (1,1) 被标记为 -1（已遍历），并加入队列。
! ^7 c" g+ t! d+ q8 V. G
10.广度优先搜索：
0 z8 E1 z8 g7 X% l+ A5 Q# S1 }( |( B. Z
11.使用一个 while 循环来进行搜索，直到队列为空。
6 p0 ^9 a& W! m6 n5 k) B$ P
12.在每一轮中，取出队头的点 (sq.x(qh), sq.y(qh))，然后尝试向四个方向移动。
( W4 y& D% \7 X% g h3 U3 G8 U \
13.对于每个方向，如果新的坐标 (i, j) 是有效的（即在迷宫范围内且没有被遍历过），则将其标记为 -1（已遍历）并加入队列。
0 c9 d. i y* Q( u$ g0 C
14.如果新的坐标是终点 (8,8)，则从队列的尾部开始，回溯找到从终点到起点的路径。
1 N, c$ m! x; |6 o5 o
15.回溯路径：
+ D5 ~7 t3 a3 d, R
16.如果找到终点，那么从 qe 开始，通过 sq.pre 数组回溯每个点的前一个点，直到回到起点。
6 t+ [3 t0 s& j1 `# ^, F9 H, O) o% W
这样，当代码执行完成后，sq.x 和 sq.y 的值将表示从起点到终点的最短路径。
9 B) I( W" ^6 o$ T
, C+ Y2 c* ]* U# e- `; J+ d( @
0 F9 O# [% U7 l
广度优先搜索.rar
2023-12-22 15:47 上传
点击文件名下载附件
下载积分: 体力 -2 点
736 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
2 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
