• 大小: 4KB
    文件类型: .m
    金币: 1
    下载: 0 次
    发布日期: 2021-06-14
  • 语言: Matlab
  • 标签: 最大匹配  

资源简介

最大匹配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
            

评论

共有 条评论

相关资源