圖論最優(yōu)化算法

1、非誠勿擾男女最優(yōu)組合摘要：本文主要內容為尋求最大權匹配問題，即利用圖論的最大權匹配知識，為非誠勿擾節(jié)目中的男女嘉賓進行最優(yōu)組合。本文將其轉化為二部圖尋找最大權匹配的問題。關鍵詞：非誠勿擾，最大權匹配1、 問題描述 非誠勿擾是中國江蘇衛(wèi)視制作的一檔大型生活服務類節(jié)目。每期節(jié)目大部分都是5位男嘉賓，24位女嘉賓，女生有“爆燈”權利。首先男嘉賓選擇心動女生，女嘉賓在“愛之初體驗”根據第一印象選擇是否留燈；然后在“愛之再判斷”了解男嘉賓的一些基本情況，比如愛好、情感經歷等；接下來在“愛之終決選”通過男嘉賓親人或朋友的情況了解男嘉賓，做出最后的決定，如果有女生留燈的話就進入“男生權利”，男生做出最后選擇

2、，如果沒有女生留燈則只能遺憾離場。 2、 模型建立 通過觀看20150124期節(jié)目，這期節(jié)目只有4位男嘉賓，然后在整個節(jié)目男女嘉賓交流過程中4號、19號、22號、23號女嘉賓都沒有發(fā)過言，沒有了解到這四位女嘉賓的基本情況以及對男嘉賓的要求，所以在本次模型建立過程中沒有考慮這四位女嘉賓。經過上述分析，本期產生了4位男嘉賓和20位女嘉賓的可能匹配，我們將這4位男嘉賓和20位女嘉賓劃分為X部和Y部，男生為X1，X2，X3，X4，女生為Y1，Y2，Y3，.Y20。Xi與Yj之間連線，當且僅當它們所代表的男女雙方滿足彼此尋找另一半的某些要求，或者女生是男嘉賓選擇的心動女生。由以上分析得到如圖2.1所示的

3、二部圖。如何定義該二部圖的權值：首先，每位男嘉賓的心動女生基本權值為1，其余女嘉賓的基本權值為0，然后根據男女嘉賓雙方對對方的要求，在外貌、工作、性格、愛好、家庭五個方面基本相符就加1，差別很大就不加。得到如圖2.2所示的加權圖。 顯然，為這些男女嘉賓找最優(yōu)組合就轉化為二部圖（X，Y）尋找最大權匹配 圖 2.1 圖 2.2 圖 2.23、 模型求解本模型用匈牙利算法來進行求解。其中S表示交錯樹中屬于X的頂點集；T表示交錯樹中屬于Y的頂點集；F（Y）表示Y的父親；N（S）表示S的鄰域；A(Xi)表示Xi的鄰接點集；Wij表示XiYj邊上的權。求解步驟如下：1) 給出初始標號： L(X1)=max

4、1,2,0,0,0,2,0,0,0,0,2,2,0,0,1,0,0,0,0,0=2 L(X2)=max0,0,3,0,3,0,0,0,0,0,0,3,0,1,0,1,0,2,0,0=3 L(X1)=max1,2,0,0,0,2,0,0,0,0,2,2,0,0,1,0,0,0,0,0=2 L(X2)=max0,0,3,0,3,0,0,0,0,0,0,3,0,1,0,1,0,2,0,0=3 L(X3)=max0,4,0,0,0,5,2,2,3,0,4,0,1,0,0,0,5,0,1,0=5 L(X4)=max0,0,0,2,0,0,0,0,0,4,0,0,0,0,3,0,0,0,0,4=4 L(Y

5、1)=L(Y2)=L(Y3)=L(Y5)=L(Y6)=L(Y7)=L(Y8)=L(Y9)=L(Y10)=L(Y11)=L(Y12)=L(Y13)=L(Y14)=L(Y15)=L(Y16)=L(Y17)=L(Y18)=L(Y20)=L(Y21)=L(Y24)=02) 求出AGl(Xi)及匹配M： AGl(X1) = Y2 ,Y7 ,Y12 ,Y13 AGl(X2) = Y3 ,Y6 ,Y13 AGl(X3) = Y7 ,Y18 AGl(X4) = Y11 ,Y24 對應等子圖Gl如圖3.1所示，求得匹配M，M=X1Y13，X3Y7，X4Y24。如圖3.1黑線所示 。x1 。X2 。X3 。X4

6、。 。 。 。 。 。 。 。 。 Y2 Y3 Y6 Y7 Y11 Y12 Y13 Y18 Y24 圖 3.13） X2是非滲透點，u=X2 ,用匈牙利算法求出以u為根的M交錯樹得：S=X1，X2 ，X3, T=Y7，Y13，N(S)=Y2，Y3，Y6，Y7，Y12，Y13，Y18。 因NGl(S) T，找一點Y3 A(X2)-T, F(Y3)X2。因Y3 是M非滲透點，故得一條M可增長路徑P = X2Y3 E（P）= X2Y3因而得到新匹配 M = ME（P）= X1Y13，X3Y7，X4Y24, X2Y3 4）至此已滲透X中所有頂點，M即為最大權匹配。此時得到的男女最優(yōu)組合為：1號男嘉賓吳

7、楷與13號女嘉賓肖俊，吳楷是一個帥氣、認真、努力、愛好中國古文化但不是很擅長交際的專一型外國男生，對另一半的要求是活波、喜歡冒險、運動的女生，與13號女嘉賓要求男方要做到誠實相待、善良不撒謊、會照顧人相符，相處之后女生活波的一面也會帶動男生；2號男嘉賓張濤與3號女嘉賓張馨予，雙方都屬于自己創(chuàng)業(yè)，也都有一定的成就，在生活中有很多話題、很多共鳴，而且女生屬于膽大心細、溫柔不強勢類型，是男嘉賓心中的理想型，女生希望無論戀愛還是結了婚，對方都不要有欺騙，更不要輕易放棄，發(fā)生任何事情都要堅持，婚后不介意和對方家人住一起，與男嘉賓工作能力強、不善交際、踏實肯干十分相符；3號男嘉賓張凡帆與7號女嘉賓魏鸞瑩，

8、男嘉賓成熟、熱愛生活，有夢想、有追求，與女嘉賓希望對方尊重家庭，有責任感、可以分享周遭的許多事情十分相符，而且兩人在節(jié)目中互動也挺多，更幸運的是兩人還在同一城市。4號男嘉賓丁騰與24號女嘉賓顧欣偉，男嘉賓年少有為，但有點大男子主義，女嘉賓屬于溫婉、居家類型，而且為男嘉賓一路留燈到最后，需要很大勇氣，很有緣分的是兩人穿的是情侶裝。但最后得到的最大權匹配也只是建立在本模型中理論上的，與節(jié)目最終的結果還是有區(qū)別的，最后只有最大權匹配中的兩對牽手成功。附加題：校園導游任意兩景點求最短路徑方案：校園導游為用戶提供平面圖中任意兩點間的問路查詢，即查詢任意兩個景點間的最短路徑，旨在為用戶的旅游大大提高效率。

9、用無向網表示學校的平面圖，設計了該平面圖的存儲結構，并應用Dijkstra算法實現了查詢圖中任意兩個景點間的最短路徑的功能，為用戶熟悉校園環(huán)境提供了方便。算法描述：s為源，wu,v為點u和v之間的邊的長度，結果保存在dist。 初始化：源的距離dists設為0，其他的點距離設為無窮大(實際程序里設成-1了)，同時把所有的點的狀態(tài)設為沒有擴展過。 循環(huán)n-1次： 1) 在沒有擴展過的點中取一距離最小的點u，并將其狀態(tài)設為已擴展。 2) 對于每個與u相鄰的點v，如果distu+G.edgesuv<distv，那么把disv更新成更短的距離distu+wu,v。此時到點v的最短路徑上，前一個節(jié)

10、點即為u。 3) 結束。此時對于任意的u，distu就是s到u的距離。 景點1到各點最短路徑 鄰接矩陣如圖1所示 0 340 320 360 0 150 600 0 300 150 0 250 430 0 180 W = 0 100 290 0 150 0 430 0 150 0 450 0 380 0 圖 1 Dijkstra各次迭代各變量值的變化情況如下表1所示迭代 L(ui)父親uuiu2u3u4u5u6u7u8u9ui0ui1ui210U120340320360U1U330340320620360U1U240340320940620360U1U1250340320940620360U3

11、U760340320940720620740360U7U670340320940900720620910740360U9U11803403209409007206209101290740360U6U5903403209409007206209101060740360U6U910034032094090072062013409101060740360U2U411034032094090072062013409101060740360U9U1012034032094090072062013409101060740360U4U8利用算法的父點追蹤便可得到從U1到其余各點的最短路徑。部分代碼：void

12、 Dijkstra(int v, int w)int distMAXV, pathMAXV; /dist記錄頂點到其他各點的權值，path記錄源點到其余各點是否有路徑int sMAXV; /s記錄經過的頂點int mindis, i, j, u; for(i = 0; i < G.vexnum; i +)disti = G.edgesvi; /距離初始化si = 0; /s置空if(G.edgesvi < INF) /路徑初始化pathi = v;elsepathi = -1;sv = 1; pathv = 0; /源點編號v放到s中/循環(huán)直到所有頂點的最短路徑都求出for(i = 0; i < G.vexnum; i +)mindis = INF; /mindis置最小長度初值for(j = 0; j < G.vexnum; j +)if(sj = 0 && distj < mindis)u