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

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

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

3、的解空间树是“排列树用回溯法搜索排列树的算法框架： void backtrack (int t)if (t>n)output (x);elsefor (int i=f (n, t) ; i<=g (n, t) ; i+)xt=h(i);if (constraint(t)&&bound(t) backtrack(t+1);程序(50分)方法一：分支限界法程序# include <stdio.h># include <stdlib.h> # define heapsize 60typedef structint n; /男运动员个数 int *

4、p;/男运动员竞赛优势 int * q;/女运动员竞赛优势sport;typedef structint w 20 ; /_*种排列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;sizeof(node)

5、;h->last= 0;h->heep = (node *) malloc (h->maxsize + 1)/插入大根堆void heapinsert (node x, heap h)int i;if (h->last = h->maxsize)printf (n堆已满！! nn);exit (0);i = + h->last;while (i != 1 && x.val > h->heepi/2.val) h->heepi = h->heepi/2;i/= 2;h->heepi = x;/取大根堆的根，并保持堆

6、的性质void deletemax (heap h, node * x)int i, ci;node y;if (h->last = 0)printf (”空堆！ ！ ！ nn);exit (0);*x = h->heep1;y = h->heeph->last -;i = 1；ci = 2;while (ci <= h->last)if (ci < h->last && (h->heepci + 1val > h->heepci.val) ci +;if (h->heepcival < y.val)

7、break;h->heepi = h->heepci;i= ci;ci*= 2;h->heepi = y;/计算配对和void compute(sport &s, node &t)tval = 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为父节点，snode为了节点heap h;int i, best = 0;/最大的配对和maxheapinit(h);for (i =

8、 0; i < s.n; i+)fnode wi = i;fnode.t = 0;fnode.val = 0;heapinsert(fnode, h);while (h->last != 0)/当堆为空时结朿循环deletemax(h, &fnode);if (fnode . t = s.n - 1) /为一个全排列时，比较节点内值是否比当 前最优值更佳if (best < fnode .vbj.)best = fnode.val;elsefor (i = fnode t; i < s. n; i + +)/搜索子树snode = fnode;snode.t +

9、;snode wsnode.t = fnode.wi;snode wi= fnode wsnodet;compute (sz snode) ;/计算节点的valheapinsert(snode, h);printf (”最大配对总和为：%dnn, best);/构造运动员结构体void setsport (sport &s)int i, j;printf (”请输入男运动员或女运动员的人数：");scanf(n%dn，&s.n);s.p = (int *) malloc (s.n * sizeof (int);s.q = (int *) malloc (s.n * s

10、izeof (int);if (s.p = null | s.q = null)printf ("内存分配失败！! n");exit(-1);for (i = 0; i < s.n; i+)spi = (int *) malloc (s.n * sizeof (int); s.qi = (int *) malloc (s.n * sizeof (int); if (s.pi = null | s.qi = null)printf (n内存分配失败！! nn);exit(-1); printf c-请输入男运动员对女运动员的竞赛优势：n");for (i =

11、0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf(n%dn, &spij);printf ("请输入女运动员对男运动员的竞赛优势:n");for (i = 0; i < s.n; i+)for (j = 0; j < s.n; j+)scanf(n%dn, &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

12、.q = s.p = null;int main (void)sport s;setsport(s);backtrack(s);destroy(s);return 0;方法二：回溯法程序# include <stdio.h># include <stdlibh> typedef structint * p; /男运动员竞赛优势 int * q; /女运动员竞赛优势 int * w; /排列编号int * best; /最好的排列编号int n; /男运动员个数int bestsum; /最好的配对和sport;void swap(int &“ int &

13、b)int t; t = a; a = b; b = t;/计算运动员的配对和 void compute(sport &s)int sum = 0;for (int i = 0; i < s.n; i+)sum += s.pis.wi * s.qs.wii;if (sum > sbestsum)s.bestsum = sum;for (int i = 0; i < s.n; i+)s .best i = s . w i ;/保存最好的排列编号/主干函数void backtrack(int tf sport &s)if (t >= s.n)compute(

14、s);elsefor (int i = t; i < s.n; i+)swap(s.wt, s.wi);backtrack(t+1z s);swap(s.wt, s.wi);/释放申请的堆空间void destroy(sport &s)int i;for (i = 0; i < s.n; i+)free(s pi);free(sqi);free(s.p);free(s q);free(s best);free(s w);s.q = sp = null;s.best = s.w = null;/构造运动员结构体void setsport(sport &s)int i,

15、 j;printf (”请输入男运动员或女运动员的人数：”); scanf(n%dn，&s n);s.p = (int *) malloc (s.n * sizeof (int);s.q= (int *)malloc(s.n *sizeof (int);s.w= (int *)malloc(sn*sizeof (int);sbest = (int *)malloc(s.nsizeof (int);if (s.p = null | |s. q =null11s.w = null | | sbest = null)printf (n内存分配失败！!nn);exit (-1);for (i

16、= 0; i < s.n; i+)s w i = i;spi = (int *) malloc (s.n * sizeof (int);sqi = (int *) malloc (s.n * sizeof (int); if (s.pi = null | s.qi = null)printf (n内存分配失败！! n");exit(-1);printf ("请输入男运动员对女运动员的竞赛优势：n");for (i = 0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf&s.pi j);printf

17、("请输入女运动员対男运动员的竞赛优势：才);for (i = 0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf("%dn, &s.qij)；/输出最好的配对结果void output(sport &s)int i;for (i = 0; i < s.n; i+)printf ("第%d号男运动员配第%d号女运动员rt, iz s .best i); printf ("最大配对总和为:%dnn, s .bestsum);int main(void)sport s;setsport(s);backtrack(0, s);output(s);destroy(s);return 0;3. 程序运行结果（10分）分支限界法程序运行结果:请输入男运动员或女运动员的人数:3请输入男运动员对女运动员的竞赛优势:10 2 32 3 43 4 5=n=请输入女运动员对男运动员的竞赛优势:3 5 34 5 1最大配对总和为：52 请按任意键继续冋溯法程序