運(yùn)動員最佳配對問題--實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上2011-2012第二學(xué)期算法設(shè)計(jì)與分析期末考核項(xiàng)目名稱：運(yùn)動員最佳配對問題 1. 項(xiàng)目描述（10分）羽毛球隊(duì)有男女運(yùn)動員各n人。 給定2 個n×n矩陣P和Q。Pij是男運(yùn)動員i和女運(yùn)動員j配對組成混合雙打的男運(yùn)動員競賽優(yōu)勢；Qij是女運(yùn)動員i和男運(yùn)動員j配合的女運(yùn)動員競賽優(yōu)勢。由于技術(shù)配合和心理狀態(tài)等各種因素影響，Pij不一定等于Qji。男運(yùn)動員i和女運(yùn)動員j配對組成混合雙打的男女雙方競賽優(yōu)勢為Pij*Qji。設(shè)計(jì)一個算法，計(jì)算男女運(yùn)動員最佳配對法，使各組男女雙方競賽優(yōu)勢的總和達(dá)到最大。編程任務(wù)：設(shè)計(jì)一個算法，對于給定的男女運(yùn)動員競賽優(yōu)勢，計(jì)算男女運(yùn)動員最

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

3、合就是女運(yùn)動員的各種排列。因此，搜索的解空間樹是“排列樹”。用回溯法搜索排列樹的算法框架：void backtrack (int t)if (t>n)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 <stdio.h># include <stdlib.h># define HeapSize 60typedef structint n;

4、/男運(yùn)動員個數(shù)int * p;/男運(yùn)動員競賽優(yōu)勢int * q;/女運(yùn)動員競賽優(yōu)勢Sport;typedef structint w20;/一種排列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;H->

5、;last = 0;H->heep = (Node *) malloc (H->maxsize + 1) * sizeof(Node);/插入大根堆void HeapInsert (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

6、 = x;/取大根堆的根，并保持堆的性質(zhì)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 = 1;ci = 2;while (ci <= H->last)if (ci < H->last && (H->heepci + 1.val > H->heepci.val)ci +;if (H->h

7、eepci.val < y.val)break;H->heepi = H->heepci;i = ci;ci *= 2;H->heepi = y;/計(jì)算配對和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;/主干函數(shù)void Backtrack (Sport &S)Node fNode,sNode;/fNode為父節(jié)點(diǎn),sNode為子節(jié)點(diǎn)Heap H;int i, best = 0;/最大的配對

8、和MaxHeapInit(H);for (i = 0; i < S.n; i+)fNode.wi = i;fNode.t = 0;fNode.val = 0;HeapInsert(fNode, H);while (H->last != 0)/當(dāng)堆為空時結(jié)束循環(huán)DeleteMax(H, &fNode);if (fNode.t = S.n - 1) /為一個全排列時，比較節(jié)點(diǎn)內(nèi)值是否比當(dāng)前最優(yōu)值更佳if (best < fNode.val)best = fNode.val;elsefor (i = fNode.t; i < S.n; i+)/搜索子樹sNode =

9、fNode;sNode.t +;sNode.wsNode.t = fNode.wi;sNode.wi = fNode.wsNode.t;Compute(S, sNode); /計(jì)算節(jié)點(diǎn)的valHeapInsert(sNode, H);printf("最大配對總和為:%dn", best);/構(gòu)造運(yùn)動員結(jié)構(gòu)體void SetSport (Sport &S)int i, j;printf("請輸入男運(yùn)動員或女運(yùn)動員的人數(shù):");scanf("%d",&S.n);S.p = (int *) malloc (S.n * siz

10、eof(int);S.q = (int *) malloc (S.n * sizeof(int);if (S.p = NULL | S.q = NULL)printf("內(nèi)存分配失??！n");exit(-1);for (i = 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èi)存分配失敗！n");exit(-1);printf(&

11、quot;請輸入男運(yùn)動員對女運(yùn)動員的競賽優(yōu)勢：n");for (i = 0; i < S.n; i+)for (j = 0; j < S.n; j+)scanf("%d", &S.pij);printf("請輸入女運(yùn)動員對男運(yùn)動員的競賽優(yōu)勢：n");for (i = 0; i < S.n; i+)for (j = 0; j < S.n; j+)scanf("%d", &S.qij);/釋放申請的堆空間void Destroy (Sport &S)int i;for (i = 0

12、; 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 <stdio.h># include <stdlib.h>typedef structint * p;/男運(yùn)動員競賽優(yōu)勢int * q;/女運(yùn)動員競賽優(yōu)勢int * w;/排列編號int * best;/最好的排列編號int n;/男運(yùn)動員個數(shù)int

13、 bestsum;/最好的配對和Sport;void Swap(int &a, int &b)int t;t = a;a = b;b = t;/計(jì)算運(yùn)動員的配對和void Compute(Sport &S)int sum = 0;for (int i = 0; i < S.n; i+)sum += S.piS.wi * S.qS.wii;if (sum > S.bestsum)S.bestsum = sum;for (int i = 0; i < S.n; i+)S.besti = S.wi;/保存最好的排列編號/主干函數(shù)void Backtrack(

14、int t, Sport &S)if (t >= S.n)Compute(S);elsefor (int i = t; i < S.n; i+)Swap(S.wt, S.wi);Backtrack(t+1, 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 = N

15、ULL;/構(gòu)造運(yùn)動員結(jié)構(gòu)體void SetSport(Sport &S)int i, j;printf("請輸入男運(yùn)動員或女運(yùn)動員的人數(shù):");scanf("%d",&S.n);S.p = (int *) malloc (S.n * sizeof(int);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

16、 = NULL | S.w = NULL | S.best = NULL)printf("內(nèi)存分配失敗！n");exit(-1);for (i = 0; i < S.n; i+)S.wi = 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èi)存分配失敗！n");exit(-1);printf("請輸入男運(yùn)動員對女運(yùn)動員的競賽優(yōu)勢：n")

17、;for (i = 0; i < S.n; i+)for (j = 0; j < S.n; j+)scanf("%d", &S.pij);printf("請輸入女運(yùn)動員對男運(yùn)動員的競賽優(yōu)勢：n");for (i = 0; i < S.n; i+)for (j = 0; j < S.n; j+)scanf("%d", &S.qij);/輸出最好的配對結(jié)果void Output(Sport &S)int i;for (i = 0; i < S.n; i+)printf("第 %d 號男運(yùn)動員配第 %d 號女運(yùn)動員n", i, S.besti);printf("最大