资源简介
最大匹配matlab算法程序,直接输入矩阵信息,输出最大匹配方案
代码片段和文件信息
function [sumwmatch]=maxmatch2004(A)
match=[];
[mn]=size(A);
if m A=[A;zeros(n-mn)];
elseif m>n
A=[Azeros(mm-n)];
end
w=A;
l=zeros(n2);
for i=1:n
for j=1:n
if l(i1) l(i1)=w(ij);
end
end
end
FLAG_AGL=zeros(nn);
FLAG_S=zeros(1n);
FLAG_T=zeros(1n);
FLAG_NGLS=zeros(1n);f=zeros(n2);
for i=1:n
for j=1:n
if l(i1)+l(j2)==w(ij)
FLAG_AGL(ij)=i;
end
end
end
M=zeros(n2);
for i=1:n
for j=1:n
if (FLAG_AGL(ij)==i)&(~M(j2))&(~M(i1))
M(i1)=i;
M(j2)=i;
end
end
end
FLAG3=1;
while FLAG3
FLAG3=0;
u=0;
for i=1:n
if ~M(i1)
u=i;
break;
end
end
if ~u
fprintf(1‘---------------------二部图的最大权匹配运行结果-----------------------\n‘);
fprintf(1‘\n\n求得最大权匹配M={‘);
sumw=0;
for i=1:n
for j=1:n
if M(j2)==i&A(ij)~=0
fprintf(1‘x%dy%d‘ij);
match(:size(match2)+1)=[i;j];
sumw=sumw+w(ij);
break;
end
end
end
fprintf(1‘}\n‘);
fprintf(1‘最大权W(M)=%g\n‘sumw);
return
else
FLAG_S=zeros(1n);
FLAG_T=zeros(1n);
FLAG_S(u)=1;f=zeros(n2);FLAG_NGLS=zeros(1n);
end
FLAG4=1;
while FLAG4
for i=1:n
if FLAG_S(i)
for j=1:n
if FLAG_AGL(ij)==i
FLAG_NGLS(j)=1;
end
end
end
end
FLAG_EQU=1;
for i=1:n
if FLAG_NGLS(i)~=FLAG_T(i)
FLAG_EQU=0;
break;
end
end
FLAG4=0;
al=inf;
if FLAG_EQU
for i=1:n
for j=1:n
if (FLAG_S(i))&(~FLAG_T(j))
temp=l(i1)+l(j2)-w(ij);
if al>temp
al=temp;
end
end
end
end
for i=1:n
if FLAG_S(i)
l(i1)=l(i1)-al;
end
end
for j=1:n
- 上一篇:线性矩阵不等式
- 下一篇:matlab矩阵运算
评论
共有 条评论