匹配问题与匈牙利算法和较大基数匹配.docx

图论-浅谈匹配问题1匹配问题的起源匹配理论起源于组合数学中著名的婚配问题：若在一个团体中有若干待婚的小伙子和姑娘，所有人都已到结婚年龄，若没有其他条件的限制，为了满足姑娘的愿望，唯一的必备条件就是小伙子的人数至少和姑娘的人数一样多。但是在事实上，所有人都不会草率地处理自己的终身大事，以姑娘为例（与小伙子的情况是完全相同的），每个姑娘往往会排除一些小伙子作为她们可能的配偶，也即每个姑娘都会有一个有序的可接受的配偶名单。那么会有一个问题出现：在这个团体中是否每个姑娘都可以嫁给自己认可的小伙子？显然，上述问题并非是永远可以的，因为或许有几个姑娘手头上的名单是完全一样的。而既然上述问题并非永远可行，那么什么条件下可以满足上述要求？在并满足这些条件的时候，最多会有几位姑娘可以实现自己的愿望？如何配对，才能使得最终的团体中婚后的家庭更为美满？为了解决诸如此类的问题，人们发展得到了一种匹配理论和诸多有效算法。2图论相关知识若图G的所有顶点能够分为两个非空子集X和，并且每条边都有一个顶点在中，而另一个顶点在Y中，则称此图是二分图或者偶图；而如果X的每个顶点都与Y的每个顶点相连，则称此图为完全二分图或者完全偶图。设M是图G=（V,E）的边集E的子集，如果M的任何两边都不邻接，则称M为G的一个匹配；匹配M中边元素个数称为此匹配的基数，而在匹配M中边的端点称为M-饱和点，其他的端点称为M-未饱和点。若G中的每个顶点都是M-饱和点，也即匹配M将G中的所有顶点进行了配对，那么称M为G的完美匹配；而在图G中不存在另一个匹配M，使得MM，则称M为最大匹配，其中M称为图G的匹配数。设M是G的一个匹配，G的M交错路是指其边在EM和M中交错出现的路。M可扩路是指其起点和终点都是M未饱和的M交错路。以下结论是在二分图中寻找最大匹配和最佳匹配算法的理论基础：定理1： G的匹配M是最大匹配当且仅当G不包含M可扩路。定理2： 设X，Y为二分图G的二分类，则G包含饱和X的每个顶点的匹配当且仅当N(S)S，对所有SX成立其中N(S)为G中S的临集，即为与S的顶点相邻的所有顶点的集合。定理3： G有完美匹配当且仅当oG-SS，对所有的SV成立其中，oG-S为图G的奇分支（图的分支根据它有奇数或者偶数个顶点而分别称为奇分支或偶分支）的个数。3几个典型的匹配算法由于刚接触到图论知识，碍于在图论方面能力有限，因此本文在本节中选择性地介绍了三个图论匹配问题中比较经典的算法：婚配问题的Gale-Shapley算法、最大匹配的匈牙利算法和图论中的较大基数匹配算法，并且对匈牙利算法和较大基数匹配算法进行了matlab代码实现。3.1 婚配问题婚配问题可以说是一个相对经典的图论匹配算法的入门问题。假设对于n个男人的集合M=m1,m2,mn和n个女人的集合W=w1,w2,wn。在男人女人进行匹配的情况下，就会产生一个如何进行完美匹配的问题。在这个问题背景下，进一步加入优先的概念：根据实际情况，每个男人mM将对所有女人进行排名，如果m给w的排名高于w，那么我们就说m偏爱w超过w，因此我们将把m的按顺序的排名作为他的优先表。依照常理来看，每个男人都会按照自己的优先表顺序从高向低依次进行求婚，直到被接受为止。那么，接下来本文将讨论如何生成一个稳定的完美匹配。Gale和Shapley两人根据自己对申请人-雇主之间关系的研究，提出了Gale-Shapley算法，具体算法描述如下：初始所有的mM和wW都是自由的while 存在男人m是自由的且还没对每个女人都求过婚 选择这样的一个男人m 令w为m的优先表中还没有求过婚的最高排名的女人 if w是自由的 (m,w）变为约会状态 else w当前与m约会 if w是更加偏爱m而不爱m m保持自由 else w更加偏爱m而不爱m (m,w)变为约会状态 m变为自由 end end end输出约会状态的所有匹配集合S分析Gale-Shapley算法，可以得到以下结论：结论1： G-S算法至多在n2次while循环的迭代之后终止；结论2： 程序终止时返回的集合S为一个完美匹配；结论3： 考虑G-S算法的一次执行，结果为一个集合S，且S是一个稳定匹配；结论4： G-S算法的每次执行最终得到的匹配集合是相同的；结论5： 稳定匹配集合S中，每个女人与她最差（即排名最低）的有效伴侣匹配。由结论5，在G-S算法中，主动进行求婚的一方以最佳可能的稳定匹配结束，而另一方则以最差可能的稳定匹配结束。3.2 匈牙利算法二分图的匹配问题是图的最大匹配问题的特殊类型。对于一个二分图G=（X,Y,E），我们可以利用匈牙利算法对其进行最大匹配。其基本的思想为：从G的任意匹配M开始,对X中所有M的非饱和点,寻找M-增广路。 若不存在M-增广路,则M为其最大匹配;若存在M-增广路P,则将P中M与非M的边互换得到比M多一边的匹配M1,再对M1重复上述过程。匈牙利算法具体的运行过程为：输入：G的一个初始匹配M输出：满足要求的最大匹配任意给出G的一个初始匹配Mif M饱和了X中的所有节点 则M是G的一个完全匹配else找出X中的非饱和点x，令A=x，B=； 考察A的邻接点 if N(A)=B 计算结束 else 在Y中找出一点y属于N(A)-B if y为M的饱和点 在X中找出y的配对点z，令A=Az,B=By,转6； else存在一条从x到y的可扩路P，故M不是G的最大匹配 end endend令M=M+E(P)，转2。根据上述运行过程，利用matlab可以很方便的进行算法的实现，程序代码如下：（其中A为X与Y的邻接矩阵，M为X与之间的匹配，为中顶点个数，为中顶点个数，最终的最大匹配结果为矩阵）m= ;n= ;M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j)M(i,j)=1;break;endend if(M(i,j)break;endend while(1)for(i=1:m)x(i)=0;end for(i=1:n)y(i)=0;end for(i=1:m)pd=1; for(j=1:n)if(M(i,j)pd=0;endendif(pd)x(i)=-n-1;endend pd=0;while(1)xi=0;for(i=1:m)if(x(i)1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)x(i)=-yy(j);pdd=0;break;endendif(pdd)break;end;endif(pdd)k=1;j=yy(j); while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j); if(j=n+1)break;end k=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)M(P(i,1),P(i,2)=0; else M(P(i,1),P(i,2)=1;endend break;endendendif(pd)break;endend M; 上述算法中，由于二分图的一切M-可增长路径都是一个顶点在X中，另一个在Y中的非渗透点，因此上述方法对X中的所有非渗透点出发的交错路径都进行搜索，如果搜索不到可增长路径，说明图中不存在任何的可增长路径，因而最终得到的匹配为最大匹配。通过下例可以清楚的看到程序运行需要的输入以及运行结束时的输出结果：例：有个顶点，Y有4个顶点，且已知它们之间的邻接矩阵A为A = 则利用上述代码，取m=5，n=4，进行计算可以得到最终的匹配结果M：M =3.3 较大基数匹配算法对于图G，求其较大基数匹配算法的基本步骤为：1. 任意取得图G中一边，将其存入匹配M中；2. 从图G中将与匹配M中的每一条边相邻的所有边删除；3. 直到所剩子图全为孤立顶点，算法结束；否则，转1编程对其进行实现，代码如下：（其中，M表示图G的邻接矩阵，S表示匹配结束时所有顶点之间的邻接矩阵）n=size(M,1);%这里M表示邻接矩阵S=zeros(n,n);%S为程序的输出结果，这里S表示较大基数的匹配矩阵while sum(sum(M)=0a=find(M=0);t1=mod(a(1),n);if t1=0t1=n;endif a(1)/nfloor(a(1)/n)t2=floor(a(1)/n)+1;elset2=floor(a(1)/n);endS(t1,t2)=1;S(t2,t1)=1;M(t1,:)=0;M(t2,:)=0;M(:,t1)=0;M(:,t2)=0;endS同样举例说明其运行过程：例：假设图G=(X,Y)，其中X、Y的邻接矩阵A为：