数学建模社区-数学中国
标题:
深度优先搜索解决迷宫难题
[打印本页]
作者:
2744557306
时间:
2023-12-22 17:11
标题:
深度优先搜索解决迷宫难题
为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
4 o' g( A4 N c
3 |, i! _3 ]$ H! l( H
当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
2 w/ z1 X( ]4 e' c, b
7 [0 d; k) U4 K5 V8 B
1.function [total,maze]=search(i,j,maze,total);
5 [! @4 D5 a1 `# [
3 @7 m1 R6 @% s3 W
4 q2 b" s; e; u
2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
$ ^* Z; U8 w5 a* G
+ y' O! L9 |9 a
1 A% v, E+ e/ W
3.fx(1:4)=[0,1,-1,0];
$ `7 B* M$ }# f" [: v
$ T" h$ A" O0 J0 r5 M
8 J& H+ t! F1 m9 A6 M' ?) s2 U
4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
; O( E: I) B. g$ ]) I4 N4 k) F" ^. u0 ~
# c8 ^: q2 y$ H$ ~
( p3 c5 U; I1 |- h* W3 }
5.fy(1:4)=[1,0,0,-1];
6 ^# Q* O, e, v+ N0 k- f
! d$ C# F9 ^; ?, o( _7 B. P2 K
) N. y* u }/ {
6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
3 y% c; v, U; G' B+ K9 p
; x# P9 R7 e" c1 n% z: F- K, [
4 L4 n0 u, ?: u# A
7.for k=1:4
, Q5 ]2 N, x* X& d' w& M i1 C
3 R* w$ D4 _4 q- {
% o; G4 j8 J) J6 ^; i/ j) Q
8.开始一个循环，遍历四个可能的移动方向。
. [, z. O4 p/ c8 h* X
: \# [( Z: I9 L. F0 K1 r$ c1 B
3 K4 V z0 D7 \: |' c6 w
9.newi=i+fx(k);
+ H$ g$ U( J: L. p5 `
. n. ~6 U$ L _
: i" D/ w1 i8 W1 O2 p; F+ M
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
+ U: F* i& u$ k. f H! ^
3 W+ T7 s1 E. E) b
; c, g6 A% V1 A$ {
11.newj=j+fy(k);
: @6 U) x( k9 D
& @9 e! s m |. x
+ l( `4 t* f o9 Q/ Z
12.根据当前位置(i, j)和移动方向计算新的列坐标newj。
7 v! ?" ^% Y2 j# O* t2 ?
, }; q8 j- x) o# }+ ]$ `
0 p$ F& {. p- V4 e, U# A( K
13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
Z; ^9 C8 ^! [9 Q8 f* @1 Q" e; S
5 L4 B! B9 r7 C
+ u- m2 y! _) R' t0 N3 R2 y4 D! u9 W
14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
; [$ e+ X/ l. G- ]9 }
) Q) a/ [9 n/ g j
}, G7 U4 E4 r+ H( \' g3 ^
15.maze(newi,newj)=3;
; H$ j% B8 X9 ~# m! L, ?
1 q# ?1 |$ q2 C
/ n3 f9 I' J+ h" _; |
16.将迷宫中新的位置标记为3，表示已经走过。
* w1 o) L( G6 T$ w
6 O1 _6 E( ]0 `6 a+ l: e
: r7 O3 s: ]" a2 l9 O) l+ `
17.if newi==8&newj==8
4 b/ r4 Q4 A q$ ]# o+ d% G
/ D+ p3 a% C4 K1 W9 M$ H, e
* b* h2 N+ L5 Q- J+ T# q2 J
18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。
w. f# I% L5 A) P" }- ^
! Y" s/ f7 p2 V! ~& P# o: ` ]* F
, H) @+ Q4 x: |& L! F: J- F
19.total=total+1
5 O( ^4 o7 W, g6 ~# M) p
' M' i( J1 P' f( q, g5 `
20.增加解的数量。
3 B2 F# q) h a& ~# }
21.maze
# T1 N& S* ?. n
$ y( v8 m/ k; D8 l3 l
22.显示当前的迷宫状态。
7 Q8 s& d5 _3 e) ]0 y' Q
23.else
8 D" s1 a0 l6 D) O# x
; b4 ~- W1 q: J' ]
24.如果新的位置不是终点，执行下面的语句。
, V4 m! H; b2 r! o0 D& Z
25.[total,maze]=search(newi,newj,maze,total);
4 i4 Q3 I }8 j2 |" G
7 K& E# S T# R8 o3 X" h
26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
- ?" R3 i. j8 {$ o0 O- Y
27.end
/ S2 s2 l, G# ~8 \: ]
6 w) F! A% Q, v" _8 K3 c5 w) L# G( ^
28.结束if语句。
4 d2 L2 Q. S& x% R1 L& [, B
29.end
3 ]4 U9 D+ [/ h$ K
2 b1 J) m( \$ @& U8 g
30.结束for循环。
3 r: `; H5 u, |! U
31.maze(i,j)=2;
- Z, c/ |# V; K* O& y
; Y. d8 n# n* I
32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
: I, H3 Y2 x) \' h3 p, }, N/ f+ r
33.end
T2 P7 q' z# X& k3 A
* F3 ^4 P7 o1 k; {% m/ U/ l
34.结束search函数。
) P( M& H* o$ j7 X0 ]9 c
35.clear all
: p/ L7 n/ X5 R' `! w
6 c& N B5 W: W* e' R3 Y9 Y D
36.清除工作区中的所有变量。
4 o( Q% g1 @6 j9 p# J" o: a
37.clc
9 E% i5 f7 Y" }
0 M2 z7 ]4 k% g) \- H1 a
38.清空命令窗口。
; e' c$ K% v/ I1 t
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
4 Q& t6 X& _7 L4 J: {
40.total=0;
" }) q; s% { q* y1 N
) r6 r5 h+ f% t7 ~" d* \1 \
41.初始化解的数量。
. N* w) c4 x, A# m3 v
42.maze(1,1)=3;
0 |* M- Y J& d4 Y0 y/ G2 M
- t2 ^/ H: M, B- B
43.将起始位置标记为3，表示已经走过。
: U; A4 L) G+ _9 y& J. d3 p% J/ ]
44.[total,maze]=search(1,1,maze,total);
# M1 ] ~+ ~, b& [( C; K5 E
: t) ^& L) U. e$ }% P1 F# l7 p! W9 U
45.调用search函数开始深度优先搜索。
8 D+ p2 f% v% u" X
7 ~. ?! \+ F4 h& Q* C" k
整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。
7 |5 ~# E; L3 \$ h
+ V( v& d8 S# a
9 _+ Y6 E/ ~, M- R
/ ~! a% P4 i; R; @! K7 l- z3 I
$ M8 g& {6 {% C% X0 l* r
5 B: U5 B8 w% E1 _
* ~; A9 ^7 }- C' G9 _/ \2 a" _
深度优先搜索.rar
2023-12-22 17:11 上传
点击文件名下载附件
下载积分: 体力 -2 点
637 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
1 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
