数据结构课程设计-马踏棋盘分解

学学 号 号 2012812044 杭州师范大学 钱江学院 课课 程程 设设 计计 题题 目目 马踏棋盘算法研究马踏棋盘算法研究 教教 学学 院院 信息与机电工程分院信息与机电工程分院 专专 业业 计算机科学与技术计算机科学与技术 班班 级级 计算机计算机 12011201 姓姓 名名 吴秋浩吴秋浩 指导教师指导教师 王李冬王李冬 2013 年12 月21日 目目 录录 一 概述 2 二 总体方案设计 3 三 详细设计 4 四 最终输出 5 五 课程设计总结 6 参考文献 7 一一 概述概述 1 课程设计的目的课程设计的目的 1 课题描述 设计一个国际象棋的马踏遍棋盘的演示程序 2 课题意义 通过 马踏棋盘 算法的研究 强化了个人对 栈 数据结构的定义和 运用 同时也锻炼了自身的 C 语言编程能力 另一方面 通过对 马踏棋盘 算法的研究 个人对 迷宫 棋盘遍历 一类的问题 有了深刻的认识 为今后解决以此问题为基础的相关的问题 打下了坚实的基础 3 解决问题的关键点说明 解决问题的关键首先要熟练掌握 C 语言编程技术 同时能够熟练运用 栈 数据结构 另外 态度也是非常重要的 在课程设计过程中 难免会 遇到困难 但是不能轻易放弃 要肯花时间 能静得下心 积极查阅相关资 料 积极与指导老师沟通 2 课程设计的要求课程设计的要求 1 课题设计要求 将马随机放在国际象棋的 8 8 棋盘 Board 0 7 0 7 的某个方格中 马按走棋规则进行移动 要求每个方格只进入一次 走遍棋盘上全部 64 个 方格 编制非递归程序 求出马的行走路线 并按求出的行走路线 将数字 1 2 64 依次填入一个 8 8 的方阵 输出之 程序由回溯法和贪心法实现 比较两种算法的时间复杂度 2 课题设计的思路 首先 搞清楚马每次在棋盘上有 8 个方向可走 定义两个一位数组 来 存储马下一着点的水平和纵向偏移量 程序再定义一个 8 8 二维数组 初始 所有元素置 0 起始点元素置 1 若为回溯法 初始方向数据 一维数组下 标 入栈 随后 马从起始点开始 每次首先寻找下一可行的着点 然后记 下方向 方向数据入栈 把该位置元素置为合适的序列号 若无下一可行着 点 则回溯 寻找下一方向位置着点 以此类推 直到 64 填入数组中 则 输出二维数组 即为马可走的方案 若为贪婪法 选择下一出口的贪婪标准 是在那些允许走的位置中 选择出口最少的那个位置 直到没有下一着点位 置 若此时已标记到 64 则找到可行方案 输出之 反之 改变初始寻找方 向继续寻找 直到 8 种方向顺序都试过 若还是没有合适的方案 则说明以 该起始 点开始马无法踏遍棋盘 二二 总体方案设计总体方案设计 1 1 回溯法回溯法 算法思想 按深度优先策略 从一条路往前走 能进则进 不能进则退回来 换一条路再 试 也就是说每当前进的路不通 我们总是返回到前一次的岔路口 选择下一条新 的路线 1 函数头文件定义和宏定义 include include define N 8 便于改变棋盘大小 2 栈数据结构定义 typedef struct int b N N 记录每次走的方向 int top 栈指针 SqStack 3 定义探寻路径函数 Board N N 模拟 N N 棋盘 填入 1 2 3 64 x y 传递初始位置 bool HorsePath int Board N int x int y 初始化栈 定义方向数组 int xx 8 1 2 2 1 1 2 2 1 int yy 8 2 1 1 2 2 1 1 2 初始方向下表入栈 回溯法开始寻找合适方案 详见 详细设计 4 定义主函数 void main 定义基本变量及 Board N N 数组 输入初始位置 x0 y0 调用 HorsePath Board x0 y0 输出方案 2 2 贪心法贪心法 算法思想 从问题的某一个初始解出发逐步逼近给定的目标 以尽可能快的地求得更好的 解 当达到某算法中的某一步不能再继续前进时 算法停止 该算法存在问题 1 不能保证求得的最后解是最佳的 2 不能用来求最大或最小解问题 3 只能求满足某些约束条件的可行解的范围 1 函数头文件定义和宏定义 include define N 8 便于改变棋盘大小 2 程序要用到的一些全局变量的定义 int xx 8 1 2 2 1 1 2 2 1 int yy 8 2 1 1 2 2 1 1 2 控制马能走的 8 个方向 int Board N N 0 初始棋盘所有位置可走 3 定义 FeassiblePath 计算每个点的后续着点个数 int FeassiblePath int x int y int start 函数体 详见 详细设计 4 定义 NextPath 找出一个着点的后续着点中可走方位最少的 把着点到后续 点的方向记下返回主函数 int NextPath int x int y int start 函数体 详见 详细设计 5 定义主函数 void main 输入初始位置 x0 y0 定义变量整型变量 start 控制起始 8 种方向 While start 8 循环调用 NextPath x0 y0 start 找到方案 则输出之 start 三三 详细设计详细设计 1 1 回溯法回溯法 马踏棋盘马踏棋盘 演示程序演示程序 include include define N 8 typedef struct int b N N 记录每次走的方向 int top SqStack bool HorsePath int Board N int x int y SqStack s s SqStack malloc sizeof SqStack 初始化栈 s top 1 int xx 8 1 2 2 1 1 2 2 1 int yy 8 2 1 1 2 2 1 1 2 控制马能走的 8 个方向 int p 0 s top s b s top p while s top 1 Board x y s top 1 找到方案 则输出之 if Board x y N N return true while p 0 s b s top p p 0 break p if p 8 Board x y 0 x xx s b s top y yy s b s top p s b s top 1 s top return false 循环结束 未找到合适方案 void main bool flag int x0 y0 i j int Board N N 0 设置开始每一格都可走 printf 请输入马的起始位置 x y n 注 0 x d 0 y d N N while scanf d d else break flag HorsePath Board x0 y0 if flag false printf 无法遍历 n else printf 一种可行的方案为 n for i 0 i N i for j 0 j N j printf t d Board i j printf n n z 2 2 贪心法贪心法 马踏棋盘马踏棋盘 演示程序演示程序 include define N 8 int xx 8 1 2 2 1 1 2 2 1 int yy 8 2 1 1 2 2 1 1 2 控制马能走的 8 个方向 int Board N N 0 初始棋盘所有位置可走 计算每个点的后续着点个数 int FeassiblePath int x int y int start int count 0 i 0 p k k start while i 0 k i return count 找出一个着点的后续着点中可走方位最少的 把着点到后续着点的方向记下返 回主函数 int NextPath int x int y int start int min 9 i 0 num p k f k start while i 0 f k 8 k i if min 9 return 1 return f 后续着点的方向记下返回主函数 void main int i j x0 y0 start 0 flag sign 0 printf 请输入马的起始位置 x y n 注 0 x d 0 y d N N while scanf d d else break Board x0 y0 1 while start 8 如果一种起始方位无法遍历 改变方位 再次寻找 i x0 j y0 for int step 2 step N N step flag NextPath i j start if flag 1 i xx flag j yy flag Board i j step else break 若找到一种方案 则输出之 if step N N 1 sign 1 printf 一种可行的方案为 n for i 0 i N i printf t for j 0 jtop 1 循环 同时这个循环内部还有一个 while p 8 的循环 由回溯算法的思想 我们可知这个外循环的时间复杂度相当大 故整个程序的时间复杂度也很大 如果 n 个数比较小的时候或许能够较快地显示结果 但随着问题规模的增大 当 n 8 时 T n 简直可以用天文数字来形容 在 windows 操 作系统下 有时候要等几十分钟 甚至更久才能出结果 显然 我们得追寻更优化的 算法 2 2 贪心法贪心法 1 程序正确输入下运行结果 2 贪心法求解的时间复杂度分析 设问题的规模为 n 即棋盘的的大小为 n n 由贪婪算法可知选择下一出口的贪婪 标准是在那些允许走的位置中 选择出口最少的那个位置 显然 影响程序运行时间 的基本运算是在寻找出口最少的位置 由程序我们可知 T n O n 2 显然贪心算法的时间复杂度小多了 即使棋盘的大小是 8 8 想要搜索任意起始点 下的可行方案 一秒钟内就可以输出结果 3 回溯法和贪心法的比较 回溯法求解马踏棋盘 思想简单易懂 能够一次性得到所有可能的情况 但是算法 时间复杂度过大 在棋盘大小过大时 不推荐采用 贪心法 思想也是比较容易让人 理解的 同时 算法的时间复杂度为 O n 2 能够较快地找出一种复合要就的方案 但 是利用贪心法不便于得到所有的可行方案 五五 课程设计总结课程设计总结 此次数据结构课程设计的课题是设计一个国际象棋的马踏遍棋盘的演示程序 在刚开始选课题时 我就被 马踏棋盘 这几个字深深地吸引了 虽然那是我第一 次听说这个名词 但我还是选择了 马踏棋盘 于是我便开始在网上搜集关于 马踏棋盘 的内容 然后我知道了 马踏棋盘 算法的要求 由于在数据结构课 上学习过利用栈来求解迷宫问题 所以第一时间我就想到了利用栈来求解这个问题 也就是利用回溯法求解 虽然很快我写出了 回溯法求解的源程序 可是当我运行 程序时 出现的现象使我很惊讶 对于一个 8 8 的棋盘 输入不同的起始点 得到 结果的时间不同 例如输入 0 0 较快的得到了结果 但是输入 1 1 我等了几 十分钟 依旧没有等到实验结果的出现 这时 我开始思考 一定有更优化的算法 存在 为了较快得到实验结果 我又开始在网上搜索 然后我得知了利用贪心法能 够大大提高程序运行的效率 因为该算法选择下一出口的贪婪标准是在那些允许走 的位置中 选择出口最少的那个位置 直到没有下一着点位置 于是 我又用贪心 法实现了 马踏棋盘 演示程序 在此次课程设计中我一直想尝试一次输出所有的 马踏棋盘 方案 并记录方案的个数 虽然用回溯法实现了对 5 5 等小规模棋盘 马踏遍棋盘所有方案的输出 但是对于 8 8 的棋盘 问题规模过大 无法在短时间 内得到所有的方案 我也曾想过用贪心法实现 马踏棋盘 所有方案的一次性输出 但是我觉得如果要用贪心法得到 马踏棋盘 所有方案 需要循环对每一着点的后 继可行着点进行尝试遍历 这样就违背了贪心法 选择下一出口的贪婪标准是在那 些允许走的位置中 选择出口最少的那个位置 这一标准 这样做就会失去贪心法 本身的优点 反而使程序时间复杂度加大