查看: 2326|回复: 0

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

字体大小: 正常放大

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2023-12-22 17:11 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题

当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：

1.function [total,maze]=search(i,j,maze,total);

2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。

3.fx(1:4)=[0,1,-1,0];

4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。

5.fy(1:4)=[1,0,0,-1];

6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。

7.for k=1:4

8.开始一个循环，遍历四个可能的移动方向。

9.newi=i+fx(k);

10.根据当前位置(i, j)和移动方向计算新的行坐标newi。

11.newj=j+fy(k);

12.根据当前位置(i, j)和移动方向计算新的列坐标newj。

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

14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。

15.maze(newi,newj)=3;

16.将迷宫中新的位置标记为3，表示已经走过。

17.if newi==8&newj==8

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

19.total=total+1

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

22.显示当前的迷宫状态。
23.else

24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);

26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
27.end

28.结束if语句。
29.end

30.结束for循环。
31.maze(i,j)=2;

32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
33.end

34.结束search函数。
35.clear all

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

38.清空命令窗口。
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
40.total=0;

41.初始化解的数量。
42.maze(1,1)=3;

43.将起始位置标记为3，表示已经走过。
44.[total,maze]=search(1,1,maze,total);

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

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