打猎问题课程设计

《打猎问题课程设计》由会员分享，可在线阅读，更多相关《打猎问题课程设计（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、牙利经典算法，就是不断地寻找增广路径， 直至找到没有增广边为止； 在这次课设中我主要是用了二位数组建立了表示二分图的邻接关系，之后 采用匈牙利算法来求解。开始的时候遇到了很多为题，但在老师和同学们的帮 助下，终于一点一点的理解了，懂得了什么是二分图，什么是最大匹配，以及 怎样求得最大匹配。最后在借鉴此算法的基础上完成了课程设计。 尽管都是借鉴来的程序，但是在程序运行结束后，内心还是高兴的，毕竟 我又学到了新的知识。在这里要感谢在课程设计中给过我帮助的老师、同学， 没有你们的帮助我不会这么容易能完成的，谢谢你们了。 在为期一个多星期的课程设计中，我的收获的巨大的，这次课程设计不仅 使我进一步学会了对所学知识的应用，而且又学到了很多新的知识，填补了一 些空白。我会继续努力，学习更多的新知识，不断提高自身能力。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩