QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1751|回复: 0
打印 上一主题 下一主题

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

[复制链接]
字体大小: 正常 放大

1176

主题

4

听众

2884

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 15:52 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
clear all/ X# f7 m4 v. y. t4 M' Q
clc
) R( y1 Q4 o  s  t8 a- E3 Fmaze=[0,0,0,0,0,0,0,0;/ m3 V, E0 e. M1 ?9 P, j  E2 T' @* G
      0,1,1,1,1,0,1,0;
2 I/ Z- }0 k, L% }2 C      0,0,0,0,1,0,1,0;
- O' O1 g, T- P7 J% V( Q' \      0,1,0,0,0,0,1,0;
8 s& H: h( j8 i$ T      0,1,0,1,1,0,1,0;& t2 L! _7 v5 U
      0,1,0,0,0,0,1,1;
1 C# v0 b, u( p! H( J# ^8 M+ t6 q      0,1,0,0,1,0,0,0;+ D+ I3 C8 h- S3 O4 f# w0 n) m
      0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
) _& j  ~" k& \+ b6 Ofx(1:4)=[1,-1,0,0];/ m+ I/ ?5 m" d& c7 b
fy(1:4)=[0,0,-1,1];/ E7 U. U* u  Y4 \# _# l2 O4 X
sq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);
) m9 d) l. T. U; U: B% R3 h, jqh=0;%队头指针
4 c1 D3 G- |  D5 F' q& Nqe=1;%队尾指针( W: h. a! R- g3 j* S5 K7 M
maze(1,1)=-1;
  F% @: i5 e' `" r0 T/ B%第一个元素入队0 ?' S/ B& y, c0 p/ `7 [
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;9 k* q+ f8 I" n; `) C
7 N6 h: O1 j4 ?6 G! t  w1 d' A6 Y, ~# j
while qh-qe~=0
9 ]4 U$ ?2 M8 ?6 \7 @, j( l5 _qh=qh+1;
, J8 P$ u+ C: T2 y0 N8 z+ p2 mbb=0;
: O3 r9 j  j1 bfor k=1:4% m1 B/ ]/ R5 r0 y3 `( w- o' S7 e# e
i=sq.x(qh)+fx(k);: z7 ?! W" n& r$ S$ p1 Q6 v& l
j=sq.y(qh)+fy(k);
# E2 G9 M, e4 ^9 V; y# w7 xif check(i,j,maze)==1: l, S1 c. g$ K$ t( @
qe=qe+1;%入队
% ^. ]- r  ]9 j; t! u; P7 vsq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
$ n5 F2 E! n% i: n; m% omaze(i,j)=-1;
/ q  O) Z5 h: u. `; e/ {/ J8 Z- v: R5 O
if i==8&j==8%如果为图最后一个点
- j/ f3 |; v1 `8 B- d0 nwhile qe~=0
3 p, ]3 ]! Z/ v$ _sq.x(qe) ( D5 A9 O" d) ~! D* M
sq.y(qe)    / F8 B) z8 X; Z! N8 x" [% T
qe=sq.pre(qe);# p5 u! F# q2 f) ^' Q  Z  k
end : j9 u: ], K) L' T" q0 m
bb=1;
% h: ?" Q* l5 _, Fbreak;: z5 C0 v( y4 ?; ~9 O! w6 B) q
end %if% S2 J8 C5 W- d
end %if% a2 e8 s& T7 q. {0 V' ~; Q5 f
end0 `1 x7 C# L; g/ T# \8 T+ D' P9 T
if bb==1
( s. z2 H( t3 J  Z" j( M" vbreak
: [. R7 t% ^$ A6 e5 B* Vend1 A& ^9 i  N& e
end%while8 C  P7 x/ G9 Z: i

  ~+ q5 ?: Z$ G5 w3 g$ @& x* E! G1 N% ?' g( r% F4 \
这段代码实现了一个广度优先搜索(BFS)算法,用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。' q4 x* S! c2 n7 ~5 n3 q) z
以下是代码的详细解释:# W/ I% }( O% _1 R' o8 J9 W7 O
* U7 P  V3 `+ I- B# u
1.迷宫定义:! e0 B1 z* F+ ^" R: V
2.maze 是一个8x8的矩阵,其中 0 表示可通行的路径,1 表示墙,-1 表示已经遍历过的路径。
" T& V. h/ ~) t! D/ H; x3.方向定义:9 f) j! |# D. ~5 U. |0 _
4.fx 和 fy 定义了四个方向,即上、下、左、右的偏移量。
# n6 t8 s6 t/ l( d* N5.队列定义:* ?# @0 z. W9 ^* r. K6 J
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
! {% t' C# l4 K3 d# i7.qh 和 qe 分别是队列的头和尾的指针。. Z* z/ x* ^/ F  r( c0 s% `. b' F
8.初始设置
% M, m* A9 |) B( c9 @: M9.起点 (1,1) 被标记为 -1(已遍历),并加入队列。
  q$ U+ y, Q* u% @10.广度优先搜索:) B9 r8 Z; j2 Q6 |  @1 R
11.使用一个 while 循环来进行搜索,直到队列为空。% n& d1 p! Y) [& h! u5 a
12.在每一轮中,取出队头的点 (sq.x(qh), sq.y(qh)),然后尝试向四个方向移动。" A2 N! E, h1 D- F. B; Z; X
13.对于每个方向,如果新的坐标 (i, j) 是有效的(即在迷宫范围内且没有被遍历过),则将其标记为 -1(已遍历)并加入队列。
! X0 R$ s* q- y14.如果新的坐标是终点 (8,8),则从队列的尾部开始,回溯找到从终点到起点的路径。: J& P. k4 C5 D1 L
15.回溯路径:
, c( N9 [4 k9 b8 ]5 i8 D& ]# r! u16.如果找到终点,那么从 qe 开始,通过 sq.pre 数组回溯每个点的前一个点,直到回到起点。6 A7 j3 ^% d8 O* E
这样,当代码执行完成后,sq.x 和 sq.y 的值将表示从起点到终点的最短路径。
5 K$ x5 q# a% T& ]2 a% ?
( w1 |5 v! A+ L3 x. a* m  Z- n9 w" }7 r# L2 a: n  a8 _- q0 U  R1 H  Y

广度优先搜索.rar

736 Bytes, 下载次数: 0, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]

zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2025-9-21 15:12 , Processed in 0.297714 second(s), 54 queries .

回顶部