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

2744557306

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
, [, m" G' f- h
当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
! }, ^/ H9 O) v- p; X
1.function [total,maze]=search(i,j,maze,total);

  G" L8 n! w8 |6 T/ z! J
  `" S4 T1 B: D- _2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。


8 L0 L. }, z% ~$ L, K* J3.fx(1:4)=[0,1,-1,0];

5 n* N, k; T; Y. r+ T
4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。


& _7 p9 {; W5 Z, I% J5.fy(1:4)=[1,0,0,-1];
* Y6 ?$ Q/ i% ]* t
& E8 ^  M2 ~1 ?, s1 c
6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
% j; b2 ^# j+ Z1 N
# h. ]' i2 e- c! b
+ O: ^8 H" j5 x. ]7.for k=1:4
' J" V: c4 D  c/ m9 y9 f3 `& J4 B

+ D& n+ G3 N, w4 X& \8.开始一个循环，遍历四个可能的移动方向。
0 c" Y1 i2 _2 T* t9 e2 ]

- _8 @/ ?/ T' e( n% e9.newi=i+fx(k);

4 L  Y& V" v$ I# E
: ^. ~* ~3 A! V10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
6 n" L5 v' d) X6 \  G3 N
9 D6 Z8 `4 A5 a6 J* I9 {( V
11.newj=j+fy(k);
! b! i5 o# b! F, M# R
+ ]5 N7 g2 _5 [/ x! B4 S3 w8 Q
12.根据当前位置(i, j)和移动方向计算新的列坐标newj。


" F+ _8 k( X. B13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0

8 l# J' A+ q6 ?- F4 y
0 K7 S- d+ u4 C5 B4 f14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
% r' |6 s+ z9 |! n
& t& R7 U9 |% }
8 I. V1 ~# {: h! R% q  v) I15.maze(newi,newj)=3;
8 A' U5 }' D3 @2 [$ v7 w

3 F* ?' b3 b; q. w16.将迷宫中新的位置标记为3，表示已经走过。
. h, E: Y( o, e$ A+ {5 d' T$ `
% x# x$ N$ N- D- q
4 s, m/ D% R  h7 j+ l) {4 \: m17.if newi==8&newj==8


18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。

; R5 k% {1 t- g
9 U$ n7 c1 j3 R7 l  {  `% @19.total=total+1
: b4 w) \, J- S# A/ `7 y
20.增加解的数量。
7 q5 S# x0 j# i( L3 L21.maze

9 M6 q- t  W* t5 X( F7 o& y8 E0 v22.显示当前的迷宫状态。
6 E: D5 f/ N) x: [- I# ?3 {6 @23.else
: z$ s; m$ m% C4 y2 U# U0 U7 N
$ \* f& `' G- {; z! C( I. S# }: C24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);

26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
! M2 Q5 Z. r2 |1 @27.end
1 L7 e. d' u0 ]* i  f
28.结束if语句。
29.end
" o5 d; i0 }& Q5 S
  Q) V! A% g; I5 g0 m- S: N  T+ @30.结束for循环。
31.maze(i,j)=2;

32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
5 l! G1 h5 Q$ @' g- ^! g33.end
* i& `- W8 s: @3 z3 r/ K8 s. n
5 O! ^& t2 ]; m1 j34.结束search函数。
35.clear all

8 c% g/ D2 S, m8 M/ }$ k0 V8 G36.清除工作区中的所有变量。
37.clc
+ [$ I4 e2 _* x/ w/ z( G7 Q" v  p
38.清空命令窗口。
9 G; f- |' I& l' M3 W39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
$ [1 u" G* [: q6 ^3 j! L3 d" _& K40.total=0;
4 u4 }7 E/ S9 s8 l: g0 U
41.初始化解的数量。
& N% {/ f3 R' X* K8 Y42.maze(1,1)=3;
! C9 n4 S2 d4 c  E, \( W+ `& p
2 Z; x) i/ F% W: |% W4 \43.将起始位置标记为3，表示已经走过。
44.[total,maze]=search(1,1,maze,total);

45.调用search函数开始深度优先搜索。

1 X7 M2 s5 O6 g2 Q- ?" {( a& Q整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。


: p1 G! V$ A9 b2 m( P2 N

( r- f  F; k/ V$ A' Y2 k3 F