罗密欧与朱丽叶迷宫课程设计报告

1 课程设计报告文档课程设计报告文档 题目 罗密欧与朱丽叶的迷宫问题 一 任务的描述一 任务的描述 1 问题描述 罗密欧与朱丽叶的迷宫 罗密欧与朱丽叶身处一个 m n 的迷宫中 每一个方 格表示迷宫中的一个房间 这 m n 个房间中有一些房间是封闭的 不允许任何人 进入 在迷宫中任何位置均可沿 8 个方向进入未封闭的房间 罗密欧位于迷宫的 p q 方格中 他必须找出一条通向朱丽叶所在的 r s 方格的路 在抵达朱丽 叶之前 他必须走遍所有未封闭的房间各一次 而且要使到达朱丽叶的转弯次数 为最少 每改变一次前进方向算作转弯一次 请设计一个算法帮助罗密欧找出这 样一条道路 对于给定的罗密欧与朱丽叶的迷宫 编程计算罗密欧通向朱丽叶的 所有最少转弯道路 输入数据 第一行有 3 个正整数 n m k 分别表示迷宫的行数 列数和封 闭的房间数 接下来的 k 行中 每行 2 个正整数 表示被封闭的房间所在的行号 和列号 最后的 2 行 每行也有 2 个正整数 分别表示罗密欧所处的方格 p q 和朱丽叶所处的方格 r s 结果输出 将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的 最少转弯道路 文件的第一行是最少转弯次数 文件的第 2 行是不同的最少转弯 道路数 接下来的 n 行每行 m 个数 表示迷宫的一条最少转弯道路 A i j k 表 示第 k 步到达方格 i j A i j 1 表示方格 i j 是封闭的 如果罗密欧无法通 向朱丽叶则输出 No Solution 输入文件示例 4 3 2 1 2 3 4 1 1 2 2 输出文件示例 6 7 1 1 9 8 2 10 6 7 3 4 5 1 2 任务目标 1 确定能对给定的任何位置的罗密欧都能够找到一条通向朱 丽叶的路线 2 程序能够演示一条罗密欧找到朱丽叶的路线过程等 3 运行环境 vc 6 0 二 任务设计二 任务设计 1 系统流程图 程序概要的流程图如下 2 数据初始化 得到罗密欧 位置 沿八个方向 搜索 是否得到一个解 是 否 与当前最优解比 较 适时更新 继续朝其它方 向搜索 是否满足剪枝函数 沿该方向深 度搜索 是 否 2 函数的划分 1 函数 1 void print 调用自动显示函数 au 和动态显示函数 dynamic 输出一条转弯最少的路径 2 函数 2 void search intdep int x int y int di 执行搜索 结果保存在 bestb 二维数组中 供输出使用 3 函数 3 bool consistant int x int y int dep 约束剪枝函数 4 函数 4 void save save 保存找到的最优路线 5 函数 5 int StepOk int x int y 用于判断是否越界和可通过 6 函数 6 void au 自动显示一条路径 7 函数 7 void dynamic 动态显示一条路径 8 函数 8 void init 完成数据输入 3 9 函数 9 int main 主函数 调用 init 和 search 及 print 实现相应 的功能 3 函数之间的关系 从主函数开始运行 调用 init 函数 输入迷宫行数列数封闭房间数 输入罗密欧与朱丽叶坐标后输出迷宫图 然后开始执行搜索函数 search int int int int 进行搜索 在搜索函数中会调用剪枝函数 consistant 和 StepOk 及 保存函数 save 将路径保存在 bestb 矩阵当中 由print 函数调用 au 和 dynamic 函数 将找到的一条路径在屏幕上动态地输出 三 分组情况三 分组情况 本人组长负责执行搜索模块 其他两人分别实现自动显示和动态显示 四 编写代码四 编写代码 1 问题 1 1 问题描述 程序需要处理不同的迷宫大小 2 解决办法 可以预先分配很大的内存空间和动态地分配一个矩阵数组给 予解决 这里采用动态分配方式 提高空间利用率 2 问题 2 1 问题描述 执行搜索时 最少转弯数运行结果不对 2 解决办法 反复检查 没能理解题意 第一步应该可以朝任何方向而都 不算转弯才对 于是在判断是否转弯时 还得判断是否为第一步才行 3 问题 3 1 问题描述 执行效率在迷宫较大且可通过房间数很多时低的难以想象 2 解决办法 通过对搜索过程仔细反复研究 进一步挖掘出限制条件 增 强剪枝功能 当迷宫较大且封闭房间数较多或较密集时 明显提高了搜索效率 五 程序运行五 程序运行 1 自动显示功能 4 5 2 动态显示功能 六 感想认识六 感想认识 通过本次训练 让我体会到这样一个事实 对问题本身掌握的信息越多 就越有可能设计出较好的算法和实现方法 而通用方法比如 万能的 回溯法 必须经过具体问题的改造才有可能得到满意的结果 算法设计也得 拳不离手 曲不离口 否则也会生疏而进展缓慢 参考文献参考文献 1 王晓东 计算机算法设计与分析 第三版 北京 电子工业出版社 2007 5 2 严蔚敏 吴伟民 数据结构 c 语言版 北京 清华大学出版社 2007 3 林华聪 C 语言程序设计思想与实践 北京 冶金工业出版社 2002 4 美 Nicholas A Solter Scott J Kleper 著 C 高级编程 刘鑫 杨建康等译 北京 机械工 业出版社 2006 1 6 附录 源程序 include include include include using namespace std 全局变量 int board 指向访问的标志若以访问记录次序 int bestb 指向一个最优值 int dtp 在动态输出时的辅助数组 int m n k 列 行 封闭房间的数目 int x y 罗密欧的行列号 int x1 y1 朱丽叶的行列号 int count 0 最优解的个数 int best 1000 最优解 int dirs 0 当前最优解 int dx 8 1 1 1 0 1 1 1 0 从该节点依次从左上方开始顺时针搜索 int dy 8 1 0 1 1 1 0 1 1 bool StepOk int x int y 边界函数 没加外围 墙 return x 0 void save 保存函数 for int i 0 i n i for int j 0 j m j bestb i j board i j 连 1 一块保存 bool consistant int x int y int dep 约束剪枝函数 int i 0 j 0 num1 0 num2 0 if StepOk x y board x y 1 假设该节点为活结点 for i 0 i 8 i 从周围八个方向开始考察 if StepOk x dx i y dy i 7 for j 0 j 8 j if StepOk x dx j y dy j num1 统计可选的通道数 if num1 0return false 复位 void search int dep int x int y int di int i if dep m n k 一般约束 else for i 0 i 8 i if StepOk x dx i y dy i if di i search dep 1 x dx i y dy i i if di i 回溯 board x dx i y dy i 0 8 cout 第 dep 层 endl Sleep 3000 void au int i j for i 0 i n i 静态显示迷宫 for j 0 j m j cout width 6 cout bestb i j cout n cout 输出拐弯数 cout best cout n cout 输出路径数 cout count cout n cout 以下自动演示 endl for int a 1 a m n k a for i 0 i n i 静态显示迷宫 for j 0 j m j if bestb i j a 打印出 1 a 的步数 cout width 6 cout bestb i j else cout width 6 cout board i j cout n 9 cout 下一步 n Sleep 1800 void dynamic int i j for int a 1 a m n k a for i 0 i n i for j 0 j m j if bestb i j a 打印出 1 a 的步数 cout width 6 cout bestb i j else cout width 6 cout board i j cout n cout 请按任意键继续 n getchar void print 显示迷宫路径 while 1 cout endl 选择 操作 endl cout 0 退出 endl cout 1 单步 endl cout 2 自动 choose switch choose case 0 return case 1 dynamic break case 2 au break void init 10 ifstream in data txt 测试时间数据 ofstream out result txt int i j int p q cout n m k board new int n bestb new int n dtp new int n for i 0 i n i board i new int m bestb i new int m dtp i new int m for i 0 i n i for j 0 j m j board i j 0 bestb i j 0 cout 输入封闭空间的行列号 n for i 0 i p q board p 1 q 1 1 dtp p 1 q 1