匈牙利算法matlab源程序及实例(适合各种矩阵).txt
- 文档编号:18635317
- 上传时间:2023-08-23
- 格式:TXT
- 页数:4
- 大小:5.83KB
匈牙利算法matlab源程序及实例(适合各种矩阵).txt
《匈牙利算法matlab源程序及实例(适合各种矩阵).txt》由会员分享,可在线阅读,更多相关《匈牙利算法matlab源程序及实例(适合各种矩阵).txt(4页珍藏版)》请在冰点文库上搜索。
function[Matching,Cost]=Edmonds(a)
Matching=zeros(size(a));
num_y=sum(~isinf(a),1);
num_x=sum(~isinf(a),2);
x_con=find(num_x~=0);
y_con=find(num_y~=0);
P_size=max(length(x_con),length(y_con));
P_cond=zeros(P_size);
P_cond(1:
length(x_con),1:
length(y_con))=a(x_con,y_con);
ifisempty(P_cond)
Cost=0;
return
end
Edge=P_cond;
Edge(P_cond~=Inf)=0;
cnum=min_line_cover(Edge);
Pmax=max(max(P_cond(P_cond~=Inf)));
P_size=length(P_cond)+cnum;
P_cond=ones(P_size)*Pmax;
P_cond(1:
length(x_con),1:
length(y_con))=a(x_con,y_con);
exit_flag=1;
stepnum=1;
whileexit_flag
switchstepnum
case1
[P_cond,stepnum]=step1(P_cond);
case2
[r_cov,c_cov,M,stepnum]=step2(P_cond);
case3
[c_cov,stepnum]=step3(M,P_size);
case4
[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(P_cond,r_cov,c_cov,M);
case5
[M,r_cov,c_cov,stepnum]=step5(M,Z_r,Z_c,r_cov,c_cov);
case6
[P_cond,stepnum]=step6(P_cond,r_cov,c_cov);
case7
exit_flag=0;
end
end
Matching(x_con,y_con)=M(1:
length(x_con),1:
length(y_con));
Cost=sum(sum(a(Matching==1)));
function[P_cond,stepnum]=step1(P_cond)
P_size=length(P_cond);
forii=1:
P_size
rmin=min(P_cond(ii,:
));
P_cond(ii,:
)=P_cond(ii,:
)-rmin;
end
stepnum=2;
function[r_cov,c_cov,M,stepnum]=step2(P_cond)
P_size=length(P_cond);
r_cov=zeros(P_size,1);
c_cov=zeros(P_size,1);
M=zeros(P_size);
forii=1:
P_size
forjj=1:
P_size
ifP_cond(ii,jj)==0&&r_cov(ii)==0&&c_cov(jj)==0
M(ii,jj)=1;
r_cov(ii)=1;
c_cov(jj)=1;
end
end
end
r_cov=zeros(P_size,1);%Avectorthatshowsifarowiscovered
c_cov=zeros(P_size,1);%Avectorthatshowsifacolumniscovered
stepnum=3;
function[c_cov,stepnum]=step3(M,P_size)
c_cov=sum(M,1);
ifsum(c_cov)==P_size
stepnum=7;
else
stepnum=4;
end
function[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(P_cond,r_cov,c_cov,M)
P_size=length(P_cond);
zflag=1;
whilezflag
row=0;col=0;exit_flag=1;
ii=1;jj=1;
whileexit_flag
ifP_cond(ii,jj)==0&&r_cov(ii)==0&&c_cov(jj)==0
row=ii;
col=jj;
exit_flag=0;
end
jj=jj+1;
ifjj>P_size;jj=1;ii=ii+1;end
ifii>P_size;exit_flag=0;end
end
ifrow==0
stepnum=6;
zflag=0;
Z_r=0;
Z_c=0;
else
M(row,col)=2;
ifsum(find(M(row,:
)==1))~=0
r_cov(row)=1;
zcol=find(M(row,:
)==1);
c_cov(zcol)=0;
else
stepnum=5;
zflag=0;
Z_r=row;
Z_c=col;
end
end
end
function[M,r_cov,c_cov,stepnum]=step5(M,Z_r,Z_c,r_cov,c_cov)
zflag=1;
ii=1;
whilezflag
rindex=find(M(:
Z_c(ii))==1);
ifrindex>0
ii=ii+1;
Z_r(ii,1)=rindex;
Z_c(ii,1)=Z_c(ii-1);
else
zflag=0;
end
ifzflag==1;
cindex=find(M(Z_r(ii),:
)==2);
ii=ii+1;
Z_r(ii,1)=Z_r(ii-1);
Z_c(ii,1)=cindex;
end
end
forii=1:
length(Z_r)
ifM(Z_r(ii),Z_c(ii))==1
M(Z_r(ii),Z_c(ii))=0;
else
M(Z_r(ii),Z_c(ii))=1;
end
end
r_cov=r_cov.*0;
c_cov=c_cov.*0;
M(M==2)=0;
stepnum=3;
function[P_cond,stepnum]=step6(P_cond,r_cov,c_cov)
a=find(r_cov==0);
b=find(c_cov==0);
minval=min(min(P_cond(a,b)));
P_cond(find(r_cov==1),:
)=P_cond(find(r_cov==1),:
)+minval;
P_cond(:
find(c_cov==0))=P_cond(:
find(c_cov==0))-minval;
stepnum=4;
functioncnum=min_line_cover(Edge)
[r_cov,c_cov,M,stepnum]=step2(Edge);
[c_cov,stepnum]=step3(M,length(Edge));
[M,r_cov,c_cov,Z_r,Z_c,stepnum]=step4(Edge,r_cov,c_cov,M);
cnum=length(Edge)-sum(r_cov)-sum(c_cov);
��a=[0.94000.97000.86000.97000.96800.94800.96800.9800
0.86000.93000.92000.93000.96800.96800.98800.9600
0.90000.93000.94000.95000.90800.94800.96800.9600
0.94000.93000.94000.95000.96800.90800.98800.9200
0.86000.89000.92000.95000.98800.94800.96800.9200
0.92000.93000.92000.95000.90800.94800.98800.9200
0.94000.97000.90000.93000.96800.94800.96801.0000
0.92000.97000.92000.93000.98800.98800.94800.9600
0.94000.97000.90000.97000.96800.94800.94800.9600
0.92000.95000.92000.97000.94800.94800.94800.9800
];
��[z,ans]=Edmonds(a)
������
z=
00100000
10000000
00001000
00000100
01000000
00000001
00000000
00010000
00000000
00000010
ans=
7.2240
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 匈牙利 算法 matlab 源程序 实例 适合 各种 矩阵