数据结构课程设计——迷宫求解问题

数据结构课程设计 迷宫数据结构课程设计 迷宫 实验报告实验报告 任务分配 任务分配 程序员 主要任务 负责整体的算法设计以及程序的主要源代码的编写 测试员 主要任务 负责在程序员每完成一个阶段对程序进行挑错 测试主程序并对 实验结果进行整理分析 最后完成实验报告的第三 四部分即测试结果与分析探讨的 内容 文档员 主要任务 负责对程序及界面的美观提出改善意见 查找程序的小漏洞 负 责撰写实验报告的第一 二部分即实验内容简介与算法描述的内容 同时完成整个文 档的整合 使整篇报告排版 文字风格统一 一 一 简介简介 图的遍历就是从指定的某个顶点 称其为初始点 出发 按照一定的搜索方法对图中 的所有顶点各做一次访问过程 根据搜索方法不同 遍历一般分为深度优先搜索遍历和广 度优先搜索遍历 本实验中用到的是广度优先搜索遍历 即首先访问初始点 vi 并将其标记为已访问过 接着访问 vi的所有未被访问过的邻接点 顺序任意 并均标记为已访问过 以此类推 直 到图中所有和初始点 vi有路径相通的顶点都被访问过为止 鉴于广度优先搜索是将所有路 径同时按照顺序遍历 直到遍历出迷宫出口 生成的路径为最短路径 因此我们采用了广 度优先搜索 无论是深度优先搜索还是广度优先搜索 其本质都是将图的二维顶点结构线性化的过 程 并将当前顶点相邻的未被访问的顶点作为下一个顶点 广度优先搜索采用队列作为数 据结构 本实验的目的是设计一个程序 实现手动或者自动生成一个 n m 矩阵的迷宫 寻找一 条从入口点到出口点的通路 具体实验内容如下 选择手动或者自动生成一个 n m 的迷宫 将迷宫的左上角作入口 右下角作出口 设 0 为通路 1 为墙 即无法穿越 假设一只老鼠从起点出发 目的为右下角终点 可 向 上 下 左 右 左上 左下 右上 右下 8 个方向行走 如果迷宫可以走通 则 用 代表 1 用 代表 0 用 代表行走迷宫的路径 输出迷宫原型图 迷宫路线图以及迷宫行走路径 如果迷宫为死迷宫 则只输出迷宫原型图 二 二 算法说明算法说明 根据实验内容 本实验主要设计实现手动输入迷宫 判断迷宫能否走通 自动生成迷 宫 判断迷宫能否走通 迷宫算法的整体思想如下 1 迷宫的创建 迷宫中存在通路和障碍 为了方便迷宫的创建 可用 0 表示通路 用 1 表示障碍 这 样迷宫就可以用 0 1 矩阵来描述 设置迷宫的长为 n 宽为 m 范围为 49 49 用int maze N 2 M 2 来表示 这样相当于在迷宫外层包了一层 1 即防止搜索路径时跳出迷宫 1 手动生成迷宫 void hand maze int m int n 手动生成迷宫 int i j for i 0 i m i for j 0 j maze i j 2 自动生成迷宫 void automatic maze int m int n 自动生成迷宫 int i j for i 0 i m i for j 0 j n j maze i j rand 2 随机生成 0 1 maze 0 0 0 将开始和结束位置强制为 0 保证有可能出 来迷宫 maze m 1 n 1 0 2 迷宫路径的搜索 在生成的 0 1 矩阵迷宫中 首先从迷宫的入口开始 如果该位置就是迷宫出口 则已 经找到了一条路径 搜索工作结束 否则搜索其北 1 0 东北 1 1 东 0 1 东南 1 1 南 1 0 西南 1 1 西 0 1 西北 1 1 8 个方向位 是否 是障碍 若不是障碍 就移动到该位置 然后再从该位置开始搜索通往出口的路径 若是 障碍就选择另一个相邻的位置 并从它开始搜索路径 为防止搜索重复出现 则将已搜索 过的位置标记为 2 同时保留搜索痕迹 在考虑进入下一个位置搜索之前 将当前位置保 存在一个队列中 如果所有相邻的非障碍位置均被搜索过 且未找到通往出口的路径 则 表明不存在从入口到出口的路径 这实现的是广度优先遍历的算法 如果找到路径 则为 最短路径 逆序输出路径 将已输出的路径标记为 3 实验数据如下 列列 行行0123 00101 10010 21010 31100 算法如下 int path int maze 51 51 int m int n 路径求解 X 1 初始值定为 1 struct point p 0 0 1 定义入口节点 if maze p row p col 1 入口为 1 时 迷宫不可解 cout 0 东北 if p row 0 m 东 if p row 1 m 东南 if p row 1 m 南 if p row 1 m 西南 if p row 0 m 西 if p row 1 0 西北 if p row m 1 123456789 0 0 1 1 1 0 0 2 2 1 1 3 3 2 2 3 3 3 111223456 cout 出口 endl cout endl printf d d n p row 1 p col 1 cout endl maze p row p col 3 逆序将路径标记为 3 while p predecessor 1 p queue p predecessor printf d d n p row 1 p col 1 cout endl maze p row p col 3 cout 入口 endl else cout 此迷宫无解 n n X 0 return 0 3 输出迷宫图 1 生成迷宫图 将迷宫外壳输出为 将迷宫中的 0 输出为 将 1 输出为 for k 0 k n k cout 这两个黑三角用来生成顶部外壳 for i 0 i m i cout n cout 生成左外壳 for j 0 j n j if maze i j 0 cout if maze i j 1 cout cout 生成右外壳 cout endl for k 0 k n k cout cout n 生成底部外壳 2 生成迷宫路径图 for i 0 i m i cout n for j 0 j n j if maze i j 0 maze i j 2 2 是队列中访问过的点 cout if maze i j 1 cout if maze i j 3 3 是标记的可以走通的路径 cout 3 总界面的实现 考虑到添加画图部分 对我们的原程序改动较大 因此我们没有采用画图画线输出迷 宫路径 同时 我们也扩充了迷宫的功能 可以定义任意宽度和长度的迷宫并实现手动 自动生成迷宫等功能 输出界面有三个选项 1 为手动生成迷宫 2 为自动生成迷宫 3 为推出程序 当程序 运行时 设 cycle 为 0 当选择 3 退出程序时 cycle 为 1 void main int i m n cycle 0 while cycle 1 switch i case 1 手动输出迷宫 cout m cout n cout n while m49 n49 cout n 抱歉 你输入的行列数超出预设范围 0 49 0 49 请重新输入 n n cout m cout n cout n shoudong maze m n data m n print maze m n mgpath maze m n if X 0 result maze m n cout n nPress Enter Contiue n getchar while getchar n break case 2 自动输出迷宫 cout m cout n cout n while m49 n49 cout n 抱歉 你输入的行列数超出预设范围 0 49 0 49 请重新输入 n n cout m cout n cout n zidong maze m n data m n print maze m n mgpath maze m n if X 0 result maze m n cout n nPress Enter Contiue n getchar while getchar n break case 3 程序退出 cycle 1 break default 其他情况时 输出有误 cout n cout 你的输入有误 n cout nPress Enter Contiue n getchar while getchar n break 三 三 测试结果测试结果 本设计采用广度优先的算法 实现迷宫的路径求解 在原要求的基础上 加以扩展 实现要求范围内的 N N N M 的手动 自动生成迷宫矩阵的求解 一 基本功能测试 1 手动迷宫 1 N N 迷宫路径求解 a 4 4 迷宫矩阵 0 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 运行后 判定为有解迷宫 输出如下 运行后 判定为无解迷宫 输出如 下 对符号解释的放置 对 1 墙的解释 b 7 7 迷宫矩阵 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 运行后 判定为有解迷宫 输出如下 运行后 判定为无解迷宫 输出如 下 1 N M 迷宫路径求解 N M a 4 6 迷宫矩阵 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 运行后 判定为有解迷宫 输出如下 运行后 判定为无解迷宫 输出如下 b 5 3 迷宫矩阵 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 运行后 判定为有解迷宫 输出如下 运行后 判定为无解迷宫 输出如下 2 自动迷宫 1 N N 迷宫路径求解 5 5 迷宫矩阵 测试次数第一次第二次第三次 生成迷宫 判断结果 2 N M 迷宫矩阵测试 N M 6 8 迷宫矩阵 测试次数第一次第二次第三次 生成迷宫 判断结果 二 广度优先搜索 BFS 测试 多通路迷宫折取最优 1 课本实例 P68 测试用例 1 输出迷宫 输出结果 2 自行设计手动输入迷宫 测试迷宫 全部路径展示 测试结果 四 分析与探讨四 分析与探讨 第三部分中 展示了程序所实现的各种情况 下面从程序源代码的角度来进一步分析 各算法的时间复杂性 1 程序分析 1 手动生成迷宫算法 void hand maze int m int n int i j cout endl cout 请按行输入迷宫 0 表示通路 1 表示障碍 endl for i 0 i m i for j 0 j maze i j 可以看出 该算法的时间复杂度为 T N O N2 因此 这是一个线性算法 随着 N 的 增加 算法的时间复杂度线性增加 2 自动生成迷宫算法 void automatic maze int m int n 自动生成迷宫 int i j cout n 迷宫生成中 n n system pause for i 0 i m i for j 0 j n j maze i j rand 2 随机生成 0 1 maze 0 0 0 maze i 1 j 1 0 首尾置为 0 保证迷宫基本功能的实现 时间复杂性 度上 该算法同于手动生成迷宫算法 为 T N O N2 也是一 个线性算法 随着 N 的增加 算法的时间复杂性增加 3 输出迷宫的星号路径算法 void result maze int m int n 打印输出迷宫的星号路径 int i j printf 迷宫通路 用 表示 如下所示 n t for i 0 i m i printf n for j 0 j n j if maze i j 0 maze i j 2 printf if maze i j 1 printf if maze i j 3 printf 2 程序讨论 1 在程序编写的过程中 我们发现了很多问题及错误 例如 程序刚形成雏形时 经测试 程序只能实现课本要求的 8 8 的迷宫矩阵寻路 并且会出现寻路时跳出迷宫的情 况 因此 程序员在此基础上 将迷宫矩阵数组由原来的 maze 10 10 改为 maze N 2 M 2 并在相应函数上加以大量改动 最终使本程序实现了程序本身范围内的任意 N M 迷宫矩阵 组合的寻路求解 2 在输出界面上 起初 仅仅是将最终结果展示 而无矩阵的规范输出 即如果使 用者手输出迷宫时 并未整齐的输入迷宫 如果此时显示迷宫最后的路径 使使用者不易 清晰的看出路径而难以理解 基于站在使用者的角度 加入了 data 函数 实现了数组 符 号 数位路径 字符路径共同出现的最终界面 并在输出时添加相应的箭头指示 在输出 的迷宫图时将最外层加入的围墙用 表示 经多次修改 使得输出界面整洁大方 3 在最开始判断搜索方向的时候 我们列出的八个方向并未按照一定顺序搜索 此 时就会出现错误 后来采用一定顺序来完成迷宫的搜索 因为设定迷宫的入口在左上方 出口在右下方 所以采用顺时针方向比采用逆时针方向能最先找出最短路径 所以最后采 用了顺时针的搜索方向 即沿北 东北 东 东南 南 西南 西 西北八个方向搜索 4 在测试输出结果方面 出了一个困扰我们一阵时间的问题 在以 5 7 自动生成迷 宫矩阵的测试过程中 几乎每隔几次都会出现一次这样类似的问题 见下图 在下图的输 出界面 以及字符展示界面中 经过简单的分析 便可以得出最后通往出口的道路 但在程序判断 并输出路径后 在图中可以看到 五角星所标记的走过的路 在出口处出现了错误 但是 此程序手动输入的时候不会出现任何错误 所以问题锁定在自动生成迷宫函数中 在此 我们列出当时的自动生成迷宫函数 void automatic maze int m int n int i j cout n 迷宫生成中 n n system pause for i 0 i m i for j 0 j n j maze i j rand 2 maze 0 0 0 maze i 1 j 1 0 将此问题反映给了程序员 在修改过程中 反复分析了各个函数后将问题锁定在自动 生成函数处 观察此函数 发现 maze i 1 j 1 0 是导致问题的最终所在 该语句的初 衷是将迷宫矩阵中最初一个数判定为 0 防止出现迷宫出口不通的情况 在这儿以 5 7 迷 宫为例 经过分析 当跳出 for 循环时 i 5 j 6 而要改变的数是 maze 5 7 而非 maze 5 6 这也就是导致上图所示结果的原因 将该语句改为 maze m 1 n 1 问题解决 3 程序的前景展望及感想 由于时间匆忙 还有很多功能未能实现 例如 自动生成迷宫时经常出现无解迷宫 加以改进的话 希望可以实现当自动生成的迷宫无解时 可以自动搜索直到出现有解迷宫 或者我们可以实现操作者可以自己手动输出迷宫路径等等 在整个程序设计的几天里 我们三个同学分工明确 共同设计讨论程序 经过多方改 进与完善 最终完成了此次迷宫的设计 附录附录 源代码源代码 include 库中包含 system pause 和 rand 函数 include c 语言里的库 include using namespace std define N 49 定义为全局变量 这是迷宫数组的上线 可以自行修 改 define M 49 int X int maze N 2 M 2 int head 0 tail 0 队列的头尾指针 初始值设为 0 struct point 存放迷宫访问到点的队列结构体 包含列 行 序号 int row col predecessor queue 1200 void hand maze int m int n 手动生成迷宫 int i j cout endl cout 请按行输入迷宫 0 表示通路 1 表示障碍 endl for i 0 i m i for j 0 j maze i j void automatic maze int m int n 自动生成迷宫 int i j cout n 迷宫生成中 n n system pause for i 0 i m i for j 0 j n j maze i j rand 2 随机生成 0 1 maze 0 0 0 将开始和结束位置强制为 0 保证有可能出来迷宫 maze m 1 n 1 0 void data int m int n 当用户输入的不是规整的 m 行 n 列的迷宫 用来生成规则的数字迷 宫 int i j cout endl cout 根据您先前设定的迷宫范围 endl cout endl cout 我们将取所输入的前 m n 个数生成迷宫 endl cout n 数字迷宫生成结果如下 n n cout 迷宫入口 n cout for i 0 i m i cout n for j 0 j n j if maze i j 0 cout 0 if maze i j 1 cout 1 cout 迷宫出口 n void print maze int m int n 打印迷宫外壳 int i j k cout n 字符迷宫生成结果如下 n n cout 迷宫入口 n cout cout endl cout 生成上外壳 for k 0 k n k cout 这两个黑三角用来生成顶部外壳 for i 0 i m i cout n 生成左外壳 cout for j 0 j n j if maze i j 0 printf if maze i j 1 printf cout 生成右外壳 cout endl for k 0 k n k cout cout n 生成底部外壳 for i 0 i n i cout cout n for i 0 i n i cout cout 迷宫出口 n void result maze int m int n 这个是打印输出迷宫的星号路径 int i j cout 迷宫通路 用 表示 如下所示 n t for i 0 i m i cout n for j 0 j n j if maze i j 0 maze i j 2 2 是队列中访问过的点 cout if maze i j 1 cout if maze i j 3 3 是标记的可以走通的路径 cout void enqueue struct point p 迷宫中队列入队操作 queue tail p tail 先用再加 队列尾部加 1 struct point dequeue 迷宫中队列出队操作 不需要形参 因此用结构体定 义 head return queue head 1 int is empty 判断队列是否为空 return head tail void visit int row int col int maze 51 51 访问迷宫矩阵中的节点 struct point visit point row col head 1 head 1 的作用是正在访问的这个点的序号为之前的点序 号 maze row col 2 将访问过的点位标记为 2 enqueue visit point 入队 int path int maze 51 51 int m int n 路径求解 X 1 初始值定为 1 struct point p 0 0 1 定义入口节点 if maze p row p col 1 入口为 1 时 迷宫不可解 cout n n cout 0 东北 if p row 0 m 东 if p row 1 m 东南 if p row 1 m 南 if p row 1 m 西南 if p row 0 m 西 if p row 1 0 西北 if p row m 1 cout 迷宫路径为 n cout 出口 endl cout endl printf d d n p row 1 p col 1 cout endl maze p row p col 3 逆序将路径标记为 3 while p predecessor 1 p queue p predecessor printf d d n p row 1 p