最大匹配算法(匈牙利算法) matlab程序
1、文档下载：
本算法已整理成文档如下。有需要的朋友可以点击下载
| 序号 | 文档(点击下载) |
|---|---|
| 本项目文档 | 匹配算法MATLAB.docx |
2.算法详解:
最大匹配算法(匈牙利算法)， 其基本思想是：从G的任意匹配M开始, X中所有M的非饱和点， 寻找M-增广路. 若不存在M-增广路, M是最大匹配； 若存 在M-增广路P, 则将P中M与非M边的交换比M多匹配M1 , 再对M1 重复上述过程.
设G= (X,Y,E)为二部图, 其中X= {x1,x2, ? ,xn},Y= {y1,y2, ? ,yn}. 一开始任取G 始匹配M(如任取e∈E, 则M= {e}是匹配). ① 令S=f,T=f, 转向②. ② 若M饱和X\S的所有点, M是二部图G最大的匹配. 否则, 任取M的非饱和点 u∈X\S, 令S=S∪{u}, 转向③. ③ 记N(S) = {v| ?u∈S,uv∈E}. 若N(S) =T, 转向②. 否则取y∈N(S) \?T. 若y是M 的饱和点, 转向④, 否则转向⑤. ④ 设x y∈M, 则令S=S∪{x},T=T∪{y}, 转向③. ⑤u-?y路是M-增广路, 设为P, 并令M=M⊕P, 转向①. 这里M⊕P=M∪P\?M∩P, 是对称差.
由于计算M-增广路P比较麻烦， 因此，将迭代步骤改为： ① 将X中M所有非饱和点(不是M中某条边的端点)都标有0 和标记*, 转向②. ② 若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则，任命X中一 既有标号又有标记的点xi, 去掉xi的标记, 转向 ③ 找出G中的所有和xi邻接的点yj(即xi yj∈E), 若所有这些yj都有标号， 则转向 ②, 否则转向④. ④ 对与xi相邻且尚未给出标号的yj都给定标号i. 若所有的yj都是M的饱和点， 则转向⑤, 否则逆向返回. 也就是说，M的任何不饱和点yj找到标号ixi, 再由xi找到标号kyk, ? , 最后由yt找到标号为0的标号s 的xs时结束, 获得M-增广路xs yt?xi yj, 记P= {xs yt, ? , xi yj}, 重新记M为M⊕P, 转向①. ⑤ 将yj与M相邻的点xk(即xk yj∈M), 给标号j和标记*, 转向②. 例1求图 6-9 二部图G的最大匹配. 
匈牙利算法 MATLAB 程序代码如下：
m=5;n=5;A=[0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1]; M(m,n)=0; for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%求初始匹配M if(M(i,))break;end;end%获得仅含一条边的初始匹配M
while(1)
for(i=1:m)x(i)=0;end%将记录X中点的标号和标记*
for(i=1:n)y(i)=0;end%将记录Y中点的标号和标记*
for(i=1:m)pd=1;%寻找X中M的所有非饱和点
for(j=1:n)if(M(i,j))pd=0;end;end
if(pd)x(i)=-n-1;end;end%将X中M的所有非饱和点都给以标号0 和标记*, 程序中用n+1 表
示0 标号, 标号为负数时表示标记*
pd=0;
while(1)xi=0;
for(i=1:m)if(x(i)<0)xi=i;break;end;end%假如X 中存在一个既有标号又有标记*的点, 则任
取X中一个既有标号又有标记*的点xi
if(xi==0)pd=1;break;end%假如X中所有有标号的点都已去掉了标记*, 算法终止
x(xi)=x(xi)*(-1);%去掉xi 的标记*
k=1;
for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;end%对与xi 邻接且尚未给标号的yj 都
给以标号i
if(k>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;end;end%将yj 在M中与之邻接的
点xk (即xkyj∈M), 给以标号j 和标记*
if(pdd)break;end;end
if(pdd)k=1;j=yy(j);%yj 不是M的饱和点
while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%任取M的一个非饱和点yj, 逆向返回
if(j==n+1)break;end%找到X中标号为0 的点时结束, 获得M-增广路P
k=k+1;end
for(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0;%将匹配M 在增广路P 中出现的边
去掉
elseM(P(i,1),P(i,2))=1;end;end%将增广路P 中没有在匹配M中出现的边加入
到匹配M中
break;end;end;end
if(pd)break;end;end%假如X中所有有标号的点都已去掉了标记*, 算法终止
M%显示最大匹配M, 程序结束
图 6-9 利用可行点标记求最佳匹配的算法步骤如下： 设G= (X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标记, 通常取
① 若X的每个点都是M的饱和点, 则M是最佳匹配. 否则取M的非饱和点u∈X, 令S = {u},T=f, 转向②. ② 记NL(S) = {v| u∈S,uv∈EL}. 若NL(S) =T, 则GL没有完美匹配, 转向③. 否则转 向④. ③ 调整可行点标记, 计算 aL= min {L(x) +L(y) -F(x y) |x∈S,y∈Y\T}. 由此得新的可行顶点标记
令L=H,GL=GH, 重新给出GL的一个匹配M, 转向①. ④取y∈NL(S) \T,若y是M的饱和点,转向⑤.否则,转向⑥. ⑤设x y∈M,则令S=S∪{x},T=T∪{y},转向②. ⑥在GL中的u-y路是M-增广路,记为P,并令M=M⊕P,转向①. 利用可行点标记求最佳匹配算法的MATLAB程序代码如下：
n=4;A=[4 5 5 1
2 2 4 6
4 2 3 3
5 0 2 1];
for(i=1:n)L(i,1)=0;L(i,2)=0;end
for(i=1:n)for(j=1:n)if(L(i,1)<A(i,j))L(i,1)=A(i,j);end;%初始可行点标记L
M(i,j)=0;end;end
for(i=1:n)for(j=1:n)%生成子图Gl
if(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;
elseGl(i,j)=0;end;end;end
ii=0;jj=0;
for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;end
if(ii)break;end;end%获得仅含Gl的一条边的初始匹配M
M(ii,jj)=1;
for(i=1:n)S(i)=0;T(i)=0;NlS(i)=0;end
while(1)
for(i=1:n)k=1;
否则.
for(j=1:n)if(M(i,j))k=0;break;end;end
if(k)break;end;end
if(k==0)break;end%获得最佳匹配M,算法终止
S(1)=i;jss=1;jst=0;%S={
xi}, T=φ
while(1)
jsn=0;
for(i=1:jss)for(j=1:n)if(Gl(S(i),j))jsn=jsn+1;NlS(jsn)=j;%NL(S)={
v|u∈S,uv∈EL}
for(k=1:jsn-1)if(NlS(k)==j)jsn=jsn-1;end;end;end;end;end
if(jsn==jst)pd=1;%判断NL(S)=T?
for(j=1:jsn)if(NlS(j)~=T(j))pd=0;break;end;end;end
if(jsn==jst&pd)al=Inf;%如果NL(S)=T,计算al, Inf为∞
for(i=1:jss)for(j=1:n)pd=1;
for(k=1:jst)if(T(k)==j)pd=0;break;end;end
if(pd&al>L(S(i),1)+L(j,2)-A(S(i),j))al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;end
for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end%调整可行点标记
for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end%调整可行点标记
for(i=1:n)for(j=1:n)%生成子图GL
if(L(i,1)+L(j,2)==A(i,j))Gl(i,j)=1;
elseGl(i,j)=0;end
M(i,j)=0;k=0;end;end
ii=0;jj=0;
for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;end
if(ii)break;end;end%获得仅含Gl的一条边的初始匹配M
M(ii,jj)=1;break
else%NL(S)≠T
for(j=1:jsn)pd=1;%取y∈NL(S)\T
for(k=1:jst)if(T(k)==NlS(j))pd=0;break;end;end
if(pd)jj=j;break;end;end
pd=0;%判断y是否为M的饱和点
for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;end
if(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj);%S=S∪{
x}, T=T∪{
y}
else%获得Gl的一条M-增广路,调整匹配M
for(k=1:jst)M(S(k),T(k))=1;M(S(k+1),T(k))=0;end
if(jst==0)k=0;end
M(S(k+1),NlS(jj))=1;break;end;end;end;end
MaxZjpp=0;
for(i=1:n)for(j=1:n)if(M(i,j))MaxZjpp=MaxZjpp+A(i,j);end;end;end
M%显示最佳匹配M
MaxZjpp%显示最佳匹配M的权,程序结束