算法設計與分析課程設計報告——穩(wěn)定婚姻問題的gale-shapley算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、lt;b>　　程序及算法測試報告</b></p><p><b>　　前言</b></p><p>　　測試目的及采用的主要測試方法</p><p>　　目的：測試該程序能否成功對N對男女成功配對，且婚姻穩(wěn)定。</p><p>　　測試方法：設置不同的數據，判斷是否有錯誤。</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<<"輸入男生人數（女生）："<<endl;</p><p><b>　　cin>>max;</b></p><p>　　int *nextm=new int[max+1

19、]; //男生下個追求女士的號碼</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;//對數組初始化</p><p>　　for(int i=0;i<max;i++)</p><p><b>　　{</b></p><p>　　cout<<"第"<<i<<"位男士喜歡女生順序為："&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<<"位女士喜歡男生順序為："<<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、被拋棄，且號碼小，應讓其重新最求女生</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);//比較前任與現任的排序先后</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>　　預期輸出：不會出現重復數字</p><p><

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

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

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