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

2744557306

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题
9 j5 c# n3 O( F  F+ ]
当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：

2 s" _9 q& I) I, U6 }0 D1 Q) ^6 y1.function [total,maze]=search(i,j,maze,total);

7 C% L+ E6 K* \" F. h( `
8 M' Q/ ]2 c5 w- U. R2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。
7 D) j( T2 v) ^7 ]
. E+ T3 p& g7 F+ w& R2 ?
$ `( C) G, O2 {2 b) B3.fx(1:4)=[0,1,-1,0];
- Q) }* y! V; O

4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
7 g3 Z( D$ f) i$ w* a$ F

$ O2 M4 w+ @; @3 K5.fy(1:4)=[1,0,0,-1];
/ C3 i; w$ N( w  U8 r  {
1 W- q  L" E( Z1 s: f  A, `+ u
$ A$ E. w; i5 t& @- U/ h! I3 ~6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。
1 f% @/ [7 r; u$ M2 _

: ^" @2 m1 }$ z7.for k=1:4
4 v- N; m$ H0 a' i. C

6 w# ~8 E* G( W% z8.开始一个循环，遍历四个可能的移动方向。
1 @# z+ I2 T* v' v( A
# V, N+ ]4 G1 m* I$ G) t  U
8 b9 Y; f  k7 {9.newi=i+fx(k);

5 c& C$ ?3 ]8 V1 l: [% r
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。


11.newj=j+fy(k);
4 M! V1 b0 }2 n% Y" k. H7 j0 \
, t: f9 j! L; L. C, t5 ~# L: F
& N- q! w7 l- b12.根据当前位置(i, j)和移动方向计算新的列坐标newj。


13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0

9 i) K5 _- W1 P/ R; R9 v. U
( i% x3 S$ ]4 g1 X  k7 ^( w* n14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。
1 m! D. [. P" W8 s# g

$ K- g. m; h) R( f15.maze(newi,newj)=3;
$ s0 |- G% O1 r
' N% k9 B% r: z& Z) r( V
$ S% L9 D! q9 b16.将迷宫中新的位置标记为3，表示已经走过。
. q9 Z( G! Y+ I' K$ |! [( F

+ \/ f( C# S  O: @17.if newi==8&newj==8
4 c1 g% C3 u2 |' a
! }2 m3 n  y, k( _9 @
! p: k6 ]1 \. W& L5 k18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。

& o9 ^4 d. A: F2 c' w+ M
19.total=total+1

20.增加解的数量。
21.maze

22.显示当前的迷宫状态。
* y3 j5 e, U) \% }6 }4 l, Y5 |2 |9 a5 f23.else
6 C0 G( F: ]% x6 h
24.如果新的位置不是终点，执行下面的语句。
6 N( W* U# O- q5 j: E3 d25.[total,maze]=search(newi,newj,maze,total);

5 }+ U; @6 W, W0 E26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
27.end

28.结束if语句。
29.end
9 u" b3 |1 N# F: ^$ {5 a
9 ^; a8 g4 q, s! e4 \' R2 Q30.结束for循环。
3 u/ r5 f7 a. c2 Q* g& X# D; M* n31.maze(i,j)=2;

32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
33.end
7 P9 F) v9 ^0 L- s6 Z
. r) }$ \, P. G) G9 L34.结束search函数。
8 P: N. o1 `+ V35.clear all

36.清除工作区中的所有变量。
37.clc

38.清空命令窗口。
" I0 f7 M8 n2 J: g) @8 ^' P39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
40.total=0;
( g8 s- q, c# u. J
41.初始化解的数量。
42.maze(1,1)=3;

43.将起始位置标记为3，表示已经走过。
44.[total,maze]=search(1,1,maze,total);
( j* g7 j; D9 o
1 @7 k3 v% |% k5 j1 p# J45.调用search函数开始深度优先搜索。

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





) g% E" W  x0 Q* g5 t# `