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的邊，則問題轉化成點數相同的問題。