数据结构课设数据结构课设报告B类.doc

《数据结构课设数据结构课设报告B类.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计课题报告题目男女运动员最佳组合课题组组长马忠玉课题组成员董远斐吴思锦邱子君专业名称计算机科学与技术班级计算机1102班指导教师孟凡荣2013年6月课程设计任务书题目：男女运动员最佳组合问题描述：设有N个男羽毛球运动员和N个女羽毛球运动员，现组成N对男女混合最佳组合。每个男运动员对每个女运动员都有一个满意度排序，用矩阵mf[0:n-1][0:n-1]表示。mf[i][j]表示第i个男运动员对第j个女运动员的满意度，满意度值越高，满意程度越高。同理，每个女运动员对

2、每个男运动员也有一个满意度排序，用矩阵fm[0:n-1][0:n-1]表示。男女运动员之间的一个完全匹配称为一个组合。设计要求：设计对于给定的满意度，求最佳组合的程序，使得满意度总和达到最大。（1）采用STL的向量等数据结构。（2）实现STL的一维向量类vector。（3）利用一维向量类构造二维向量矩阵。（4）尝试采用不同数据结构的多种解法。　　　　　　　　　　　　指导教师签字：年　　月　　日课题任务分工学号姓名程序设计分工课题报告分工20113167马忠玉回溯法中pairup类及类的成员函数1.课题

3、背景2.需求分析3.方案设计4.方案实现5.个人报告20113180董远斐分支限界法中的主函数1.个人报告2.课题总结20113183吴思锦分支限界法中的Argnode类及成员函数1.个人报告2..测试与运行20113182邱子君回溯法中主函数1.个人报告2.方案设计目录1课题背景11.1课题来源11.2课题任务21.3课题原理22需求分析43方案设计83.1总体（功能）设计84方案实现34.1开发环境与编程工具44.2程序设计关键技术45测试与运行45.1系统运行46用户手册（可选）47课题总结67

4、.1课题评价67.2设计心得78附录A（组员分课题报告）88-1马忠玉分课题报告88-2董远斐分课题报告188-3吴思锦分课题报告248-4邱子君分课题报告299附录B（源程序文件清单）(光盘)349-1源程序代码（*.cpp）349-2源程序代码（*.cpp）341课题背景1.1课题来源运动员最佳配对问题是一个较为复杂的问题,借助于算法设计策略开展对该问题的研究,对解决像乒乓球、羽毛球、网球、跳水、沙滩排球和划艇等项目的人选问题具有一定的实际意义。1.2课题任务设计对于给定的满意度，求最佳组合的程序

5、，使得满意度总和达到最大。（1）采用STL的向量等数据结构。（2）实现STL的一维向量类vector。（3）利用一维向量类构造二维向量矩阵。（4）尝试采用不同数据结构的多种解法。1.3课题原理1.3.1回溯法回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。1.3.2分支限界法分支限界法常以广度优先或以最小耗费（最大效益）优先的方

6、式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2需求分析3方案设计3.1数据结构设计主要运用了STL中的vector模板以及队列模板，具体部分请查看小组成员个人报告。4方案实现4.1开发环境与编程工具开发环境为

7、C++，编程工具为visualc++6.04.2程序设计关键技术回溯法以及分支限界法的实现5测试与运行5.1系统运行运行过程截图如下：回溯法：分支限界法：6用户手册（可选）7课题总结7.1课题评价 本课题难度适中，一方面让我们学习使用不同的数据来结构来解决同一问题，此外也让我们在比较中学会选择高效的算法。方法一中回溯法，用到的是递归的进行深度优先搜索整个排列树；算法中没有剪枝函数和限界函数，算法的时间复杂度为O（n！）；复杂度很高，方法二中用的是分支限界法对排列树进行广度优先搜索，算法的时间复杂度有所

8、降低。7.2设计心得本次实验考察我们队STL的使用，通过对STL的使用大大方便了我们函数的编写及功能的实现。这是一个十分实用并且很典型的问题，在该问题的解决核心程序中我们使用了分支限界发，采用广度优先遍历，节约了时间及空间复杂度。其实，在主函数编写过程中，我们一开始并不是说有是明确的想法去利用分支限界法来解决这一问题，我们对问题进行分析讨论出两种情况，并及时查阅资料，发现我们的构想已经拥有很完善的体系构建，分别为回溯法和分支限界法。拥有了理论的支持和完善