QQ登录

只需要一步,快速开始

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

深度优先搜索解决迷宫难题

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

1189

主题

4

听众

2934

积分

该用户从未签到

跳转到指定楼层
1#
发表于 2023-12-22 17:11 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
为大家分享一个代码,该代码是使用升读优先搜索解决迷宫难题
  Y& X5 K: h& H+ V" p
2 C# d. r* m7 H! i1 [9 ?' P当调用[total,maze]=search(1,1,maze,total);时,会从(1, 1)这个位置开始,在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释:) G$ O2 ]2 a0 Q
. K8 d& D9 ?# t5 j
1.function [total,maze]=search(i,j,maze,total);* \5 n3 b# {4 s/ r  W7 Q

6 M  v# r3 }. X2 F0 {- b& _- |& M3 L$ Y) I6 u( K! d* y( J( z! g4 x
2.定义了一个函数search,该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数,并返回更新后的total和maze。, B/ n9 Q: t+ {1 C

% V9 N9 T" j' \0 z2 \, e* l* v1 d
5 P" }/ ~* e& v+ R# p* }% e3.fx(1:4)=[0,1,-1,0];3 Z8 A- F( e0 u, L
+ _3 Q+ j% i% f2 t0 r
' ~) g1 i5 V6 e
4.定义了一个包含四个元素的数组fx,表示在行方向上的四个可能的移动。7 B4 W) s' T; t& m! @' D3 ?. H. X4 |& C
3 Z. y9 Y- r8 n5 f  i6 m5 O( P% h
( U4 X) D: @- T# A2 o& J
5.fy(1:4)=[1,0,0,-1];
* j  A7 `; R$ h3 n) K0 G2 I1 y2 |
/ q' E! I* \/ v% H$ D
! p2 v$ G4 ~/ c/ m/ a4 V: b) x. C& u2 s6.定义了一个包含四个元素的数组fy,表示在列方向上的四个可能的移动。2 g2 G  Z8 s6 u  _- M

# P/ c5 l. l" K$ _$ G' t" Z5 [- r" I+ _' M; z& D5 y0 k; q
7.for k=1:4
) j# I6 i0 v( b+ z" {- ^7 l  \
; I) U0 Y: f4 p! E$ Q  v0 f1 o; K6 w8 L
8.开始一个循环,遍历四个可能的移动方向。: }( b7 ]2 c% g; I

& v, i1 n8 |# M9 |1 O, V0 Q- y
$ h& p# s8 y! J* u: {9.newi=i+fx(k);
" G" q/ o) A0 q0 O3 q- `5 d
" c0 L( }* ]0 K6 d9 c) ?3 Q* @. u* b& P% j3 N: q6 W
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。6 f; R8 }# D/ ]- Q

& Q3 V9 q$ G+ L5 t$ c* {/ ^- ^  z) g" N- r
11.newj=j+fy(k);
" K6 I  G8 G/ a  I5 d# o- U/ \) S3 Q* t/ o# A' ]& Q2 Q2 m: t
6 W0 k2 |5 j9 ^
12.根据当前位置(i, j)和移动方向计算新的列坐标newj。
; d) q- [; N3 a5 Z6 ?9 ?3 H
2 e. i2 T+ ]2 E) C: k7 p
2 k. J6 B- ]" P5 s% _) b1 Z! j% T13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
/ Q  E! j4 v0 S
1 X0 t' }* T$ _5 m# j/ Q- `: d# r4 o! u% M. H
14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的(即迷宫中的值为0,表示可以走)。
1 L+ v9 r( P) s8 d2 K. g5 |, T; j5 K9 a. f3 O: b

/ _: R8 L0 S" F$ l5 D& w% z15.maze(newi,newj)=3;5 p  c: P8 d- U) D6 Q) h" q+ i

, x. L- z2 O2 S
* {' N9 N! Q. ]( y16.将迷宫中新的位置标记为3,表示已经走过。0 |2 ]/ U2 W$ K- U
, l$ ^5 e" t0 v% }; q0 J& e3 K

7 b+ b% L) W6 ^9 f  A& t17.if newi==8&newj==8
2 L9 h$ W: g. O
  U6 }" f: g. R) A9 K
8 s5 A; y8 W) V1 l9 |6 Y18.如果新的位置是终点(8, 8),则增加解的数量total,显示当前迷宫maze,并结束递归。
8 \4 r( H( V! n6 v% G  G! x1 ~4 x2 j0 s" N+ |6 u5 E
* J1 d( L3 d% H9 \/ |9 q
19.total=total+1
, }& F# \  b1 ?. H7 y& {# N
( j* m0 X9 A" F8 |$ S20.增加解的数量。
9 x1 o) x( N: c/ R21.maze- `9 d  m) ~: I4 }% J- z2 v( Q

* M* n. b' O* O0 i9 s/ `; R. Q" o22.显示当前的迷宫状态。
5 b  L/ A4 }8 p* L  R23.else9 c* q* G" {- l: l

6 Q9 L9 l" H+ Y  x# G24.如果新的位置不是终点,执行下面的语句。
7 n4 q/ f- C$ H+ }. [% n25.[total,maze]=search(newi,newj,maze,total);6 @* }  B0 z, ^% N7 z" O
1 `" ?2 _/ N; n' G' b3 j" w
26.递归调用search函数,以新的位置(newi, newj)为起点进行搜索。# n' L. J& z  c
27.end% |: N3 ?  q4 }

0 H3 h' v9 u; A28.结束if语句。
# J2 W/ G( {6 X/ S# G1 f29.end
$ \% p& H+ G4 e8 L, G# {. m
5 {. U) Z* w1 T/ m$ D, d6 S30.结束for循环。* D. v5 B; R4 |( Y$ Q1 q
31.maze(i,j)=2;) Q" G" u: |  A5 {$ h2 y
3 j" J8 p% `1 G( g' }9 L
32.如果所有可能的移动都被尝试过,将当前位置标记为2,表示当前路径是死路。
* h; k  {) t  M% ^# m' w. w33.end
0 Z+ s4 P1 I- F5 `/ L0 U( i9 M5 {- Z3 c2 [, b2 G
34.结束search函数。- W1 z8 h+ b" V* J% `0 Q2 \! \/ _
35.clear all
# q5 ~  k) h% s9 V. u; |$ V1 E; G& S$ N# z$ H: i
36.清除工作区中的所有变量。, A& W: o3 q. E7 B' a- e% F
37.clc
9 p4 ^6 ~. U4 {) [# ]' c
# V1 ?, {. m1 k7 Z  a: z1 J% I  j38.清空命令窗口。
; j9 ?2 R7 n0 [) Y' ?8 s7 F39.定义了一个8x8的迷宫maze,其中0表示路,1表示墙。. p4 I3 G4 T6 n* K8 F
40.total=0;
, Q8 p2 e& J% d) K1 X
' L2 H/ _5 u8 G) e/ S. u6 @41.初始化解的数量。  w! n( X: f* ?
42.maze(1,1)=3;5 L1 x7 g+ W. p. n# h- _. X
6 ?) d, A) H2 b5 B/ g
43.将起始位置标记为3,表示已经走过。( b4 ^& v, C7 R6 }8 B
44.[total,maze]=search(1,1,maze,total);
4 j1 E( e/ G+ S+ y7 A5 T
8 q8 G3 H: b0 @  }2 l45.调用search函数开始深度优先搜索。. @4 _* L# P% H! \" o$ V9 @! i& c
) L$ k* x. D1 E8 `7 U% O) A' a& @
整个过程是通过递归实现深度优先搜索,尝试从起始位置到达终点,并记录所有可能的解。在搜索过程中,迷宫中的可行路径被标记为3,死路被标记为2。搜索结束后,会显示解的数量和每个解对应的迷宫状态。$ E" G% C# }' q' J/ Q) ]
! D. ?* Q( b1 u

, M6 X) l5 _% [
$ u8 j3 M( {. C- M( D0 D9 \; H6 C" }6 T7 \
0 Y/ r! ^; d0 I  M
' N: r9 l5 A7 _+ K0 H2 L

深度优先搜索.rar

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

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

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, 2026-6-13 12:07 , Processed in 0.383517 second(s), 54 queries .

回顶部