匈牙利算法MATLAB程序

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《匈牙利算法MATLAB程序》，欢迎阅读！

%%用匈牙利法解指派问题

%%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;

本文来源：https://www.dywdw.cn/969b830ea6e9856a561252d380eb6294dd88229f.html