km演算法c代碼實現

『壹』 km演算法中兩方數目不等應當怎麼改該演算法 附：c++程序

將點比較少的那一部擴充，使得其點數與另一部相同，再將兩部之間不相鄰的點連上邊權為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演算法的代碼！

尋匈牙利演算法:

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實現 急

這個演算法的函數matlab中本身就有，名稱為kmeans，你可以試試很好用。

『伍』 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 演算法，謝謝！

KM演算法是通過給每個頂點一個標號（叫做頂標）來把求最大權匹配的問題轉化為求完備匹配的問題的。設頂點Xi的頂標為A[ i ]，頂點Yj的頂標為B[ j ]，頂點Xi與Yj之間的邊權為w[i,j]。在演算法執行過程中的任一時刻，對於任一條邊(i,j)，A[ i ]+B[j]>=w[i,j]始終成立。KM演算法的正確性基於以下定理：
若由二分圖中所有滿足A[ i ]+B[j]=w[i,j]的邊(i,j)構成的子圖（稱做相等子圖）有完備匹配，那麼這個完備匹配就是二分圖的最大權匹配。
這個定理是顯然的。因為對於二分圖的任意一個匹配，如果它包含於相等子圖，那麼它的邊權和等於所有頂點的頂標和；如果它有的邊不包含於相等子圖，那麼它的邊權和小於所有頂點的頂標和。所以相等子圖的完備匹配一定是二分圖的最大權匹配。
初始時為了使A[ i ]+B[j]>=w[i,j]恆成立，令A[ i ]為所有與頂點Xi關聯的邊的最大權，B[j]=0。如果當前的相等子圖沒有完備匹配，就按下面的方法修改頂標以使擴大相等子圖，直到相等子圖具有完備匹配為止。
我們求當前相等子圖的完備匹配失敗了，是因為對於某個X頂點，我們找不到一條從它出發的交錯路。這時我們獲得了一棵交錯樹，它的葉子結點全部是X頂點。現在我們把交錯樹中X頂點的頂標全都減小某個值d，Y頂點的頂標全都增加同一個值d，那麼我們會發現：
1）兩端都在交錯樹中的邊(i,j)，A[ i ]+B[j]的值沒有變化。也就是說，它原來屬於相等子圖，現在仍屬於相等子圖。
2）兩端都不在交錯樹中的邊(i,j)，A[ i ]和B[j]都沒有變化。也就是說，它原來屬於（或不屬於）相等子圖，現在仍屬於（或不屬於）相等子圖。
3）X端不在交錯樹中，Y端在交錯樹中的邊(i,j)，它的A[ i ]+B[j]的值有所增大。它原來不屬於相等子圖，現在仍不屬於相等子圖。
4）X端在交錯樹中，Y端不在交錯樹中的邊(i,j)，它的A[ i ]+B[j]的值有所減小。也就說，它原來不屬於相等子圖，現在可能進入了相等子圖，因而使相等子圖得到了擴大。
現在的問題就是求d值了。為了使A[ i ]+B[j]>=w[i,j]始終成立，且至少有一條邊進入相等子圖，d應該等於：
Min{A[ i ]+B[j]-w[i,j] | Xi在交錯樹中，Yi不在交錯樹中}。
以上就是KM演算法的基本思路。但是樸素的實現方法，時間復雜度為O(n4)——需要找O(n)次增廣路，每次增廣最多需要修改O(n)次頂標，每次修改頂標時由於要枚舉邊來求d值，復雜度為O(n2)。實際上KM演算法的復雜度是可以做到O(n3)的。我們給每個Y頂點一個「鬆弛量」函數slack，每次開始找增廣路時初始化為無窮大。在尋找增廣路的過程中，檢查邊(i,j)時，如果它不在相等子圖中，則讓slack[j]變成原值與A[ i ]+B[j]-w[i,j]的較小值。這樣，在修改頂標時，取所有不在交錯樹中的Y頂點的slack值中的最小值作為d值即可。但還要注意一點：修改頂標後，要把所有的slack值都減去d。
Kuhn－Munkras演算法流程：
(1)初始化可行頂標的值
(2)用匈牙利演算法尋找完備匹配
(3)若未找到完備匹配則修改可行頂標的值
(4)重復(2)(3)直到找到相等子圖的完備匹配為止
pascal代碼:
Program Bamboobrook;
Const MaxN=1000;
Var Map:Array[0..MaxN,0..MaxN]of Longint;
X,Y:Array[1..MaxN]of Boolean;
Link,Lx,Ly:Array[0..MaxN]of Longint;
N,I,J:Longint;
Procere Readit;
Begin
Assign(Input,'km.in');Reset(Input);
Readln(N);
For I:=1 to N do
For J:=1 to N do
Read(Map[I,J]);
Close(Input);
End;
Procere Prepare;
Var I,J:Longint;
Begin
Fillchar(Lx,Sizeof(Lx),0);
Fillchar(Ly,Sizeof(Ly),0);
For I:=1 to N do
For J:=1 to N do
If(Map[I,J]>Lx[I])Then
Lx[I]:=Map[I,J];
End;
Function Find(K:Longint):Boolean;
Var I,Tmp:Longint;
Begin
X[K]:=True;
For I:=1 to N do
If(Not(Y[I]))And(Lx[K]+Ly[I]=Map[K,I])Then
Begin
Y[I]:=True;
Tmp:=Link[I];
Link[I]:=K;
If(Tmp=0)Or(Find(Tmp))Then
Exit(True);
Link[I]:=Tmp;
End;
Exit(False);
End;
Procere KM;
Var I,J,K,d:Longint;
Begin
For K:=1 to N do
Repeat
Fillchar(X,Sizeof(X),False);
Fillchar(Y,Sizeof(Y),False);
If(Find(K))Then
Break;
d:=Maxlongint;
For I:=1 to N do
If(X[I])Then
For J:=1 to N do
If(Not(Y[J]))Then
If(Lx[I]+Ly[J]-Map[I,J]<d)Then
d:=Lx[I]+Ly[J]-Map[I,J];
For I:=1 to N do
Begin
If(X[I])Then
Dec(Lx[I],d);
If(Y[I])Then
Inc(Ly[I],d);
End;
Until False;
End;
Procere Print;
Var Ans,I:Longint;
Begin
Assign(Output,'km.out');Rewrite(Output);
Ans:=0;
For I:=1 to N do
Inc(Ans,Map[Link[I],I]);
Close(Output);
End;
Begin
Readit;
Prepare;
Km;
Print;
End.

『捌』 求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.