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

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

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

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;/取大根堆的根，并保持堆的性質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)/當堆為空時結束循環(huán)DeleteMax(H, &fNode);if (fNode.t = S.n - 1) /為一個全排列時，比較節(jié)點內值是否比當前最優(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);/構造運動員結構體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);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(內存分配失?。);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;/構造運動員結構體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(內存分配失?。);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(內存分配失?。);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);/輸出最好的配對結果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