分配问题匈牙利算法的Matlab实现

function [x,fVal]=Hungary(C)
% 输出参数：
% x--Decision Varables, n*n矩阵
% fval--Objective function Value
% 输入参数:
% C--效益矩阵

c=C; %将效益矩阵暂存入c,以下的操作将针对c进行
[iMatrixRow,iMatrixCol]=size(c);

%求约化矩阵：将效益矩阵的每行每列各减去其最小值
c=c-repmat(min(c,[],2),1,iMatrixCol);
c=c-repmat(min(c,[],1),iMatrixRow,1);

%进行试分配，求出初始分配方案
while 1
%对所有零元素均已画⊙(inf)或画×(-inf)
c=CircleOrCross(c);

%划线，决定覆盖所有零元素的最少直线数
iIndepentZeroNum=find(c==inf);
if length(iIndepentZeroNum)==iMatrixRow
break;
else
[Row,Col]=line(c);
end

%查找没有被直线段覆盖的元素中的最小元素，并存入fMininumVlaue中
fMininumVlaue=inf;
for i=1:iMatrixRow
for j=1:iMatrixCol
if Row(i)~=1 && Col(j)~=1 && c(i,j)fMininumVlaue=c(i,j);
end
end
end
%修改约化矩阵中的相关数据
for i=1:iMatrixRow
for j=1:iMatrixCol
if c(i,j)==inf||c(i,j)==-inf
c(i,j)=0;
end
if Row(i)~=1 && Col(j)~=1
c(i,j)=c(i,j)-fMininumVlaue;
end
if Row(i)==1 && Col(j)==1
c(i,j)=c(i,j)+fMininumVlaue;
end
end
end
end

%返回分配方案及目标函数值
fVal=0;
for i=1:iMatrixRow
for j=1:iMatrixCol
if c(i,j)==inf
x(i,j)=1;
fVal=fVal+C(i,j);
else
x(i,j)=0;
end
end
end