匈牙利算法的MATLAB代码.doc

function[z,ans]=fenpei(marix)%//////////////////////////////////////////////////%输入效率矩阵marix为方阵;%若效率矩阵中有M,则用一充分大的数代替;%输出z为最优解,ans为最优分配矩阵;%//////////////////////////////////////////////////a=marix;b=a;%确定矩阵维数s=length(a);%确定矩阵行最小值,进行行减ml=min(a');fori=1:sa(i,:)=a(i,:)-ml(i);end%确定矩阵列最小值,进行列减mr=min(a);forj=1:sa(:,j)=a(:,j)-mr(j);end%startworkingnum=0;while(num~=s)%终止条件是“(0)”的个数与矩阵的维数相同%index用以标记矩阵中的零元素,若a(i,j)=0,则index(i,j)=1,否则index(i,j)=0index=ones(s);index=a&index;index=~index;%flag用以标记划线位,flag=0表示未被划线,%flag=1表示有划线过,flag=2表示为两直线交点%ans用以记录a中“(0)”的位置%循环后重新初始化flag,ansflag=zeros(s);ans=zeros(s);%一次循环划线全过程,终止条件是所有的零元素均被直线覆盖,%即在flag>0位,index=0while(sum(sum(index)))%按行找出“(0)”所在位置,并对“(0)”所在列划线,%即设置flag,同时修改index,将结果填入ansfori=1:st=0;l=0;forj=1:sif(flag(i,j)==0&&index(i,j)==1)l=l+1;t=j;endendif(l==1)flag(:,t)=flag(:,t)+1;index(:,t)=0;ans(i,t)=1;endend%按列找出“(0)”所在位置,并对“(0)”所在行划线,%即设置flag,同时修改index,将结果填入ansforj=1:st=0;r=0;fori=1:sif(flag(i,j)==0&&index(i,j)==1)r=r+1;t=i;endendif(r==1)flag(t,:)=flag(t,:)+1;index(t,:)=0;ans(t,j)=1;endendend%对while(sum(sum(index)))%处理过程%计数器:计算ans中1的个数,用num表示num=sum(sum(ans));%判断是否可以终止,若可以则跳出循环if(s==num)break;end%否则,进行下一步处理%确定未被划线的最小元素,用m表示m=max(max(a));fori=1:sforj=1:sif(flag(i,j)==0)if(a(i,j)<m)m=a(i,j);endendendend%未被划线,即flag=0处减去m;线交点,即flag=2处加上mfori=1:sforj=1:sif(flag(i,j)==0)a(i,j)=a(i,j)-m;endif(flag(i,j)==2)a(i,j)=a(i,j)+m;endendendend%对while(num~=s)%计算