数学建模社区-数学中国
标题:
深度优先搜索解决迷宫难题
[打印本页]
作者:
2744557306
时间:
2023-12-22 17:11
标题:
深度优先搜索解决迷宫难题
为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
4 p) p; X M% t3 j9 m3 E
! p2 g5 e5 y9 e$ _
当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
1 Y I2 _5 r4 y' r
7 q; h7 h9 ?4 i0 a! h7 p
1.function [total,maze]=search(i,j,maze,total);
/ i# h7 C) ? ~# G# T' k4 Q
: Y: L1 N: t2 x) F1 G
) `1 `& o6 t. [4 `, w9 G0 q$ G
2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
5 y e' J1 L- |
- O/ K Z6 U- B. t6 ~6 [& p
$ N* F/ |8 m3 T- M2 E
3.fx(1:4)=[0,1,-1,0];
& |% g9 ^ H9 h; D+ D% F
( Y: d7 ]- Y! g3 G( K
1 K1 `. s) }- T6 j0 O: H! U) @4 r
4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
7 c- e7 `+ l1 P/ [
0 f6 |+ I! {$ h ~
1 ], R% v5 U" V o6 ?
5.fy(1:4)=[1,0,0,-1];
% D7 D6 Y7 j4 k' S2 C$ }
}- l7 @: q5 F, Y
% G+ g% s# X0 O& i+ l
6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
3 r/ p9 A: e: i- J- X5 }
* j$ I N8 q8 p L
2 `6 K" ]7 U3 |& B
7.for k=1:4
1 h! Q M! V$ m* D/ v6 R
3 d4 h C; |# {/ m ^+ ~( k
- }- \: G3 y0 g2 b
8.开始一个循环，遍历四个可能的移动方向。
1 a8 k0 q9 k8 S. ^6 b
L( T2 t1 ?4 y' B) x
1 Z' o4 W/ Z, e
9.newi=i+fx(k);
) Y4 q! m& P$ N. h7 L5 {) C! `- H
5 Q6 x* g! f6 U* F
# r( y5 Q1 X N* e
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
- J: J1 z& _5 @& T% K* \: o) L S
$ }8 m6 J! x4 F
, i& U$ h! Y4 t. I' h/ v- I
11.newj=j+fy(k);
+ y# l( {: |3 N; L
* [; C3 b4 c5 x% R
: {) O3 s8 i7 W
12.根据当前位置(i, j)和移动方向计算新的列坐标newj。
7 |3 K3 q$ i8 Z
/ s: z' p, U) f; a1 ]
% ~8 l" q f7 D8 w
13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
8 z7 e) E/ J3 S
3 f& O( s: G2 D1 n. P& O
: _- ~0 T9 {( Y0 c
14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
9 L& D8 z" w* `* ?6 B
% Y; G, O( Q q
# J9 X: U$ t0 a) M
15.maze(newi,newj)=3;
" ] [+ J3 D: `
- K2 g( K& Z1 O/ \; |) c! ~
/ v0 I& g; F* l. L0 n1 c
16.将迷宫中新的位置标记为3，表示已经走过。
. c( \ z: Z3 ~
" @/ W, t. K4 P2 j( Q0 r6 O
& _! {) N( P) w) ^
17.if newi==8&newj==8
0 c* u& r6 S( s* J9 @$ e9 t
- N7 J0 ?, F U5 B# L
2 u8 R. K5 ~' t$ k G0 e3 ?% x
18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。
1 h& {; @+ N; k6 S- g" R
& p7 G. ~; p1 d$ x6 O. Z' \0 N
+ p/ i, r& a+ c) {/ z _" f$ |( b
19.total=total+1
3 ~) P. s% n4 f, _8 ^
# D1 i- q3 t3 M
20.增加解的数量。
) T# c* W, c$ \
21.maze
/ d8 z& O- b, d# `9 q$ z
" p6 l; O! N8 T" y) Q
22.显示当前的迷宫状态。
1 s4 T) e3 a* P$ o. t# [5 l9 Q1 D c
23.else
- ?5 i3 O3 b* a* f3 |" I
8 ?# T) L" @' p+ F( \ l! R) z2 J
24.如果新的位置不是终点，执行下面的语句。
0 j) r/ M0 X' ^ J* [
25.[total,maze]=search(newi,newj,maze,total);
9 q! {; a( s- P! `* ]
- P# z0 @! q/ h6 e& g/ ~2 W
26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
0 y" l. W7 }, H$ d' {; A! e' {
27.end
+ S1 M/ v" ^$ n( ~& R
1 J& k- }3 d2 k3 W" P( w2 }$ ]
28.结束if语句。
4 B* e! T, j6 ?/ M* t
29.end
$ Q, o6 |" u: Q( [4 U
& g$ X( o+ i; ^# a9 \
30.结束for循环。
/ u v2 R2 c Q. O+ }7 K% C6 @9 Z
31.maze(i,j)=2;
& [0 o4 F. f7 |1 z
/ x; u6 l4 s5 B) o
32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
L/ ~. o9 T* ~/ t- m. ?4 Q
33.end
* m! z" R1 G2 d! t' E* I' q7 O
( @% X3 q2 \% [% u
34.结束search函数。
' a9 c; p6 u0 Q
35.clear all
# [! ~+ j- F! g P( X! [3 L) `
% D( P( |+ P& f. d$ S8 \
36.清除工作区中的所有变量。
# b6 V8 d6 b( } j2 u% Y a$ U- x
37.clc
" }; G* a+ B) k
. D. L+ }1 t2 `8 R7 u
38.清空命令窗口。
7 O$ h5 k5 v0 C7 R6 c# |+ r- z; v: {; S
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
2 d9 _' D' {7 o3 f+ | ]$ _' m
40.total=0;
Z+ h! c8 S; [; x0 F% Y/ x" W
% x8 I& u7 I2 \; o& N7 v Q$ h
41.初始化解的数量。
t5 M, Y$ w6 x& I
42.maze(1,1)=3;
: v3 J% G4 w5 O$ c8 `* b' R
. I' i! J5 Y' P) l% [8 d6 {% d
43.将起始位置标记为3，表示已经走过。
; A1 a- a4 `8 K! z
44.[total,maze]=search(1,1,maze,total);
% `# A$ j0 |% N7 ?7 l
# z, Z* m. ~7 B3 l' z2 A7 @- `7 _, X
45.调用search函数开始深度优先搜索。
* a: A+ P% Y, L& \* Z' H
0 h" Q9 s! R6 a& W x$ ]+ {6 S
整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。
0 T/ J; I) \2 e. V, S
/ T& k1 n3 c& j* k2 q0 d0 z
# s4 I) x6 P1 U. A0 _: |
9 O( d+ S$ H4 \
- o& v L5 ^' Z- \3 D5 Y- g
% }1 q" Y0 w' t! f2 {! H. H9 [. \
9 ~7 l* R X2 h: i/ K
深度优先搜索.rar
2023-12-22 17:11 上传
点击文件名下载附件
下载积分: 体力 -2 点
637 Bytes, 下载次数: 0, 下载积分: 体力 -2 点
售价:
1 点体力
[
记录
] [
购买
]
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
