《打猎问题课程设计》由会员分享,可在线阅读,更多相关《打猎问题课程设计(17页珍藏版)》请在金锄头文库上搜索。
1、沈阳航空沈阳航空航天大学航天大学 课课 程程 设设 计计 报报 告告 课程设计名称:数据结构课程设计数据结构课程设计 课程设计题目: 打猎问题打猎问题 院(系):计算机学院 专 业:计算机科学与技术 班 级:、 学 号: 姓 名: 指导教师: 目目 录录 1 1 需求分析需求分析.1 1.1 问题描述1 1.2 问题理解1 2 2 系统设计系统设计.3 2.1 总体方案设计3 2.2 数据结构设计3 2.3 函数设计4 2.4 关键流程4 2.4.1 系统主流程4 2.4.2 最大匹配函数流程.6 2.4.3 查找增广路径函数流程.6 3 3 调试分析调试分析.8 4 4 测试及运行结果测试及
2、运行结果.9 参考文献参考文献.11 附附 录录.12 1 1 需求分析需求分析 1.11.1 问题描述问题描述 猎人要在 n*n 的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有 鸟都被打掉,也可以在某一列中打,这样此列中的所有鸟都打掉。问至少打几枪, 才能打光所有的鸟?利用二分图中的最大匹配数等于该图的最小点覆盖数来求解。 建图:二分图的 X 部为每一行,Y 部为每一列,如果(i,j)有一只鸟,那么连接 X 部的 i 与 Y 部的 j。主要使用二维数组来建立二分图的表示关系;如图 1.1 所示: 图 1.1 关系示意图 数组元素的值为 1 表示二分图的 X 部的 i 与 Y 部的 j
3、 相连;表示(i,j)有 一只鸟。而数组元素值为 0 时,表示二分图的 X 部的 i 与 Y 部的 j 不相连;表示 (i,j)没有鸟。 1.21.2 问题理解问题理解 本题主要是用到了二分图求最大匹配数等于最小覆盖点来求解;解决二分图 最大匹配的经典算法为匈牙利算法。算法的核心就是根据一个初始匹配不停的找 增广路,直到没有增广路为止。简单讲,增广路是一条交互道路,其中非匹配边 与匹配边交替出现,并且起点与终点都没匹配。 如图 1.2 所示: 图 1.2 匹配图 上图中 红边 为已匹配的边, 黑边为没匹配,则图中的增广路有: 1) x5- y5- x4- y4- x3- y2 2) x2- y
4、4- x3- y2 可以得出, 增广路有奇数条边,匹配边与非匹配边交替,顶点和终点未匹配,对 于这样的增广路,我们可以通过将匹配边变成非匹配边,将非匹配边变成匹配边 从而增加一条匹配 如: x5- y5- x4- y4- x3- y2 经过变换后,变成如下图,增加了一条匹 配边 图 1.3 转化后的匹配 这时图中已经没有了增广边,已经达到了最大匹配。另外可以证明,对于点 x , 如果求得了以 x 为起点的增广路径后,不管以后怎么改变,都将不会再有以 x 为起点的增广路径。 2 2 系统设计系统设计 2.12.1 总体方案设计总体方案设计 首先就是要建立一个二分图(即是建立一个 n*n 的格子)
5、 ,用二维数组建立 这个格子,以相应的的值代表某个位置上是否有鸟,例如:用 1 代表有鸟,用 0 代表没有鸟。根据所掌握的知识可知要用经典的求最大匹配的匈牙利算法来解决 这个问题。 2.22.2 数据结构设计数据结构设计 在程序中主要用到了数组,特别是二维数组,用二维数组来建立一个邻接矩 阵表示二分图中 X 部的 i 与 Y 部的 j 的关系。如果 i,j 相连则数值为 1;否则为 0;具体关系如图 2.1: 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 图 2.1 邻接矩阵 表示 X 与 Y 的关系如图 2.2: 图 2.2 X 与 Y 关系图 X1 X2 X4 X3 Y2
6、 Y3 Y1 Y4 2.32.3 函数设计函数设计 1本系统所设计的函数见表 2.1。 表 2.1 函数列表 函数名称函数原型功能描述 main void main();系统主程序 find int find(int i,int m,int gN,int mat,int tmat); 查找增广路径 match int match(int gN,int n,int m,int mat); 求解最大匹配 outputvoid output(aM); 输出邻接矩阵 2本系统函数的调用关系见图 2.3。 main outputmatch find 图 2.3 函数调用关系 2.42.4 关键流程关键流
7、程 2.4.12.4.1 系统主流程系统主流程 (1)主函数的简单描述 在主函数中最主要是用二维数组建立了二分图的邻接关系,之后是调用输出 函数来输出邻接关系矩阵;再之后再调用求最大匹配函数来求解;最终求得结果; (2)主函数的流程图 本函数的具体流程见图 2.4,j,k 是定义的变量;n,m 是定义的行和列;a 是表示邻接关系的二维数组; int i,j,k; scanf(“%d%d“, in i=0 j=0 jm scanf(“%d“, j+ i+ printf(“输出邻接矩阵n“); return0; N Y N Y N Y 结束 开始 图 2.4 主函数的流程图 2.4.22.4.2
8、最大匹配函数流程最大匹配函数流程 (1)查找最大匹配函数的简单描述 最大匹配函数主要是利用已知任意匹配不断地寻找增广边,直到再也找不到 为止;最终找到的匹配就是最大匹配; (2)查找最大匹配函数的流程图 本函数的具体流程见图 2.5 ,i,k,j 是定义的变量;cmat,mat 是标记数组; clr(a)是清零的宏定义; int i,k=0,cmatN; i=0 im mati=-1;i+; i=0 in clr(cmat);i+; return k; N Y N Y 结束 开始 图 2.5 查找最大匹配函数的流程图 2.4.32.4.3 查找增广路径函数流程查找增广路径函数流程 (1)查找增
9、广路径函数的简单描述 设已有的匹配为 M,它的第一条边不在 M 中,最后一条边也不在 M 中,中间 为在 M 中的边与不在 M 中的边交错出现。所以我们若对增广路中的边进行取反, 则我们能获得一个更大的匹配。所以这么一直找下去,直到找不到增广路为止。 (2)查找增广路径函数的流程图 本函数的具体流程见图 2.6,其中 v,j 是定义的变量;m 是代表列数;cmat 是标记数组;find 本身函数; int v,j=0; jm gij v=-1|find(v,m,g,mat,cmat) return 1; matj=v; j+ return 0; N Y N Y N Y 开始 结束 图 2.6
10、查找增广路径函数的流程图 3 3 调试分析调试分析 (1) 问题 1 问题描述: 数组 cmat 没有清零; 问题分析:如果不清零的话,数值将保存,会影响下一步的执行; 解决方法:用宏定义来实现清零功能;memset(a,0,sizeof(a) ) 。 (2) 问题 2 问题描述:在 match 函数中的 for 循环中套用 find 函数时出错了。 问题分析: find 函数应该再循环中。 解决方法: 将 find 函数加入到 for 循环里。 (3) 问题 3 问题描述:在 find 函数中调用本身时没有写在判断条件里。 问题分析: 如果在判断条件里没有调用 find 本身将会导致条件不足
11、而产生 错误; 解决方法:在 if 判断中加入调用本身函数的语句即可。 4 4 测试及运行结果测试及运行结果 (1) 格子行和列的输入见图 4.1。 图 4.1 行和列的输入 (2) 相关信息的输入见图 4.2。 图 4.2 相关信息的输入 (3) 输出邻接矩阵和结果见图 4.3。 图 4.3 输出邻接矩阵和结果 (4) 另一组输入与输出见图 4.4。 图 4.4 另一组输入与输出 参考文献参考文献 1 严蔚敏,吴伟民.数据结构(C 语言版)M.北京:清华大学出版社, 2006 2 吕国英.算法设计与分析M.北京:清华大学出版社,2006 3 徐宝文 李志.C 语言程序设计M.北京:机械工业出
12、版社,2004 4 Erich Gamma , Richard Helm. 设计模式(英文版)M.北京:机械工 业出版社,2004 附 录 源程序清单: #include #include #define clr(a) memset(a,0,sizeof(a) #define N 500 int find(int i,int m,int gN,int mat,int cmat) int v,j; for(j=0;jm;j+) if(gij v=matj; matj=i; if(v=-1|find(v,m,g,mat,cmat) return 1; matj=v; return 0; int m
13、atch(int gN,int n,int m,int mat) int i,k=0,cmatN; for(i=0;im;i+) mati=-1; for(i=0;in;i+) clr(cmat); k+=find(i,m,g,mat,cmat); return k; int n,m; int aNN; int matN; void output() int i,j; for(i=0;in;i+) for(j=0;jm;j+) printf(“%-3d“,aij); printf(“n“); int main() int i,j,k; printf(“输入格子的行和列n“); while(sc
14、anf(“%d%d“, printf(“输入相关信息n“); for(i=0;in;i+) for(j=0;jm;j+) scanf(“%d“, printf(“输出邻接矩阵n“); output(); printf(“输出结果n“); k=match(a,n,m,mat); printf(“%dn“,k); return 0; 课程设计总结:课程设计总结: 说实话这次的课程设计开始拿到题目的时候,真的是不知从何下手,因为 在此之前从来就没有学过有关匹配的任何算法,而题目所要用到的算法在以前 就从来没有听说过,后来通过问老师和在网上查询的资料渐渐的了解了有关匹 配的一些概念,以及求最大匹配的匈
15、牙利经典算法,就是不断地寻找增广路径, 直至找到没有增广边为止; 在这次课设中我主要是用了二位数组建立了表示二分图的邻接关系,之后 采用匈牙利算法来求解。开始的时候遇到了很多为题,但在老师和同学们的帮 助下,终于一点一点的理解了,懂得了什么是二分图,什么是最大匹配,以及 怎样求得最大匹配。最后在借鉴此算法的基础上完成了课程设计。 尽管都是借鉴来的程序,但是在程序运行结束后,内心还是高兴的,毕竟 我又学到了新的知识。在这里要感谢在课程设计中给过我帮助的老师、同学, 没有你们的帮助我不会这么容易能完成的,谢谢你们了。 在为期一个多星期的课程设计中,我的收获的巨大的,这次课程设计不仅 使我进一步学会了对所学知识的应用,而且又学到了很多新的知识,填补了一 些空白。我会继续努力,学习更多的新知识,不断提高自身能力。 指导教师评语: 指导教师(签字): 年 月 日 课程设计成绩