《匈牙利算法的matlab程序代码》由会员分享，可在线阅读，更多相关《匈牙利算法的matlab程序代码（1页珍藏版）》请在金锄头文库上搜索。
1、匈牙利算法的MATLAB 程序代码如下（算例）：m=5;n=5;A=0 1 1 0 01 1 0 1 10 1 1 0 00 1 1 0 00 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 %求初始匹配Mif(M(i,j)break;end;end %获得仅含一条边的初始匹配Mwhile(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:
2、n)if(M(i,j)pd=0;end;endif(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)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 (即xkyjM), 给以标号j 和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j); %yj 不是M的饱和点
3、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 中出现的边去掉else M(P(i,1),P(i,2)=1;end;end %将增广路P 中没有在匹配M中出现的边加入到匹配M中break;end;end;endif(pd)break;end;end %假如X中所有有标号的点都已去掉了标记*, 算法终止M %显示最大匹配M, 程序结束
