運動員最佳配對問題--實驗報告

1、2011-2012 第二學期算法設(shè)計與分析期末考核項目名稱：運動員最佳配對問題1. 項冃描述(10分)羽毛球隊有男女運動員各n人。給定2個nxn矩陣p和q。pij是男運動員i和女運動員j配對組成混合雙打的男運動 員競賽優(yōu)勢；qij是女運動員i和男運動員j配合的女運動員競賽優(yōu)勢。由于技術(shù)配合和心理狀態(tài)等各種因素影響，pij不一定等于qjio男運動員i和女運 動員j配對組成混合雙打的男女雙方競賽優(yōu)勢為pij*qjio設(shè)計一個算法，計算男女運動員最佳配對法，使各組男女雙方競賽優(yōu)熱的總和達到最大。 編程任務(wù)：設(shè)計一個算法，對于給定的男女運動員競賽優(yōu)勢，計算男女運動員最佳配對法, 使各組男女雙方競賽優(yōu)勢

2、的總和達到最大。2. 算法設(shè)計(10分)方法一：優(yōu)先隊列式分支限界法 具體算法：算法開始時創(chuàng)建一個最大堆，用于表示活結(jié)點優(yōu)先隊列堆中每個結(jié)點的值是優(yōu)先隊列的優(yōu)先級。接著算法計算出圖中每個頂點的最大valo如果搜索到所搜索的排列樹的葉子節(jié)點，算法即告結(jié)束。方法二：冋溯法具體算法：套用排列樹框架，做好初始化后開始回溯，關(guān)鍵在于到達葉子節(jié)點時，需要計算當前 的總和csum += piwi * qwii,若發(fā)現(xiàn)csum比之前的最優(yōu)值大，則更新 最 優(yōu)值和配對順序，回溯完成后則可得到最大總和及其相應(yīng)的運動員配對方法讓男隊員按自己編號順序站定，女運動員和他們搭配的各種組合就是女運動員的各種排列。因此 搜索

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; /男運動員個數(shù) int *

4、p;/男運動員競賽優(yōu)勢 int * q;/女運動員競賽優(yōu)勢sport;typedef structint w 20 ; /_*種排列int t; /已排到的位數(shù)int val; /此種排列的配對和node;typedef struct minheapint last; /此時的元素個數(shù)int maxsize; /堆中的元素最大個數(shù)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、的性質(zhì)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;/主干函數(shù)void backtrack (sport &s)node fnode, snode;/fnode為父節(jié)點，snode為了節(jié)點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)/當堆為空時結(jié)朿循環(huán)deletemax(h, &fnode);if (fnode . t = s.n - 1) /為一個全排列時，比較節(jié)點內(nèi)值是否比當 前最優(yōu)值更佳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) ;/計算節(jié)點的valheapinsert(snode, h);printf (”最大配對總和為：%dnn, best);/構(gòu)造運動員結(jié)構(gòu)體void setsport (sport &s)int i, j;printf (”請輸入男運動員或女運動員的人數(shù)：");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èi)存分配失敗！! 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內(nèi)存分配失??！! nn);exit(-1); printf c-請輸入男運動員對女運動員的競賽優(yōu)勢：n");for (i =

11、0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf(n%dn, &spij);printf ("請輸入女運動員對男運動員的競賽優(yōu)勢: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; /男運動員競賽優(yōu)勢 int * q; /女運動員競賽優(yōu)勢 int * w; /排列編號int * best; /最好的排列編號int n; /男運動員個數(shù)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 ;/保存最好的排列編號/主干函數(shù)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;/構(gòu)造運動員結(jié)構(gòu)體void setsport(sport &s)int i,

15、 j;printf (”請輸入男運動員或女運動員的人數(shù)：”); 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內(nèi)存分配失??！!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èi)存分配失??！! n");exit(-1);printf ("請輸入男運動員對女運動員的競賽優(yōu)勢：n");for (i = 0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf&s.pi j);printf

17、("請輸入女運動員対男運動員的競賽優(yōu)勢：才);for (i = 0; i < s.n; i+)for (j = 0; j < s.n; j +)scanf("%dn, &s.qij)；/輸出最好的配對結(jié)果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. 程序運行結(jié)果（10分）分支限界法程序運行結(jié)果:請輸入男運動員或女運動員的人數(shù):3請輸入男運動員對女運動員的競賽優(yōu)勢:10 2 32 3 43 4 5=n=請輸入女運動員對男運動員的競賽優(yōu)勢:3 5 34 5 1最大配對總和為：52 請按任意鍵繼續(xù)冋溯法程序