匹配算法MATLAB

《匹配算法MATLAB》由会员分享，可在线阅读，更多相关《匹配算法MATLAB（4页珍藏版）》请在装配图网上搜索。

1、求二部图G的最大匹配的算法（匈牙利算法），其基本思想是：从G的任意匹配M开始,对X中所有M的非饱和点，寻找M-增广路.若不存在M-增广路，则M为最大匹配;若存在M-增广路P,则将P中M与非M的边互换得到比M多一边的匹配Ml,再对M1重复上述过程.设G=（X,Y,E）为二部图，其中X=xl,x2,xn,Y=yl,y2,yn.任取G的一初始匹配M（如任取eWE,贝UM=e是一个匹配）. 令S=f,T=f,转向. 若M饱和XS的所有点，则M是二部图G的最大匹配.否则，任取M的非饱和点uWXS,令S=SUu,转向. 记N（S）=vIuWS,uvWE.若N（S）=T,转向.否则取yWN（S）T.若y是M

2、的饱和点,转向,否则转向. 设xyWM,贝U令S=SUx,T=TUy,转向. u-y路是M-增广路，设为P,并令M=MP,转向.这里MP=MUPMAP,是对称差.由于计算M-增广路P比较麻烦，因此将迭代步骤改为： 将X中M的所有非饱和点（不是M中某条边的端点）都给以标号0和标记*,转向. 若X中所有有标号的点都已去掉了标记*,Um是G的最大匹配.否则任取X中一个既有标号又有标记*的点xi,去掉xi的标记*,转向. 找出在G中所有与xi邻接的点刃（即xiyjWE）,若所有这样的刃都已有标号,则转向,否则转向. 对与xi邻接且尚未给标号的yj都给定标号i.若所有的刃都是M的饱和点，则转向,否则逆向

3、返回.即由其中M的任一个非饱和点刃的标号i找到xi,再由xi的标号k找到yk，,最后由yt的标号s找到标号为0的xs时结束，获得M-增广路xsytxiyj,记P=xsyt,xi刃,重新记M为MP,转向. 将yj在M中与之邻接的点xk（即xkyjWM）,给以标号j和标记*,转向.例1求图6-9中所示的二部图G的最大匹配.71丁2为丁4兀匈牙利算法的MATLAB程序代码如下：m=5;n=5;A=0110011011011000110000011;M(m,n)=0;for(i=1:m)for(j=1:n)if(A(i,j)M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j)b

4、reak;end;end%获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end%将记录X中点的标号和标记*for(i=1:n)y(i)=O;end%将记录Y中点的标号和标记*for(i=1:m)pd=1;%寻找X中M的所有非饱和点for(j=1:n)if(M(i,j)pd=0;end;endif(pd)x(i)=-n-1;end;end%将乂中M的所有非饱和点都给以标号0和标记*,程序中用n+1表示0标号,标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)v0)xi=i;break;end;end%假如X中存在一个既有标号

5、又有标记*的点,则任取X中一个既有标号又有标记*的点xiif(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都给以标号iif(k1)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%将力在M中与之邻接的点xk(即xkyjM),给以标号j和标记*if(

6、pdd)break;end;endif(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-增广路Pk=k+1;endfor(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;endif(pd)brea

7、k;end;end%假如X中所有有标号的点都已去掉了标记*,算法终止M%显示最大匹配M,程序结束图6-9利用可行点标记求最佳匹配的算法步骤如下：设G=(X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标记,通常取L(x)maxb(xy)IygY,xgX口厶,人，(M是G的一个匹配L(y)0,ygYl 若X的每个点都是M的饱和点，则M是最佳匹配.否则取M的非饱和点uex,令S=u,T=f,转向. 记NL(S)=vIueS,uvWEL.若NL(S)=T,则GL没有完美匹配，转向.否则转向. 调整可行点标记,计算aL=minL(x)+L(y)F(xy)IxeS,yeYT.由此得新的可行顶点标

8、记L(v)a,vgS,LL(v)+a,vgT,L、L(v),否则令L=H,GL=GH,重新给出GL的一个匹配M,转向. 取yeNL(S)T,若y是M的饱和点，转向.否则，转向. 设xyeM,贝U令S=SUx,T=TUy,转向. 在GL中的uL(S(i),1)+L(j,2)-A(S(i),j)al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;endfor(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)%

9、生成子图GLif(L(i,1)+L(j,2)=A(i,j)Gl(i,j)=1;elseGl(i,j)=0;endM(i,j)=0;k=0;end;endii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j)ii=i;jj=j;break;end;endif(ii)break;end;end%获得仅含Gl的一条边的初始匹配MM(ii,jj)=1;breakelse%NL(S)HTfor(j=1:jsn)pd=1;%取ywNL(S)Tfor(k=1:jst)if(T(k)=NlS(j)pd=0;break;end;endif(pd)jj=j;break;end;endpd

10、=0;%判断y是否为M的饱和点for(i=1:n)if(M(i,NlS(jj)pd=1;ii=i;break;end;endif(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj);%S=Sux,T=Tuyelse%获得Gl的一条M-增广路，调整匹配Mfor(k=1:jst)M(S(k),T(k)=1;M(S(k+1),T(k)=0;endif(jst=0)k=0;endM(S(k+1),NlS(jj)=1;break;end;end;end;endMaxZjpp=0;for(i=1:n)for(j=1:n)if(M(i,j)MaxZjpp=MaxZjpp+A(i,j);end;end;endM%显示最佳匹配MMaxZjpp%显示最佳匹配M的权，程序结束