运动员最佳配对问题--实验报告(共10页).doc

精选优质文档-倾情为你奉上2011-2012第二学期算法设计与分析期末考核项目名称：运动员最佳配对问题 1. 项目描述（10分）羽毛球队有男女运动员各n人。 给定2 个nn矩阵P和Q。Pij是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Qij是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，Pij不一定等于Qji。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为Pij*Qji。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。 2. 算法设计（10分） 方法一：优先队列式分支限界法具体算法：算法开始时创建一个最大堆，用于表示活结点优先队列堆中每个结点的val值是优先队列的优先级。接着算法计算出图中每个顶