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

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

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

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; /男運動員個數(shù)int * p;/男運動員競賽優(yōu)勢int * q;/女運動員競賽優(yōu)勢Sport;typedef structint w2

4、0;/一種排列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-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;/取大根堆的根，并保持堆的性質(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 =

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;/主干函數(shù)void Backtrack (Sport &S)Node fNode,sNode;/fNode為父節(jié)點,sNod

7、e為子節(jié)點Heap H;int i, best = 0;/最大的配對和MaxHeapInit(H);for (i = 0; i last != 0)/當堆為空時結(jié)束循環(huán)DeleteMax(H, &fNode);if (fNode.t = S.n - 1) /為一個全排列時，比較節(jié)點內(nèi)值是否比當前最優(yōu)值更佳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); /計算節(jié)點的valHeapInsert(sNode, H);printf(最大配對總和為:%dn, best);/構(gòu)造運動員結(jié)構(gòu)體void SetSport (Sport &S)int i, j;printf(請輸入男運動員或女運動員的人數(shù):);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èi)存分配失??！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èi)存分配失??！n);exit(-1);printf(請輸入男運動員對女運動員的競賽優(yōu)勢：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.pij);printf(請輸入女運動員對男運動員的競賽優(yōu)勢：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;/男運動員競賽優(yōu)勢int * q;/女運動員競賽優(yōu)勢int

11、 * w;/排列編號int * best;/最好的排列編號int n;/男運動員個數(shù)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;/構(gòu)造運動員結(jié)構(gòu)體void SetSport(Sport &S)int i, j;printf(請輸入男運動員或女運動員的人數(shù):);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èi)存分配失?。);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èi)存分配失??！n);exit(-1);printf(請輸入男運動員對女運動員的競賽優(yōu)勢：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.pij);printf(請輸入女運動員對男運動員的競賽優(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 號男運動員配第 %d 號女運動員n, i, S.besti);printf(最大配對總和為:%dn,S.bestsum);int main(v