KM算法

⑴ 匈牙利算法 和 KM算法

是的。KM是通过巧妙的方法把带权问题归结为不带权问题。

⑵ km算法求最小匹配如何处理权值矩阵

是啊，第一个顶点选取的确是任意的，这样中间过程就有比较多种了
不过如果该连通图中所有边的权值都不同，无论从哪个顶点开始最终生成树结果只有一个
即使最终的生成树的形态有多种，那个树的权值之和也是唯一的

⑶ 求KM算法模板pascal源代码 n3的复杂度

POJ2400（标准KM算法）
题目大意：有n个管理员需要雇佣n个工作人员。 每个管理员对每个工作人员的评价不同，评价值(score)从0-n-1，0代表评价最高，n-1代表评价最低，同样，每个工作人员对每个管理员也有不同 的评价，评价值也是从0-n-1，0代表评价值最高，n-1代表最低。问n个管理员怎样选择n个工作人员可以使的每个人的平均评价值最小。即总的评价值 /（2*n）最小。如果存在多种最佳方案，则按照字典序输出每一种情况。

代码：
program p2400;
const maxn=100;
var i,j,k,n,m,t,max,z:longint; ok:boolean; ans:real;
p,dist:array[1..15,1..15]of longint;
a,b,slake,link,emp:array[1..15]of longint;
ah,bh:array[1..15]of boolean;
function min(a,b:longint):longint;
begin
if a<b then exit(a); exit(b);
end;
function find(v:longint):boolean;
var i:longint;
begin
ah[v]:=true;
for i:=1 to n do
begin
if not(bh[i])and(dist[v,i]=a[v]+b[i]) then
begin
bh[i]:=true;
if(link[i]=0)or(find(link[i]))then
begin
link[i]:=v;
exit(true);
end;
end else
if dist[v,i]<a[v]+b[i] then slake[v]:=min(slake[v],a[v]+b[i]-dist[v,i]);
end;
exit(false);
end;
procere print;
var i:longint;
begin
inc(z);
writeln('Best Pairing ',z);
for i:=1 to n do
writeln('Supervisor ',i,' with Employee ',emp[i]);
end;
procere dfs(k:longint);
var i:longint;
begin
for i:=1 to n do
if ah[i] then
begin
inc(t,dist[k,i]);
if t>max then begin dec(t,dist[k,i]);exit; end;
ah[i]:=false; emp[k]:=i;
if k<>n then dfs(k+1)
else print;
ah[i]:=true; dec(t,dist[k,i]);
end;
end;
begin
assign(input,'p2400.in');reset(input);
assign(output,'p2400.out');rewrite(output);
readln(m);
for k:=1 to m do
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
fillchar(dist,sizeof(dist),0);
fillchar(link,sizeof(link),0);
read(n);
for i:=1 to n do
for j:=1 to n do
begin read(t); dist[i,t]:=j-1; end;
for i:=1 to n do
for j:=1 to n do
begin read(t); inc(dist[t,i],j-1); end;
for i:=1 to n do
for j:=1 to n do
begin
dist[i,j]:=maxn-dist[i,j];
if dist[i,j]>a[i] then a[i]:=dist[i,j];
end;
for i:=1 to n do
repeat
fillchar(ah,sizeof(ah),false);
fillchar(bh,sizeof(bh),false);
fillchar(slake,sizeof(slake),$3f);
ok:=find(i);
if not(ok) then
begin
t:=maxlongint;
for j:=1 to n do t:=min(t,slake[j]);
for j:=1 to n do
begin
if ah[j] then dec(a[j],t);
if bh[j] then inc(b[j],t);
end;
end;
until ok;
max:=0; ans:=0; t:=0; z:=0;
for i:=1 to n do
begin
max:=max+a[i];
max:=max+b[i];
end;
max:=maxn*n-max;
ans:=max/(n shl 1);
writeln('Data Set ',k,', Best average difference: ',ans:0:6);
fillchar(ah,sizeof(ah),true);
for i:=1 to n do
for j:=1 to n do
dist[i,j]:=maxn-dist[i,j];
dfs(1);
writeln;
end;
close(input);close(output);
end.

⑷ KM算法的介绍

KM算法求的是完备匹配下的最大权匹配： 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。

⑸ KM算法的注意

每一次找匹配时USED都是清0的，这是为了记录什么可以找，什么不可以找，说白了，这个模块就是一个递归的过程，USED的应用就是为了限制递归过程中的寻找范围，从而达到“不好则换，换则最好”，这里的最好是“新换”中最好的。
匈牙利算法解题是极为简单的，但是图论的难并不是难在解答，而是建图的过程，也难怪会有牛曰：用匈牙利算法，建图是痛苦的，最后是快乐的。当然，我们这些◎#！◎◎也只能搞搞NOIP了，一般不会太难，所以此算法，极为好用。
KM算法：
最大流的KM算法，又算的上算法世界中的一朵奇葩了。
解决最大流问题可以使用“网络流”，但较为繁琐，没有KM来得痛快，
下面是KM算法的核心模块：

functionfind(x:byte):boolean;vary:byte;beginfind:=false;vx[x]:=true;fory:=1tondoifnotvy[y]and(lx[x]+ly[y]=w[x,y])thenbeginvy[y]:=true;if(aim[y]=0)orfind(aim[y])thenbeginaim[y]:=x;find:=true;exit;end;end;end;
可以见出，该模块与匈牙利算法极为相似，差别便是:
if not vy[y] and (lx[x]+ly[y]=w[x,y])判断语句了，这里涉及到KM算法的思想，不再赘述，请自行“摆渡”之。
但是在源程序的调用过程更是烦杂： fork:=1tondorepeatfillchar(vx,sizeof(vx),0);fillchar(vy,sizeof(vy),0);iffind(k)thenbreak;////有机会d:=maxn;/////没有机会fori:=1tondo/////创造机会ifvx[i]thenforj:=1tondoifnotvy[j]theniflx[i]+ly[j]-w[i,j]<dthend:=lx[i]+ly[j]-w[i,j];fori:=1tondobeginifvx[i]thendec(lx[i],d);ifvy[i]theninc(ly[i],d);end;untilfalse;总结起来便是：有机会就上，没有机会创造机会也要上！

⑹ 求kM算法和匈牙利算法的程序代码

//二分图最佳匹配,kuhn munkras算法,邻接阵形式,复杂度O(m*m*n)
//返回最佳匹配值,传入二分图大小m,n和邻接阵mat,表示权值
//match1,match2返回一个最佳匹配,未匹配顶点match值为-1
//一定注意m<=n,否则循环无法终止
//最小权匹配可将权值取相反数
#include <string.h>
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)

int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}

⑺ 求KM算法的matlab实现 急

这个算法的函数matlab中本身就有，名称为kmeans，你可以试试很好用。

⑻ 急急急！！！寻匈牙利算法、KM算法的代码！

寻匈牙利算法:

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

匈牙利算法的MatLab实现 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

function [z,ans]=fenpei(marix)

%//////////////////////////////////////////////////
%输入效率矩阵 marix 为方阵;
%若效率矩阵中有 M,则用一充分大的数代替;
%输出z为最优解，ans为 最优分配矩阵；
%//////////////////////////////////////////////////
a=marix;
b=a;
%确定矩阵维数
s=length(a);
%确定矩阵行最小值，进行行减
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%确定矩阵列最小值，进行列减
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同
%index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以标记划线位，flag=0 表示未被划线，
%flag=1 表示有划线过，flag=2 表示为两直线交点
%ans用以记录 a 中“（0）”的位置
%循环后重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出“（0）”所在位置，并对“（0）”所在列划线，
%即设置flag,同时修改index,将结果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出“（0）”所在位置，并对“（0）”所在行划线，
%即设置flag,同时修改index,将结果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %对 while(sum(sum(index)))
%处理过程
%计数器：计算ans中1的个数，用num表示
num=sum(sum(ans));
% 判断是否可以终止，若可以则跳出循环
if(s==num)
break;
end
%否则，进行下一步处理
%确定未被划线的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被划线，即flag=0处减去m；线交点，即flag=2处加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %对while(num~=s)
%计算最优（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
运行实例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)

z =

127.8000

ans =

0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0

⑼ 求会km算法，且会使用matlab算出最优匹配的大神帮忙，最好懂编程的

KM算法：其实感觉它的最基本得思想就是逐渐接近最优匹配，每次向最有匹配迈出最小的一步，直到达到最优为止（到最后，sigma(lx[i]+ly[i])刚好等于最优匹配值）

算法开始，初始化LX[I]为等点I的最大的边的权值，LY[I]初始为0，在这个时候如果各个定点所对应得最大权值得边终点刚刚没有重合的话，显然，目前的匹配状况既是最优的。

算法进行的过程中不断的更新顶标（LX[I],LY[I]）的值来进行匹配。

每次寻找增广路径，找到的话继续寻找下一个点，找不到的话更改目前的顶标值，由于（sigma(lx[i]+ly[i])）是最优匹配的估计值，如果找不到当前节点的匹配的话，说明目前的最优匹配的估计值不能实现，需要调整，而KM算法的核心就是如何实现一个有效同时又正确的调整的方法。

以最小的调整逐渐靠近答案是必须的，其次就是需要知道要调整哪些顶标，首先，调整不能破坏目前的匹配状况（因为匹配是在寻找增广路径中实现的）

⑽ km算法中两方数目不等应当怎么改该算法 附：c++程序

将点比较少的那一部扩充，使得其点数与另一部相同，再将两部之间不相邻的点连上边权为0的边，则问题转化成点数相同的问题。