算法設(shè)計(jì)與分析課程設(shè)計(jì)報(bào)告——穩(wěn)定婚姻問題的gale-shapley算法

1、<p>　　算法設(shè)計(jì)與分析課程設(shè)計(jì)</p><p>　　題目:模擬實(shí)現(xiàn)穩(wěn)定婚姻問題的Gale-Shapley算法</p><p><b>　　設(shè)計(jì)分析測試報(bào)告</b></p><p>　　2013年1月 12日</p><p><b>　　程序算法設(shè)計(jì)說明書</b></p>

2、<p><b>　　前言</b></p><p>　　1.問題描述：穩(wěn)定婚姻問題：有n男n女，每人都按他對（異性）對象的喜好程度按1至n排列。安排男女結(jié)婚，使得下列情形為真:在n男n女中的任意兩對夫婦(M, W)和(m, w)，都不存在M男對w女喜好度大于現(xiàn)任妻子W女，并且w女對M男喜好度也大于現(xiàn)任丈夫m男的情形發(fā)生，此種情形稱為不穩(wěn)定。</p><p>　

3、　2.程序編制環(huán)境相關(guān)說明：</p><p>　　系統(tǒng)：WINDOWS 7</p><p>　　編制環(huán)境：visual studio 8</p><p>　　程序主要算法設(shè)計(jì)分析說明</p><p>　　Gale-Shapley算法的基本思想如下：</p><p>　　(1)初始，每個(gè)人都是未婚的。假設(shè)一個(gè)未婚的男人m

4、選擇了他的優(yōu)先表上排名最高的女人w，并且向她求婚。能立刻聲明(m, w)將是最后的穩(wěn)定匹配中的一對嗎?不一定:因?yàn)樵趯淼哪硞€(gè)時(shí)候，女人w偏愛的男人m，可能向她求婚。另一方面，對w來說，立刻拒絕m可能是危險(xiǎn)的，她可能沒有接收到來自她的優(yōu)先表上排名像m那樣高的某個(gè)人的求婚。于是一種自然地想法是使這個(gè)(m, w)對進(jìn)入一種中間狀態(tài)一約會。</p><p>　　(2)假設(shè)我們現(xiàn)在處在某種狀態(tài)，某些男人和女人是自由的(沒

5、有約會)，某些是有約會的。任意一個(gè)自由的男人m選擇他還沒有求過婚的最高排名的女人w，且向她求婚。如果w也是自由的，那么m和w就成為約會狀態(tài)。否則，w已經(jīng)在與某個(gè)其他的男人m，約會。在這種情況下，她來決定m和m，哪 個(gè)人在她的優(yōu)先表中的排名更高;排名更高的男人變成與w約會而另一個(gè)人變成自由的。</p><p>　　(3)最后，當(dāng)沒有一個(gè)人是自由的時(shí)候，算法將結(jié)束;此刻所有的約會將被宣告為最后的結(jié)果，且將返回最終的完

6、美匹配。</p><p>　　所以，在N對男女中，男生采用主動(dòng)出擊追求自己最喜歡的女生策略，女生采用“守株待兔”和“喜新厭舊”策略。每一位男生主動(dòng)去追求自己最喜歡的女生，而女生則在追求自己的男生中與現(xiàn)任男友中，選擇一位最喜歡的接受。如果追求成功，為被拋棄的男友追求他下一位喜歡的女生。如果追求不成功，則為這位男生追求他下一位喜歡的女生。這樣進(jìn)行了N次循環(huán)后，每一位男生都是從自己最喜歡的女生開始追求，并且都有女友，那

7、么男生喜歡的程度多于現(xiàn)任妻子的那位女生肯定是曾經(jīng)拒絕過自己的。同理，女生也是按照自己喜歡程度進(jìn)行選擇的。那么也不會出現(xiàn)不穩(wěn)定問題。</p><p><b>　　程序模塊說明</b></p><p><b>　　總體設(shè)計(jì)說明：</b></p><p>　　程序采用兩個(gè)二維數(shù)組man[max][max],woman[max][

8、max]來記錄max位男生，女生對異性的喜歡程度順序。</p><p>　　數(shù)組acman[]記錄男生下一位追求的女生順序（最開始從0位，也就是最喜歡的一位開始）；</p><p>　　數(shù)組acwoman[]記錄每一位女生當(dāng)前男友（最開始設(shè)置一位虛擬男友，其喜歡程度最小）</p><p>　　采用4個(gè)for循環(huán)，分別對4個(gè)數(shù)組初始化。</p><

9、p>　　采用一個(gè)for循環(huán)遍歷man數(shù)組（為每一位男生追求其最喜歡的女生）</p><p>　　采用一個(gè)for循環(huán)輸出結(jié)果</p><p><b>　　模塊說明：</b></p><p>　　模塊一：bool changeBF(vector<vector<int>> woman,int i,int newBF,in

10、t oldBF,int max)函數(shù)</p><p>　　概要說明：判斷某位女生的當(dāng)前男友與追求她的男友的排位順序（喜歡程度）</p><p>　　關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法及其分析（比較newBF和oldBF在數(shù)組woman[][max]的序號大小，從而判斷喜歡程度）</p><p>　　輸入（數(shù)組woman[][]）</p><p>　　輸出(b

11、ool類型1,0)</p><p>　　總結(jié)（含主函數(shù)設(shè)計(jì)說明）</p><p>　　穩(wěn)定婚姻問題被應(yīng)用到許多實(shí)際問題的處理過程中，例如學(xué)生的入學(xué)，工作招聘，醫(yī)生和醫(yī)院進(jìn)行匹配等等.雖然穩(wěn)定婚姻問題是一個(gè)NP問題，但是為找到所有的穩(wěn)定匹配結(jié)果，我們設(shè)計(jì)了基于先序遍歷森林的算法，利用此算法，對于眾多不同的婚姻匹配，不會重復(fù)判斷它們包含相同的配對子部分，這樣大大節(jié)省了時(shí)間。為了進(jìn)一步提高速度，

12、由Gale-Shapley算法的性質(zhì)得到一個(gè)定律及其推論，利用推論對算法做了進(jìn)一步改進(jìn)，減少了時(shí)間復(fù)雜度。</p><p>　　課程設(shè)計(jì)是一項(xiàng)復(fù)雜的工作，在程序設(shè)計(jì)的過程中，許多我們認(rèn)為應(yīng)該是正確的代碼，往往不能運(yùn)行我們想要的結(jié)果。這就需要我們的耐心與細(xì)心，去糾正任何一個(gè)可能的細(xì)小錯(cuò)誤。此次算法課程設(shè)計(jì)，我將所學(xué)到的知識運(yùn)用到了實(shí)踐中，雖然在設(shè)計(jì)過程中遇到很大的困難，一開始的時(shí)候并不知道穩(wěn)定婚姻問題的算法思想，但

13、是在老師和同學(xué)的幫助下，我理解了Gale-Shapley算法的思想。在數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的過程中，我試過用結(jié)構(gòu)體，鏈表等數(shù)據(jù)結(jié)構(gòu)，最后還是覺得直接用數(shù)組最簡潔。確定了用二維數(shù)組，程序就基本定下來了，主函數(shù)就是對二維數(shù)組的遍歷。為了實(shí)現(xiàn)多樣化，我在對二維數(shù)組初始化時(shí)采用了由用戶輸入實(shí)現(xiàn)初始化。這里用到了動(dòng)態(tài)數(shù)組的知識。在整個(gè)實(shí)驗(yàn)的過程中，遇到不少困難，但是最終得以克服，并且最終獲得了成功。</p><p>　　經(jīng)歷這次課

14、程設(shè)計(jì)，我深深體會到算法的神奇，我們要編寫一段代碼，首先要有一種算法思路，這是至關(guān)重要的，甚至可以成為編程的靈魂，但是算法思想比較難以想到，這就需要我們在以后的實(shí)踐中經(jīng)常鍛煉，經(jīng)常思考，培養(yǎng)自己思考能力，這樣才能不斷進(jìn)步。</p><p><b>　　五、參考文獻(xiàn)</b></p><p>　　清華大學(xué)出版社《算法設(shè)計(jì)與分析》</p><p>&

15、lt;b>　　程序及算法測試報(bào)告</b></p><p><b>　　前言</b></p><p>　　測試目的及采用的主要測試方法</p><p>　　目的：測試該程序能否成功對N對男女成功配對，且婚姻穩(wěn)定。</p><p>　　測試方法：設(shè)置不同的數(shù)據(jù)，判斷是否有錯(cuò)誤。</p><

16、;p>　　被測試程序算法說明及流程圖等</p><p><b>　　代碼：</b></p><p>　　#include<iostream></p><p>　　#include <vector> </p><p>　　using namespace std;</p>&l

17、t;p>　　void main()</p><p><b>　　{</b></p><p>　　int newBF;</p><p>　　int oldBF;</p><p><b>　　int t;</b></p><p>　　int search;</p>

18、;<p><b>　　int max;</b></p><p>　　cout<<"輸入男生人數(shù)（女生）："<<endl;</p><p><b>　　cin>>max;</b></p><p>　　int *nextm=new int[max+1

19、]; //男生下個(gè)追求女士的號碼</p><p>　　int *nextw=new int[max+1];//女士接受的男生號</p><p>　　vector<vector<int> > man(max, vector<int>(max));//男生對女士的喜歡程度順序</p><p>　　vector&l

20、t;vector<int> > woman(max, vector<int>(max+1));//女生對男生的喜歡程度順序</p><p>　　for(int i=0;i<max+1;i++)</p><p>　　nextm[i]=0;</p><p>　　for(int i=0;i<max;i++)</

21、p><p>　　nextw[i]=max;//對數(shù)組初始化</p><p>　　for(int i=0;i<max;i++)</p><p><b>　　{</b></p><p>　　cout<<"第"<<i<<"位男士喜歡女生順序?yàn)椋?quot;&l

22、t;<endl;</p><p>　　for(int j=0;j<max;j++)</p><p>　　cin>>man[i][j];</p><p><b>　　}</b></p><p>　　for(int i=0;i<max;i++)</p><p><b

23、>　　{</b></p><p>　　cout<<"第"<<i<<"位女士喜歡男生順序?yàn)椋?quot;<<endl;</p><p>　　for(int j=0;j<max;j++)</p><p>　　cin>>woman[i][j];</p&g

24、t;<p>　　woman[i][max]=max;</p><p><b>　　}</b></p><p>　　bool changeBF(vector<vector<int> > woman,int,int,int,int);</p><p>　　for(int j=0;j<max;j++)&

25、lt;/p><p><b>　　{</b></p><p>　　t=man[j][nextm[j]];//要追求的女生號</p><p>　　if(nextw[t]==j)</p><p><b>　　{//什么也不做</b></p><p><b>　　}</b

26、></p><p><b>　　else </b></p><p><b>　　{</b></p><p><b>　　newBF=j;</b></p><p>　　oldBF=nextw[t];</p><p>　　if(changeBF(wom

27、an,t,newBF,oldBF,max))</p><p><b>　　{</b></p><p>　　nextm[oldBF]++;</p><p>　　nextw[t]=newBF;</p><p>　　if(oldBF>j)</p><p><b>　　{</b>

28、;</p><p><b>　　//什么也不做</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　j=oldBF;//前任男友

29、被拋棄，且號碼小，應(yīng)讓其重新最求女生</p><p><b>　　j--;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><

30、;b>　　{</b></p><p>　　nextm[j]++;//最求不成功，繼續(xù)追求下一位喜歡的女生</p><p><b>　　j--;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><

31、;p><b>　　}</b></p><p>　　for(int j=0;j<max;j++)</p><p><b>　　{</b></p><p>　　cout<<"第"<<j<<"位男士"<<"的女友是&qu

32、ot;<<man[j][nextm[j]]<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　bool changeBF(vector<vector<int> > woman,int i,int newBF,

33、int oldBF,int max)</p><p><b>　　{</b></p><p>　　int temp1;</p><p>　　int temp2;</p><p>　　for(int j=0;j<=max;j++)</p><p><b>　　{</b>&

34、lt;/p><p>　　if(woman[i][j]==newBF)</p><p><b>　　{</b></p><p><b>　　temp1=j;</b></p><p><b>　　break;</b></p><p><b>　　}&l

35、t;/b></p><p><b>　　}</b></p><p>　　for(int j=0;j<=max;j++)</p><p><b>　　{</b></p><p>　　if(woman[i][j]==oldBF)</p><p><b>　　

36、{</b></p><p><b>　　temp2=j;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　re

37、turn(temp1<temp2);//比較前任與現(xiàn)任的排序先后</p><p><b>　　}</b></p><p><b>　　測試環(huán)境說明</b></p><p>　　系統(tǒng)：WINDOWS 7</p><p>　　測試環(huán)境：visual studio 8</p><

38、p><b>　　測試用例說明</b></p><p><b>　　測試用例1</b></p><p>　　目的：判斷是否一對一的配對</p><p><b>　　輸入</b></p><p>　　預(yù)期輸出：不會出現(xiàn)重復(fù)數(shù)字</p><p><

39、b>　　實(shí)際輸出</b></p><p>　　測試結(jié)果：顯示每一位男生都唯一配對以為女生</p><p><b>　　測試用例2</b></p><p>　　目的：測試每一位配對的組合是否婚姻穩(wěn)定</p><p><b>　　輸入</b></p><p>　

40、　預(yù)期輸出：0 3 2 1</p><p><b>　　實(shí)際輸出</b></p><p>　　測試結(jié)果：配對婚姻穩(wěn)定</p><p><b>　　3．測試用例3</b></p><p>　　目的：繼續(xù)測試每一對情侶婚姻是否穩(wěn)定</p><p><b>　　輸入<

41、;/b></p><p>　　預(yù)期輸出：1 0 2</p><p><b>　　實(shí)際輸出</b></p><p>　　測試結(jié)果：配對婚姻穩(wěn)定</p><p><b>　　測試結(jié)果分析</b></p><p>　　測試結(jié)果顯示，每一位男生其配對的女生都是唯一的；每一位情侶