运动员最佳配对问题--实验报告

1、2011-2012第二学期算法设计与分析期末考核项目名称：运动员最佳配对问题 1. 项目描述（10分）羽毛球队有男女运动员各n人。 给定2 个nn矩阵P和Q。Pij是男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势；Qij是女运动员i和男运动员j配合的女运动员竞赛优势。由于技术配合和心理状态等各种因素影响，Pij不一定等于Qji。男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为Pij*Qji。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。编程任务：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和

2、达到最大。 2. 算法设计（10分） 方法一：优先队列式分支限界法具体算法：算法开始时创建一个最大堆，用于表示活结点优先队列堆中每个结点的val值是优先队列的优先级。接着算法计算出图中每个顶点的最大val。如果搜索到所搜索的排列树的叶子节点，算法即告结束。 方法二：回溯法具体算法：套用排列树框架，做好初始化后开始回溯，关键在于到达叶子节点时，需要计算当前的总和csum += piwi * qwii，若发现csum比之前的最优值大，则更新最优值和配对顺序，回溯完成后则可得到最大总和及其相应的运动员配对方法让男队员按自己编号顺序站定，女运动员和他们搭配的各种组合就是女运动员的各种排列。因此，搜索的

3、解空间树是“排列树”。用回溯法搜索排列树的算法框架：void backtrack (int t)if (tn)output(x); else for (int i=f(n,t);i=g(n,t);i+) xt=h(i); if (constraint(t)&bound(t) backtrack(t+1); 程序（50分）方法一：分支限界法程序# include # include # define HeapSize 60typedef structint n; /男运动员个数int * p;/男运动员竞赛优势int * q;/女运动员竞赛优势Sport;typedef structint w2

4、0;/一种排列int t; /已排到的位数int val; /此种排列的配对和Node;typedef struct minheapint last;/此时的元素个数int maxsize;/堆中的元素最大个数Node * heep;Minheap, * Heap;/建大根堆void MaxHeapInit (Heap &H)H = (Heap) malloc (sizeof(Minheap);H-maxsize = HeapSize;H-last = 0;H-heep = (Node *) malloc (H-maxsize + 1) * sizeof(Node);/插入大根堆void He

5、apInsert (Node x, Heap H)int i;if (H-last = H-maxsize)printf(堆已满！n);exit(0);i = + H-last;while (i != 1 & x.val H-heepi/2.val)H-heepi = H-heepi/2;i /= 2;H-heepi = x;/取大根堆的根，并保持堆的性质void DeleteMax (Heap H, Node * x)int i, ci;Node y;if (H-last = 0)printf(空堆！n);exit(0);*x = H-heep1;y = H-heepH-last -;i =

6、 1;ci = 2;while (ci last)if (ci last & (H-heepci + 1.val H-heepci.val)ci +;if (H-heepci.val heepi = H-heepci;i = ci;ci *= 2;H-heepi = y;/计算配对和void Compute(Sport &S, Node &T)T.val = 0;for (int i = 0; i S.n; i+)T.val += S.piT.wi * S.qT.wii;/主干函数void Backtrack (Sport &S)Node fNode,sNode;/fNode为父节点,sNod

7、e为子节点Heap H;int i, best = 0;/最大的配对和MaxHeapInit(H);for (i = 0; i last != 0)/当堆为空时结束循环DeleteMax(H, &fNode);if (fNode.t = S.n - 1) /为一个全排列时，比较节点内值是否比当前最优值更佳if (best fNode.val)best = fNode.val;elsefor (i = fNode.t; i S.n; i+)/搜索子树sNode = fNode;sNode.t +;sNode.wsNode.t = fNode.wi;sNode.wi = fNode.wsNode.

8、t;Compute(S, sNode); /计算节点的valHeapInsert(sNode, H);printf(最大配对总和为:%dn, best);/构造运动员结构体void SetSport (Sport &S)int i, j;printf(请输入男运动员或女运动员的人数:);scanf(%d,&S.n);S.p = (int *) malloc (S.n * sizeof(int);S.q = (int *) malloc (S.n * sizeof(int);if (S.p = NULL | S.q = NULL)printf(内存分配失败！n);exit(-1);for (i

9、= 0; i S.n; i+)S.pi = (int *) malloc (S.n * sizeof(int);S.qi = (int *) malloc (S.n * sizeof(int);if (S.pi = NULL | S.qi = NULL)printf(内存分配失败！n);exit(-1);printf(请输入男运动员对女运动员的竞赛优势：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.pij);printf(请输入女运动员对男运动员的竞赛优势：n);for (i = 0; i S.n; i+)for (j

10、= 0; j S.n; j+)scanf(%d, &S.qij);/释放申请的堆空间void Destroy (Sport &S)int i;for (i = 0; i S.n; i+)free(S.pi);free(S.qi);free(S.p);free(S.q);S.q = S.p = NULL;int main (void)Sport S;SetSport(S);Backtrack(S);Destroy(S);return 0;方法二：回溯法程序# include # include typedef structint * p;/男运动员竞赛优势int * q;/女运动员竞赛优势int

11、 * w;/排列编号int * best;/最好的排列编号int n;/男运动员个数int bestsum;/最好的配对和Sport;void Swap(int &a, int &b)int t;t = a;a = b;b = t;/计算运动员的配对和void Compute(Sport &S)int sum = 0;for (int i = 0; i S.bestsum)S.bestsum = sum;for (int i = 0; i = S.n)Compute(S);elsefor (int i = t; i S.n; i+)Swap(S.wt, S.wi);Backtrack(t+1,

12、 S);Swap(S.wt, S.wi);/释放申请的堆空间void Destroy(Sport &S)int i;for (i = 0; i S.n; i+)free(S.pi);free(S.qi);free(S.p);free(S.q);free(S.best);free(S.w);S.q = S.p = NULL;S.best = S.w = NULL;/构造运动员结构体void SetSport(Sport &S)int i, j;printf(请输入男运动员或女运动员的人数:);scanf(%d,&S.n);S.p = (int *) malloc (S.n * sizeof(in

13、t);S.q = (int *) malloc (S.n * sizeof(int);S.w = (int *) malloc (S.n * sizeof(int);S.best = (int *) malloc (S.n * sizeof(int);if (S.p = NULL | S.q = NULL | S.w = NULL | S.best = NULL)printf(内存分配失败！n);exit(-1);for (i = 0; i S.n; i+)S.wi = i;S.pi = (int *) malloc (S.n * sizeof(int);S.qi = (int *) mall

14、oc (S.n * sizeof(int);if (S.pi = NULL | S.qi = NULL)printf(内存分配失败！n);exit(-1);printf(请输入男运动员对女运动员的竞赛优势：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.pij);printf(请输入女运动员对男运动员的竞赛优势：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.qij);/输出最好的配对结果void Output(Sport &S)int i;for (i = 0; i S.n; i+)printf(第 %d 号男运动员配第 %d 号女运动员n, i, S.besti);printf(最大配对总和为:%dn,S.bestsum);int main(v