匹配算法MATLAB

1、求二部圖 G 的最大匹配的算法(匈牙利算法),其基本思想是：從 G 的任意匹配 M 開(kāi)始，對(duì) X 中所有 M 的非飽和點(diǎn),尋找 M增廣路.若不存在 M增廣路，則 M 為最大匹配；若存在 M增廣路 P,則將 P 中 M 與非 M 的邊互換得到比 M 多一邊的匹配 M1,再對(duì)M1 重復(fù)上述過(guò)程.設(shè) G=(X,Y,E)為二部圖，其中 X=x1,x2,?,xn,Y=y1,y2,?,yn.任取G 的一初始匹配 M(如任取 eCE,則 M=e是一個(gè)匹配).令S=f,T=f,轉(zhuǎn)向.若 M 飽和 XS 的所有點(diǎn)，則 M 是二部圖 G 的最大匹配.否則，任取 M 的非飽和點(diǎn)uCXS,令 S=SUu,轉(zhuǎn)向.記 N

2、(S)=v|uCS,uvCE.若 N(S)=T,轉(zhuǎn)向.否則取 yCN(ST.若 y 是 M的飽和點(diǎn)，轉(zhuǎn)向，否則轉(zhuǎn)向.設(shè) xyM,則令 S=SUx,T=TUy,轉(zhuǎn)向.u-y 路是 M-增廣路，設(shè)為 P,并令 M=MP,轉(zhuǎn)向.這里 MP=MUPMnP,是對(duì)稱差.由于計(jì)算 M-增廣路 P 比較麻煩，因此將迭代步驟改為：將 X 中 M 的所有非飽和點(diǎn)(不是 M 中某條邊的端點(diǎn))都給以標(biāo)號(hào) 0 和標(biāo)記*,轉(zhuǎn)向.若 X 中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*,則 M 是 G 的最大匹配.否則任取 X 中一個(gè)既有標(biāo)號(hào)又有標(biāo)記*的點(diǎn) xi,去掉 xi 的標(biāo)記*,轉(zhuǎn)向.找出在 G 中所有與 xi 鄰接的點(diǎn) yj(即

3、xiyjE),若所有這樣的 yj 都已有標(biāo)號(hào)則轉(zhuǎn)向，否則轉(zhuǎn)向.對(duì)與 xi鄰接且尚未給標(biāo)號(hào)的 yj都給定標(biāo)號(hào) i.若所有的 yj都是M的飽和點(diǎn)， 則轉(zhuǎn)向，否則逆向返回.即由其中 M 的任一個(gè)非飽和點(diǎn) yj 的標(biāo)號(hào) i 找到 xi,再由 xi 的標(biāo)號(hào) k找到 yk,?,最后由 yt 的標(biāo)號(hào) s 找到標(biāo)號(hào)為 0 的 xs 時(shí)結(jié)束，獲得 M-增廣路 xsyt?xiyj,記P=xsyt,?,xiyj,重新記 M 為 MP,轉(zhuǎn)向.將 yj 在 M 中與之鄰接的點(diǎn) xk(即 xkyjM),給以標(biāo)號(hào) j 和標(biāo)記*,轉(zhuǎn)向.例 1 求圖 6-9 中所示的二部圖 G 的最大匹配.x4匈牙利算法的 MATLAB 程序

4、代碼如下：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)break;end;end%獲得含一條邊的初始匹配 Mwhile(1)for(i=1:m)x(i)=0;end%將記錄 X 中點(diǎn)的標(biāo)號(hào)和標(biāo)記*for(i=1:n)y(i)=0;end%將記錄 Y 中點(diǎn)的標(biāo)號(hào)和標(biāo)記*for(i=1:m)pd=1;%尋找 X 中 M 的所有非飽和點(diǎn)for(j=1:n)if(M(i,j)pd=0;end;endif(pd)x(i)=-

5、n-1;end;end%將*中 M 的所有非飽和點(diǎn)都給以標(biāo)號(hào) 0 和標(biāo)記*,程序中用 n+1表示 0 標(biāo)號(hào)，標(biāo)號(hào)為負(fù)數(shù)時(shí)表示標(biāo)記*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;end;end%將的在 M 中與之鄰接的點(diǎn)xk(即 xkyjCM),給以標(biāo)號(hào) j 和標(biāo)記*if(pdd)break;end;endif(pdd)k=1;j=yy(j);%yj 不是 M 的飽和點(diǎn)while(1)P(k,2)=j;P(k,1)=y(j);j=ab

6、s(x(y(j);%任取 M 的一個(gè)非飽和點(diǎn) yj,逆向返回if(j=n+l)break;end%找到 X 中標(biāo)號(hào)為 0 的點(diǎn)時(shí)結(jié)束，獲得 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 中出現(xiàn)的去掉elseM(P(i,1),P(i,2)=1;end;end%將增廣路 P中沒(méi)有在匹配 M中出現(xiàn)的邊加入到匹配 M中break;end;end;endif(pd)break;end;end%假如 X 中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*,算法終止M%顯小最大匹配 M,程序結(jié)束圖 6-9利用可行點(diǎn)標(biāo)記求

7、最佳匹配的算法步驟如下：設(shè) G=(X,Y,E,F)為完備的二部賦權(quán)圖,L 是其一個(gè)初始可行點(diǎn)標(biāo)記，通常取L(x)=maxIFxy|yYJ,xXlyJiy,M是GL的一個(gè)匹配L(y)=0,yY若 X 的每個(gè)點(diǎn)都是 M 的飽和點(diǎn)，則 M 是最佳匹配.否則取 M 的非飽和點(diǎn) uX,令 S=u,T=f,轉(zhuǎn)向.記 NL(S)=v|uCS,uvCEL.若 NL(S)=T,貝 UGL 沒(méi)有完美匹配，轉(zhuǎn)向.否則轉(zhuǎn)向.調(diào)整可行點(diǎn)標(biāo)記，計(jì)算aL=minL(x)+L(y)-F(xy)|xS,yCYT.由此得新的可行頂點(diǎn)標(biāo)記L(v)-aL,vWS,*L(v)+aL,vf、L(v),否則令 L=H,GL=GH,重新給出

8、 GL 的一個(gè)匹配 M,轉(zhuǎn)向.取 yCNL(ST,若 y 是 M 的飽和點(diǎn)，轉(zhuǎn)向.否則，轉(zhuǎn)向.設(shè) xyM,則令 S=SUx,T=TUy,轉(zhuǎn)向.在 GL 中的 u-y 路是 M-增廣路，記為 P,并令 M=MP,轉(zhuǎn)向.利用可行點(diǎn)標(biāo)記求最佳匹配算法的 MATLAB 程序代碼如下：n=4;A=455122464 2335 021;for(i=1:n)L(i,1)=0;L(i,2)=0;endfor(i=1:n)for(j=1:n)if(L(i,1)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;endfor(i=1:js

9、s)L(S(i),1)=L(S(i),1)-al;end%調(diào)整可行點(diǎn)標(biāo)記for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end%調(diào)整可行點(diǎn)標(biāo)記for(i=1:n)for(j=1:n)%生成子圖 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;breakel

10、se%NL(S)wTfor(j=1:jsn)pd=1;%MyNL(S)Tfor(k=1:jst)if(T(k)=NlS(j)pd=0;break;end;endif(pd)jj=j;break;end;endpd=0;%判斷 y 是否為 M 的飽和點(diǎn)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-增廣路，調(diào)整匹配 Mfor(k=1:jst)M(S(k),T(k)=1;M(S(k+1),T(k)=0;endif(js