queshangxintou 发表于 2006-8-21 00:40

匈牙利算法的matlab程序

匈牙利算法的matlab程序
几点说明：
1.输入的变量是一个时，求最小值；反之，不论对m赋任何值，都求最大值。
2.msum表示求得的极值；（result（1，i）result（2，i））表示所选元素的坐标，i=1、2…n
3.cost是要输入的矩阵，必须是n阶的方阵。
4.矩阵的维数不要太大，建议在200阶以下。（一般100阶的要花10到20秒）
5.程序虽然可以运行，但是还有些地方在理论上没有依据。

function =sbppp(cost,m)
if nargin==1
    dd=cost;
else
    dd=max(max(cost))-cost;
end
=size(cost);msum=0;
for i=1:nop
    dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
    dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
    bh=nop;bl=nop;result=[];
    for k=1:nop
      for i=1:nop
            h=find(dd(i,:)==0);
            if length(h)~=0&length(h)<bh
                bh=length(h);
                ch=i;
            end
      end
      L=find(dd(ch,:)==0);
      for j=1:length(L)
            l=find(dd(:,L(j))==0);
            if length(l)<bl
                bl=length(l);
                cl=L(j);
            end
      end
      result(1,k)=ch;result(2,k)=cl;
      dd(ch,:)=1;dd(:,cl)=1;
      bl=nop;bh=nop;
      if length(find(dd==0))==0
            break
      end
    end
    if length(result(1,:))==nop
      break
    end
    dd=backup;DD=dd;d=zeros(nop);
    for i=1:length(result(1,:))
      d(result(1,i),result(2,i))=1;
    end
    D=~(d+dd);
    p=[];q=[];k=1;zx=inf;
    for i=1:nop
      if sum(d(i,:))==0
            p(k)=i;
            k=k+1;
      end
    end
    for j=1:length(p)
      q=find(D(p(j),:)==1);
      for e=1:length(q)
            pp=find(d(:,q(e))==1);
            if pp~=0
                p(k)=pp;
                k=k+1;
            end
         end
   end
   for l=1:length(p)
         q=find(D(p(l),:)==1);
         for u=1:length(q)
             DD(:,q(u))=inf;
         end
   end
   for l=1:length(p)
         if min(DD(p(l),:))<zx
               zx=min(DD(p(l),:));
         end
   end
   for l=1:length(p)
         q=find(D(p(l),:)==1);
         for u=1:length(q)
             dd(:,q(u))=dd(:,q(u))+zx;
         end
   end
   for l=1:length(p)
         dd(p(l),:)=dd(p(l),:)-zx;
   end
   backup=dd;
end
for i=1:length(result(1,:))
   msum=msum+cost(result(1,i),result(2,i));
end

[ 本帖最后由 suffer 于 2006-10-9 20:40 编辑 ]

gospel125 发表于 2007-4-29 13:27

你好

我想知道怎么去实现这个程序，我在matlab中输入它，可出现错误：??? function =sbppp(cost,m)
    |
Error: Function definitions are not permitted at the prompt or in scripts.
还有，能不能给你的程序中添加注释啊，这样看起来不是那么的费劲。

gospel125 发表于 2007-4-29 13:29

不好意思

对了，我的qq是3719487，可以的话加我吧。谢了先。

eight 发表于 2007-4-29 13:37

原帖由 gospel125 于 2007-4-29 13:27 发表 http://forum.vibunion.com/forum/images/common/back.gif
我想知道怎么去实现这个程序，我在matlab中输入它，可出现错误：??? function =sbppp(cost,m)
    |
Error: Function definitions are not permitted at the prompt or in scripts.
还有，能不 ...


请阅读matlab基础书，了解 m 文件和脚本文件的作用

gospel125 发表于 2007-4-29 21:25

你好

我知道了 ，是我装时出现问题了。现在是说程序中ch没有定义，可是在第19行 我已经是赋值了啊.能不能说说这是怎么回事？

[ 本帖最后由 eight 于 2007-4-29 21:28 编辑 ]

gospel125 发表于 2007-4-30 21:43

帮忙啊

我想知道，后面的从第46行开始后的那些代码有什么作用啊？我觉得如果给出一个可以完美匹配的矩阵的话，前面就可以完美匹配了，后天我调试的时候就直接跳过了。谢谢大家啊。

gospel125 发表于 2007-4-30 21:50

你好！

运行到42行时，我觉得后面的没有必要了嘛。如果直接给出一个可以完美匹配的矩阵的话，前面的代码就能直接得出一个完美匹配了。谁能告诉我后面的有什么用？给我一个具体矩阵让我试试啊？
页: [1]
查看完整版本: 匈牙利算法的matlab程序