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

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

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

4、0;/一種排列int t; /已排到的位數(shù)int val; /此種排列的配對和Node;typedef struct minheapint last;/此時(shí)的元素個(gè)數(shù)int maxsize;/堆中的元素最大個(gè)數(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;/計(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),sNod

7、e為子節(jié)點(diǎn)Heap H;int i, best = 0;/最大的配對和MaxHeapInit(H);for (i = 0; i last != 0)/當(dāng)堆為空時(shí)結(jié)束循環(huán)DeleteMax(H, &fNode);if (fNode.t = S.n - 1) /為一個(gè)全排列時(shí)，比較節(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 = fNode;sNode.t +;sNode.wsNode.t = fNode.wi;sNode.wi = fNode.wsNode.

8、t;Compute(S, sNode); /計(jì)算節(jié)點(diǎn)的valHeapInsert(sNode, H);printf(最大配對總和為:%dn, best);/構(gòu)造運(yùn)動(dòng)員結(jié)構(gòu)體void SetSport (Sport &S)int i, j;printf(請輸入男運(yùn)動(dòng)員或女運(yùn)動(dòng)員的人數(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)存分配失?。);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ùn)動(dòng)員對女運(yùn)動(dòng)員的競賽優(yōu)勢：n);for (i = 0; i S.n; i+)for (j = 0; j S.n; j+)scanf(%d, &S.pij);printf(請輸入女運(yùn)動(dòng)員對男運(yùn)動(dòng)員的競賽優(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ùn)動(dòng)員競賽優(yōu)勢int * q;/女運(yùn)動(dòng)員競賽優(yōu)勢int

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