图论最优化算法.

非诚勿扰男女最优组合 摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述 《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立 通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要求，所以在本次模型建立过程中没有考虑这四位女嘉宾。 经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生为Y1，Y2，Y3，....Y20。Xi与Yj之间连线，当且仅当它们所代表的男女双方满足彼此寻找另一半的某些要求，或者女生是男嘉宾选择的心动女生。由以上分析得到如图2.1所示的二部图。 如何定义该二部图的权值：首先，每位男嘉宾的心动女生基本权值为1，其余女嘉宾的基本权值为0，然后根据男女嘉宾双方对对方的要求，在外貌、工作、性格、爱好、家庭五个方面基本相符就加1，差别很大就不加。得到如图2.2所示的加权图。 显然，为这些男女嘉宾找最优组合就转化为二部图（X，Y）寻找最大权匹配 图 2.1

图 2.2

3、模型求解 本模型用匈牙利算法来进行求解。其中S表示交错树中属于X的顶点集；T表示交错树中属于Y的顶点集；F（Y）表示Y的父亲； N（S）表示S的邻域；A(Xi)表示Xi的邻接点集；Wij表示XiYj边上的权。 求解步骤如下： 1) 给出初始标号： L(X1)=max{1,2,0,0,0,2,0,0,0,0,2,2,0,0,1,0,0,0,0,0}=2 L(X2)=max{0,0,3,0,3,0,0,0,0,0,0,3,0,1,0,1,0,2,0,0}=3 L(X3)=max{0,4,0,0,0,5,2,2,3,0,4,0,1,0,0,0,5,0,1,0}=5 L(X4)=max{0,0,0,2,0,0,0,0,0,4,0,0,0,0,3,0,0,0,0,4}=4 L(Y1)=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)=0 2) 求出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

。 。 。 。 。 。 。 。 。 Y2 Y3 Y6 Y7 Y11 Y12 Y13 Y18 Y24

图 3.1

3）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 = M△E（P）= {X1Y13，X3Y7，X4Y24, X2Y3} 4）至此已渗透X中所有顶点，M即为最大权匹配。 此时得到的男女最优组合为：1号男嘉宾吴楷与13号女嘉宾肖俊，吴楷是一个帅气、认真、努力、爱好中国古文化但不是很擅长交际的专一型外国男生，对另一半的要求是活波、喜欢冒险、运动的女生，与13号女嘉宾要求男方要做到诚实相待、善良不撒谎、会照顾人相符，相处之后女生活波的一面也会带动男生；2号男嘉宾张涛与3号女嘉宾张馨予，双方都属于自己创业，也都有一定的成就，在生活中有很多话题、很多共鸣，而且女生属于胆大心细、温柔不强势类型，是男嘉宾心中的理想型，女生希望无论恋爱还是结了婚，对方都不要有欺骗，更不要轻易放弃，发生任何事情都要坚持，婚后不介意和对方家人住一起，与男嘉宾工作能力强、不善交际、踏实肯干十分相符；3号男嘉宾张凡帆与7号女嘉宾魏鸾莹，男嘉宾成熟、热爱生活，有梦想、有追求，与女嘉宾希望对方尊重家庭，有责任感、可以分享周遭的许多事情十分相符，而且两人在节目中互动也挺多，更幸运的是两人还在同一城市。4号男嘉宾丁腾与24号女嘉宾顾欣伟，男嘉宾年少有为，但有点大男子主义，女嘉宾属于温婉、居家类型，而且为男嘉宾一路留灯到最后，需要很大勇气，很有缘分的是两人穿的是情侣装。 但最后得到的最大权匹配也只是建立在本模型中理论上的，与节目最终的结果还是有区别的，最后只有最大权匹配中的两对牵手成功。 附加题：校园导游任意两景点求最短路径 方案：校园导游为用户提供平面图中任意两点间的问路查询，即查询任意两个景点间的最短路径，旨在为用户的旅游大大提高效率。用无向网表示学校的平面图，设计了该平面图的存储结构，并应用Dijkstra算法实现了查询图中任意两个景点间的最短路径的功能，为用户熟悉校园环境提供了方便。

算法描述： s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]。 初始化：源的距离dist[s]设为0，其他的点距离设为无穷大(实际程序里设成-1了)，同时把所有的点的状态设为没有扩展过。 循环n-1次： 1) 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。 2) 对于每个与u相邻的点v，如果dist[u]+G.edges[u][v]dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。 3) 结束。此时对于任意的u，dist[u]就是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) 父 亲 u ui u2 u3 u4 u5 u6 u7 u8 u9 ui0 ui1 ui2 1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ U1 2 0 340 320 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 360 U1 U3 3 0 340 320 ∞ ∞ ∞ 620 ∞ ∞ ∞ ∞ 360 U1 U2 4 0 340 320 940 ∞ ∞ 620 ∞ ∞ ∞ ∞ 360 U1 U12 5 0 340 320 940 ∞ ∞ 620 ∞ ∞ ∞ ∞ 360 U3 U7 6 0 340 320 940 ∞ 720 620 ∞ ∞ ∞ 740 360 U7 U6 7 0 340 320 940 900 720 620 ∞ 910 ∞ 740 360 U9 U11 8 0 340 320 940 900 720 620 ∞ 910 1290 740 360 U6 U5 9 0 340 320 940 900 720 620 ∞ 910 1060 740 360 U6 U9 10 0 340 320 940 900 720 620 1340 910 1060 740 360 U2 U4 11 0 340 320 940 900 720 620 1340 910 1060 740 360 U9 U10 12 0 340 320 940 900 720 620 1340 910 1060 740 360 U4 U8

利用算法的父点追踪便可得到从U1到其余各点的最短路径。 部分代码： void Dijkstra(int v, int w) { int dist[MAXV], path[MAXV]; //dist[]记录顶点到其他各点的权值，path[]记录源点到其余各点是否有路径 int s[MAXV]; //s[]记录经过的顶点 int mindis, i, j, u; for(i = 0; i < G.vexnum; i ++) { dist[i] = G.edges[v][i]; //距离初始化 s[i] = 0; //s[]置空 if(G.edges[v][i] < INF) //路径初始化 path[i] = v; else path[i] = -1; } s[v] = 1; path[v] = 0; //源点编号v放到s中

//循环直到所有顶点的最短路径都求出 for(i = 0; i < G.vexnum; i ++){ mindis = INF; //mindis置最小长度初值