xylmat.txt

真正可以用的匈牙利算法 我校赛的时候用过 很不错 不过写的不够简洁

%%用匈牙利法解指派问题
%%C是效益矩阵
function [y,fval,flag]=Hungary(C)
[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

AssignMatrix=zeros(m,n);         
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
for i=1:m
    for j=1:n
        if tempC(i,j)==inf
            AssignMatrix(i,j)=1;
        end
    end
end
% y=AssignMatrix;
for i=1:m
    for j=1:m
        if AssignMatrix(i,j)==1
            y(i,1)=i;
            y(i,2)=j;
            break;
        end
    end
end
col=zeros(1,m);
row=zeros(1,m);
for i=1:m
    col=sum(AssignMatrix(i,:));
    row=sum(AssignMatrix(:,i));
end
if col==ones(1,m)&row==ones(1,m)
    flag=1;
else
    flag=0;
end
temp=C.*AssignMatrix;
fval=sum(temp(:));

 

%% 对处理过的每行每列都有零元素的矩阵C进行试指派
function y=TryAssign(C)
[m,n]=size(C);
while IsInMatrix(0,C)==1
    flag=0;
    for i=1:m       
        if ZeroNumber(C(i,:))==1
            temp=C(i,:);
            ZeroRowPos=find(temp==0);
            C(i,ZeroRowPos)=inf;   
            temp=C(:,ZeroRowPos);
            ZeroColPos=find(temp==0);
            for j=ZeroColPos
                C(j,ZeroRowPos)=-inf;  
            end
            flag=flag+1;
        end
    end
    for i=1:n       
        if ZeroNumber(C(:,i))==1
            temp=C(:,i);
            ZeroColPos=find(temp==0);
            C(ZeroColPos,i)=inf;     
            temp=C(ZeroColPos,:);
            ZeroRowPos=find(temp==0);
            for j=ZeroRowPos
                C(ZeroColPos,j)=-inf;
            end
            flag=flag+1;
        end
    end
    if flag==0        
        temp=inf;
        for i=1:m     
            if (ZeroNumber(C(i,:))<temp) & (ZeroNumber(C(i,:))>0)
                temp=ZeroNumber(C(i,:));
                ZeroRow=i;
            end
        end
        temp1=find(C(ZeroRow,:)==0);
        temp2=inf;
        for i=temp1     
            if (ZeroNumber(C(:,i))<temp2) & (ZeroNumber(C(:,i))>0)
                temp2=ZeroNumber(C(:,i));
                ZeroCol=i;
            end
        end
        C(ZeroRow,ZeroCol)=inf;
        temp=find(C(ZeroRow,:)==0);
        for i=temp      
            C(ZeroRow,i)=-inf;
        end
        temp=find(C(:,ZeroCol)==0);
        for i=temp
            C(i,ZeroCol)=-inf;
        end
    end
end
y=C;

 

%% 判断矩阵A中是否含有元素a
%% 若有，返回1，否则返回0
function y=IsInMatrix(a,A);
[m,n]=size(A);
y=0;
for i=1:m
    for j=1:n
        if A(i,j)==a
            y=1;
            break;
        end
    end
    if j<n
        break;
    end
end

 

%% 用最少的直线覆盖所有零元素
function [y,Row,Col]=ZeroCover(C,Row,Col,Cur)
[m,n]=size(C);
temp=C(Cur,:);      
flag=0;
Cur=[];
for i=1:m
    if temp(i)==-inf & Col(i)~=0      
        Col(i)=0;
        Cur=[Cur,i];
        flag=1;
    end
end
if flag==0                            
    y=0;
else                                 
    for i=Cur
        temp=C(:,i);
        for i=1:m
            if temp(i)==inf & Row(i)==0   
                Row(i)=1;
                y=i;
                flag=0;
                [y,Row,Col]=ZeroCover(C,Row,Col,y);
                break;
            end
        end
        if flag==1       
            y=0;
        end
    end
end

 

%%计算向量A中的零元素的个数
function y=ZeroNumber(A)
y=0;
for i=1:length(A)
    if A(i)==0
        y=y+1;
    end
end