用匈牙利算法解決相親類型問題的數(shù)學模型-預覽頁
【正文】 ACD29BBABB注：表中的要求條件一般是指不低于所給的條件。一般認為，男青年至多比女青年的年齡大5歲，或女青年的年齡比男青年的大2歲，并且要至少滿足個人要求5項條件中的2項，才有可能配對成功。每項條件通?？梢苑譃槲鍌€等級A、B、C、D、E，如外貌、性格、氣質(zhì)、事業(yè)可分為很好、好、較好、一般、差；財富可以分為很多、多、較多、一般、少。再在矩陣R中將大于2的數(shù)字賦1反之賦0，再利用KM算法可得問題（2）的結果。 現(xiàn)在在城市大齡青年的婚姻問題引起了社會的廣泛關注，針對這一現(xiàn)象，我們給出20對青年男女的基本條件和擇偶條件的抽樣是真實可靠的。s Federation solving this problem.Key words: mathematical model。本文根據(jù)每個人的情況和要求，建立數(shù)學模型幫助婦聯(lián)解決3個問題。該單位的婦聯(lián)組織擬根據(jù)他們的年齡，基本條件和要求條件牽線搭橋。s Federation of this pany wants to wirepull for them on the basis of their age, basic condition and demand. This paper, according to everyone’s condition and demands, helps the Women39。 KM algorithm。 在模型中，根據(jù)男青年的基本條件和女青年的要求條件構造度量矩陣（權值矩陣）A，男1號的基本條件和女1號的要求條件，比如在外貌方面，男1號滿足女1號的要求則賦值為53+1，在事業(yè)方面，男1號不滿足女1號的要求，則賦值為0，按照這個方法，如果滿足條件則按公式（男青年基本條件值女青年相應的要求條件+1）賦值，反之賦值為0，這樣可以得到外貌，性格，氣質(zhì)，事業(yè)，財富五個方面的數(shù)值，并將這些數(shù)值相加得到，最終得到權值矩陣T=（）2020，同理可得，女青年的基本條件和男青年的要求條件所構成的權值矩陣S=()2020，那么男女青年配對的總權值矩陣（即為滿意度矩陣）為R1=T+S，（因為表示男i號的基本條件對j號的要求條件，表示女j號的基本條件對男i號的要求條件，那么用+ 表示男i號對女j號的總權數(shù)即為他們之間的滿意度）：再次，我們根據(jù)年齡的限制在矩陣R1中將不滿足條件的賦0，得到矩陣R，利用匈牙利算法可得到問題（1）的結果。某單位現(xiàn)在有20對大齡青年男女，每個人的基本條件都不相同，如外貌、性格、氣質(zhì)、事業(yè)、財富等。下面給出20對大齡青年男女的年齡、基本條件和要求條件（如下表）。(3)假設男女雙方都相互了解了對方的條件和要求，讓每一個人出一次選擇，只有當男女雙方相互選中對方時才認為配對成功，每一個人只有一次選擇機會。任意一對男女的配對可以看成一個隨機事件，按某一概率可能配對成功，或不成功。相互的滿意度越高，雙方配對的成功率就越大。實際中，假如一個男青年（）對一個女青年（）的滿意度最高，但對的滿意度不一定最高，即若選擇，但不一定選擇。4. 模型的假設與符號說明4．1模型的假設 (1)題目所給出的男女青年的評價是客觀真實的。于是根據(jù)上表可以得到男女青年的基本條件量化矩陣和要求條件量化矩陣（或稱權值矩陣）以及滿意度分量分別記為： 滿意度現(xiàn)在，我們對滿意度進行說明，要確定對的第K項條件的滿意度。 我們把二十個青年男女抽象化為40個結點得到一個帶權二部圖，其中Aj表示二十個男青年，Bj表示二十個女青年，而從男青年到女青年有一條帶權邊，權則由上面求得的滿意度矩陣決定，然后，我們用最大二部圖匹配算法（匈牙利算法）求出一個最大匹配的解；但是，一開始所求得的是一個有向圖，因此我們必須把它無向化，至此對問題（1）我們僅僅是采用把兩結點間權值相加而轉(zhuǎn)化為一個無向圖，進而就可以用匈牙利算法對其求解了?？梢宰C明在尋找增廣路集的每一個階段所尋找到的最短增廣路都具有相等的長度，并且隨著算法的進行最短增廣路的長度是越來越長的，更進一步分析可以證明最多只需增廣ceil(sqrt(n))次就可以得到最大匹配（證明在這里略去）。也就是說，如果一方的實際條件比對方期望（要求）的條件差距越大，則對方對另一方失望就越大，即滿意度就越小?，F(xiàn)在模型的基礎上加以改進：如果的基本條件達不到的要求，即（）時，給它賦值它是一個負值，體現(xiàn)了當一方實際條件低于期望（要求）的條件時，則對方對他（她）失望（相對于要求條件）就會增加差距越大，失望度就越大，相應的滿意度就越小。而對問題3則要在男女雙方都滿意的前提下并且是雙方都選擇了雙方。在社會上各人的擇偶標準不同，所以他們在選擇對象的側重點也會不同，比方說；有的人會特別注重外表，然而有的人特別注重對方的事業(yè)和個人的氣質(zhì)等等。另外本文的完成還得到了羅光輝同學和李鵬同學的幫助，在此也對他們表示衷心的感謝。 int n,m,edge,num。iv[s].size()。 if(list[point]==1 || dfs(point)){ list[point] = s。 bool flog = false。 for(i=0。j++) if(list[v[i][j]] == 1) { mark1[i] = false。 break。 for(j=0。 mark2[point] = false。 } } }mark1[i] = false。 while(cinn) { if(n == 0)break。 for(i=0。 } Solve()。 const int INF = 100000000。 void KM_Perfect_Match(const int n, const int edge[][size]) { // i n。 j n。 } bool perfect = false。 初始化鄰接矩陣 for(i = 0。 for(j = 0。 for(i = 0。memset(xckd, false, sizeof(xckd))。 // 修改標號過程 xckd[i] amp。 } i++) { if(xckd[i]) lx[i] = ex。 } } int i。 i n。 int t = match[i]。 } int main() { edge[i][j]為連接Xi與Yj的邊的權值 *保存二分圖中X與Y的頂點數(shù)n,若上一步不等應保 int cost = 0。 i n。 } 1
數(shù)學相關推薦
鄂ICP備17016276號-1