数学建模社区-数学中国
标题:
深度优先搜索解决迷宫难题
[打印本页]
作者:
2744557306
时间:
2023-12-22 17:11
标题:
深度优先搜索解决迷宫难题
为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
5 e: A% F/ I; t, g m+ c
7 C- I3 ~2 c" E
当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
. w* n0 ?9 V& l2 q6 f, U
/ D8 r2 c( q5 e. Z/ Y! ]/ a) \1 E
1.function [total,maze]=search(i,j,maze,total);
; ^) ?& v' K2 w# i
& k0 x* x, t4 t" L7 ~) y) z
5 f |" R8 I- }0 M4 N) Z* [8 b
2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
) x$ }) M- E0 v$ ?; `/ x9 l. R& V
: |6 q1 I2 ^& N: J" S
) @2 @1 V( e0 }8 s9 s4 j! h
3.fx(1:4)=[0,1,-1,0];
# u" j8 a& \6 a3 ]5 ]' j2 J
% }+ a8 P4 G. L! ^$ g+ K
0 L/ f- p1 J9 v7 A3 F1 P
4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
O9 @; @) G8 c Q, \ D+ \! h$ E
+ p' K$ \4 h/ o5 p2 C( P* N% S
0 l6 X5 d0 n. g" F1 E3 v
5.fy(1:4)=[1,0,0,-1];
# @0 @; y- X7 q1 x b! d" v7 ?5 ]
6 }" u) \) e2 k# r- G9 L# s
% D+ I% r1 {9 `9 {. [' T/ r
6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
( k( H! O5 H% g3 }
2 M3 h+ E" e" h3 j/ N
8 u( b* B6 {* s4 }
7.for k=1:4
6 k/ n- ?6 j; X+ G, p# j. Z
! w5 p/ j7 U; u+ {
; {3 r4 ]. @+ Y
8.开始一个循环，遍历四个可能的移动方向。
8 U8 ^, F( P, {8 h- C2 m
1 b6 z) [3 S* y1 m) u
" Z. q) j! e; r9 P/ q, c
9.newi=i+fx(k);
* k" }% I. a1 p7 N9 G
8 G ^5 N$ f2 ^* y
1 O% L b2 p& r( X, x/ b, H
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
, F4 S: G6 d2 ]' S q7 U( C& [% J2 b
: k- d+ {8 x6 x" W
1 |8 J. b, D w! N; ?# j
11.newj=j+fy(k);
* y0 y: Z2 |& ^! q& |
0 T: }2 k7 W& H' t" T7 G6 p& E( S7 x
( s, \3 F$ Y# Q, c) l, _0 m
12.根据当前位置(i, j)和移动方向计算新的列坐标newj。
! q) P8 ]% k7 K' P5 s
# ^+ l$ e5 b- m. E8 I) b
& {- P1 J1 P: ?! q
13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
' y/ a% Q% _4 R! L3 D) \ t9 h
+ J2 s! B4 w, C* i3 z+ ^
+ e6 e- |7 D/ d9 J& g2 \* k) H$ ?2 k2 z, ^
14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
( Q: w3 [8 R1 Z. e5 }
. M( i+ r# I* g9 ]3 K3 K
' S: F# w3 [: [ F# |/ m4 B
15.maze(newi,newj)=3;
7 y8 `& U" E! o1 I- A9 }1 V
4 R7 L8 C7 ~% q: B6 H1 Q2 m5 G% ?1 s
% o, r- _' R; ^1 }: d
16.将迷宫中新的位置标记为3，表示已经走过。
. E# \. q6 V- j3 _9 u% z4 D0 @
* Q' W; _6 `7 o9 L
2 I* P X0 h! P& q( X
17.if newi==8&newj==8
2 k" u V% g6 E) m# o* ^
+ I5 K# f) I( t3 Z
0 Y4 q1 C+ b+ ~
18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。
! u) J0 X4 y* k1 s
3 q% n$ F3 `: I2 w* L& v0 v6 k3 u
8 D( J4 g1 X* X, {3 s4 R+ i
19.total=total+1
z8 m- l! Q9 s
r& P9 t* h! t2 A @
20.增加解的数量。
. e1 A6 A8 z, v
21.maze
/ Y! T$ _- x* N# \+ z( C! n' Y% N* E
' j' x1 g8 e' R: c3 Z0 D7 k2 |
22.显示当前的迷宫状态。
4 t# t- O/ p5 \' }5 _
23.else
" o, X& b! g. ?9 X
+ I8 ?; b) W: D D; ~$ b
24.如果新的位置不是终点，执行下面的语句。
+ A) ^# o a7 l, |
25.[total,maze]=search(newi,newj,maze,total);
* {8 q# M; k! Z9 h2 `
- V) \* ?" J0 C8 w( r; V
26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
7 B) c4 C2 _5 S1 |9 c& f; G! ^
27.end
7 G: X+ X* @6 q( n* H* L
/ F% o, T" `. g
28.结束if语句。
6 T1 L; |4 Q B3 C0 x
29.end
3 L! P7 Q% f. q& R0 {* C9 ~8 l
4 I: z; f5 r* Z) ~; f
30.结束for循环。
$ l# V2 g+ @' i$ J7 a4 Q1 |
31.maze(i,j)=2;
, l: W1 Q8 O7 P7 k
! k+ ]+ x8 s0 q* g: K
32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
# e7 ]/ z+ B( _& x# v
33.end
& H c$ p {/ X3 O- C9 g6 G
& v$ y: v+ D; a- [# y$ ^8 o4 m
34.结束search函数。
4 ~& |$ g8 p. F' |/ ^7 R0 `
35.clear all
( d1 j9 l( i9 |9 O% w3 w$ J8 ~
3 z+ n! Q% ?: @% w) s* Q
36.清除工作区中的所有变量。
$ x$ k" V& h0 l6 d0 ^
37.clc
% Z2 P- X5 ^* ~
% o6 C$ C# k$ S# b: I
38.清空命令窗口。
4 G- s; Z7 ]& p. \$ m" k8 g
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
' U0 M# g7 c: ^/ H y( B+ Q9 q
40.total=0;
) [+ ?/ j1 F+ Z' u- i! X# u
7 Y u, o V3 ?- B$ ]$ V4 ]2 R
41.初始化解的数量。
% I$ z1 T( B' I5 L, \/ W+ s T
42.maze(1,1)=3;
4 n$ j }! G8 T: j
6 Z) t% Z3 R( _3 t8 Y( }+ P
43.将起始位置标记为3，表示已经走过。
4 b8 y* G+ {9 e. X) j" n" I: M
44.[total,maze]=search(1,1,maze,total);
; t+ B. D* N, a+ J
+ ^6 R5 f; ~1 \# z; J' S$ s7 w9 V% X
45.调用search函数开始深度优先搜索。
/ y. m q9 C3 A Q$ B- n% _* _
6 p2 K% P/ m0 Z r3 g z. h
整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。
. n3 \$ u' g- k/ N0 s" Q
" M' ~" A6 F$ a6 s" y
! [( d, f( G0 `0 m! C, R
$ @2 C% v. U; F& m3 |# Z* f: ^2 I j
3 }. t" B: B$ Z! s0 M
* b( N, W) l) s
6 [3 A1 F5 ]) t
深度优先搜索.rar
2023-12-22 17:11 上传
点击文件名下载附件
下载积分: 体力 -2 点
637 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
1 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
