hungary.m

现在我发现网站上对于匈牙利方法的matlab实现还是比较的少

%%用匈牙利法解指派问题
%%C是效益矩阵
function [y,fval,flag]=Hungary(C)%y返回的是最优值的行列号
[m,n]=size(C);
tempC=C;
%%%以下两个循环使每行每列都出现零元素
for i=1:m
    tempC(i,:)=tempC(i,:)-min(tempC(i,:));
end
for i=1:n
    tempC(:,i)=tempC(:,i)-min(tempC(:,i));
end       
tempC=TryAssign(tempC); %对每行每列都产生了零的矩阵进行试派              
OneNumber=0;%每行独立零的个数
for i=1:m                        
    for j=1:n
        if tempC(i,j)==inf
            OneNumber=OneNumber+1;
            break;
        end
    end
end
while OneNumber<m%如果独立的零可个数小于行数
    Row=zeros(m,1);     
    Col=ones(1,n);      
    Line=[];
    for i=1:m
        if IsInMatrix(inf,tempC(i,:))==0
            Line=[Line,i];
            Row(i)=1;
        end
    end
    for i=Line
        Cur=i;
        while Cur~=0
            [Cur,Row,Col]=ZeroCover(tempC,Row,Col,Cur);%用最少的直线覆盖所得零
        end
    end
    temp=inf;
    for i=1:m     
        for j=1:n
            if Row(i)==1&Col(j)==1&tempC(i,j)<temp
                temp=tempC(i,j);
            end
        end
    end
    for i=1:m
        for j=1:n
            if tempC(i,j)==inf|tempC(i,j)==-inf
                tempC(i,j)=0;
            end
        end
    end
    for i=1:m   
        if Row(i)==1
            tempC(i,:)=tempC(i,:)-temp;
        end
    end
    for j=1:n   
        if Col(j)==0
            tempC(:,j)=tempC(:,j)+temp;
        end
    end
    tempC=TryAssign(tempC);%进行试派
    OneNumber=0;%独立的零的个数
    for i=1:m                        
        for j=1:n
            if tempC(i,j)==inf
                OneNumber=OneNumber+1;
                break;
            end
        end
    end
end%while
AssignMatrix=zeros(m,n); %指派矩阵
for i=1:m
    for j=1:n
        if tempC(i,j)==inf
            AssignMatrix(i,j)=1;
        end
    end
end
 y=AssignMatrix;
temp=C.*AssignMatrix;
fval=sum(temp(:));