匈牙利算法的matlab程序

queshangxintou

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

1. function [result,msum]=sbppp(cost,m)
   
2. if nargin==1
   
3.     dd=cost;
   
4. else
   
5.     dd=max(max(cost))-cost;
   
6. end
   
7. [nop,nop]=size(cost);msum=0;
   
8. for i=1:nop
   
9.     dd(i,:)=dd(i,:)-min(dd(i,:));
   
10. end
    
11. for j=1:nop
    
12.     dd(:,j)=dd(:,j)-min(dd(:,j));
    
13. end
    
14. backup=dd;
    
15. for z=1:nop
    
16.     bh=nop;bl=nop;result=[];
    
17.     for k=1:nop
    
18.         for i=1:nop
    
19.             h=find(dd(i,:)==0);
    
20.             if length(h)~=0&length(h)<bh
    
21.                 bh=length(h);
    
22.                 ch=i;
    
23.             end
    
24.         end
    
25.         L=find(dd(ch,:)==0);
    
26.         for j=1:length(L)
    
27.             l=find(dd(:,L(j))==0);
    
28.             if length(l)<bl
    
29.                 bl=length(l);
    
30.                 cl=L(j);
    
31.             end
    
32.         end
    
33.         result(1,k)=ch;result(2,k)=cl;
    
34.         dd(ch,:)=1;dd(:,cl)=1;
    
35.         bl=nop;bh=nop;
    
36.         if length(find(dd==0))==0
    
37.             break
    
38.         end
    
39.     end
    
40.     if length(result(1,:))==nop
    
41.         break
    
42.     end
    
43.     dd=backup;DD=dd;d=zeros(nop);
    
44.     for i=1:length(result(1,:))
    
45.         d(result(1,i),result(2,i))=1;
    
46.     end
    
47.     D=~(d+dd);
    
48.     p=[];q=[];k=1;zx=inf;
    
49.     for i=1:nop
    
50.         if sum(d(i,:))==0
    
51.             p(k)=i;
    
52.             k=k+1;
    
53.         end
    
54.     end
    
55.     for j=1:length(p)
    
56.         q=find(D(p(j),:)==1);
    
57.         for e=1:length(q)
    
58.             pp=find(d(:,q(e))==1);
    
59.             if pp~=0
    
60.                 p(k)=pp;
    
61.                 k=k+1;
    
62.             end
    
63.          end
    
64.      end
    
65.      for l=1:length(p)
    
66.          q=find(D(p(l),:)==1);
    
67.          for u=1:length(q)
    
68.              DD(:,q(u))=inf;
    
69.          end
    
70.      end
    
71.      for l=1:length(p)
    
72.          if min(DD(p(l),:))<zx
    
73.                  zx=min(DD(p(l),:));
    
74.          end
    
75.      end
    
76.      for l=1:length(p)
    
77.          q=find(D(p(l),:)==1);
    
78.          for u=1:length(q)
    
79.              dd(:,q(u))=dd(:,q(u))+zx;
    
80.          end
    
81.      end
    
82.      for l=1:length(p)
    
83.          dd(p(l),:)=dd(p(l),:)-zx;
    
84.      end
    
85.      backup=dd;
    
86. end
    
87.   for i=1:length(result(1,:))
    
88.      msum=msum+cost(result(1,i),result(2,i));
    
89. end

复制代码

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

gospel125

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

gospel125

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

eight

原帖由 gospel125 于 2007-4-29 13:27 发表

                               
登录/注册后可看大图

我想知道怎么去实现这个程序，我在matlab中输入它，可出现错误：??? function [result,msum]=sbppp(cost,m)
    |
Error: Function definitions are not permitted at the prompt or in scripts.
还有，能不 ...

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

gospel125

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

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

gospel125

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

gospel125

运行到42行时，我觉得后面的没有必要了嘛。如果直接给出一个可以完美匹配的矩阵的话，前面的代码就能直接得出一个完美匹配了。谁能告诉我后面的有什么用？给我一个具体矩阵让我试试啊？