|
马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?我要加入
x
匈牙利算法的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 [result,msum]=sbppp(cost,m)
- if nargin==1
- dd=cost;
- else
- dd=max(max(cost))-cost;
- end
- [nop,nop]=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 编辑 ] |
评分
-
1
查看全部评分
-
|