edmonds演算法

1. edmonds-karp演算法是如何求最大流的

Edmonds-Karp 演算法步驟

每次通過BFS，找到殘余網路上從源點到匯點的一條最短增廣路

在流網路上增加增廣路

修改殘余網路，殘余容量減去增廣路，並添加增廣路的反向弧

當無法BFS到增廣路時，演算法結束

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: ditch
LANG: C++

//對ford演算法的改進，變為多項試的。

/*
ID:cmykrgb1
PROG:ditch
LANG:C++
*/
#include<iostream>
#include<fstream>
#defineMAX201
usingnamespacestd;

classTadjl
{
public:
classTnode
{
public:
intr,v;
voidset(inttr,inttv)
{
r=tr;
v=tv;
}
};
intcnt;
Tnodelink[MAX];
};

classtQueue
{
public:
classlinklist
{
public:
linklist*next;
intvalue;
linklist()
{
next=0;
value=0;
}
};
linklist*first,*last;
intsize;
voidadd(intp)
{
if(size==0)
first=last=newlinklist;
else
last=last->next=newlinklist;
last->value=p;
size++;
}
intdel()
{
intrtn=first->value;
linklist*tfirst=first;
first=first->next;
deletetfirst;
size--;
returnrtn;
}
voidreset()
{
size=0;
first=last=0;
}
tQueue()
{
reset();
}
};

ifstreamfi("ditch.in");
ofstreamfo("ditch.out");

Tadjladjl[MAX];
intN,M,ans;

inlineintmin(inta,intb)
{
returna<b?a:b;
}

voidinit()
{
inti,a,b,v;
fi>>N>>M;
for(i=1;i<=N;i++)
{
fi>>a>>b>>v;
adjl[a].link[++adjl[a].cnt].set(b,v);
}
}


intedmonds(intstart,intend)
{
inti,j,k;
intfather[MAX],fp[MAX],max[MAX];
intMaxflow=0;
memset(father,0,sizeof(father));
max[start]=0x7FFFFFFF;
tQueue*Q=newtQueue;
Q->add(start);
while(Q->size)
{
i=Q->del();
for(k=1;k<=adjl[i].cnt;k++)
{
j=adjl[i].link[k].r;
if(!adjl[i].link[k].v||j==start)continue;
if(!father[j])
{
father[j]=i;
fp[j]=k;
max[j]=min(adjl[i].link[k].v,max[i]);
if(j==end)
{
Maxflow+=max[j];
while(father[j])
{
adjl[father[j]].link[fp[j]].v-=max[end];
adjl[j].link[++adjl[j].cnt].set(father[j],max[j]);
j=father[j];
}
memset(father,0,sizeof(father));
Q->reset();
Q->add(start);
break;
}
Q->add(j);
}
}
}
returnMaxflow;
}

voidprint()
{
fo<<ans<<endl;
fi.close();
fo.close();
}

intmain()
{
init();
ans=edmonds(1,M);
print();
return0;
}

2. Hungarain algorithm是什麼

Hungarian algorithm

匈牙利演算法
匈牙利演算法是由匈牙利數學家Edmonds於1965年提出，因而得名。匈牙利演算法是基於Hall定理中充分性證明的思想，它是部圖匹配最常見的演算法，該演算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的演算法。

3. 幫我解釋下網路流

必須知識：最短路徑問題
1.Dijkstra
適用於滿足所有權系數大於等於0（lij≥0）的網路最短路問題，能求出起點v1到所有其他點vj的最短距離；
樸素的Dijkstra演算法復雜度為O(N^2)，堆實現的Dijkstra復雜度為O(NlogN).

2.bellman-ford
適用於有負權系數，但無負迴路的有向或無向網路的最短路問題，能求出起點v1到所有其它點 vj的最短距離。bellman-ford演算法復雜度為O(V*E)。

3.Floyed
適用於有負權系數，可以求出圖上任意兩點之間的最短路徑。DP思想的演算法，時間復雜度為O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];

NO.1 s-t最大流
兩大類演算法
1.增廣路演算法
Ford-Fulkerson演算法: 殘留網路中尋找增加路徑
STEP0：置初始可行流。
STEP1：構造原網路的殘量網路，在殘量網路中找s－t有向路。如果沒有，演算法得到最大流結束。否則繼續下一步。
STEP2：依據殘量網路中的s－t有向路寫出對應到原網路中的s－t增廣路。對於增廣路中的前向弧，置s(e)＝u(e)- f(e)。對於反向弧，置s(e)＝f（e） STEP3：計算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：對於增廣路中的前向弧，令f(e)＝f(e)＋crement；對於其中的反向弧，令f(e)＝f(e)-crement，轉STEP1。
關鍵點:尋找可增廣路。決定了演算法復雜度。
實現：Edmonds-Karp 通過採用了廣度優先的搜索策略得以使其復雜度達到O(V*E^2)。

優化—> Dinic演算法(*)
Dinic演算法的思想是為了減少增廣次數，建立一個輔助網路L，L與原網路G具有相同的節點數，但邊上的容量有所不同，在L上進行增廣，將增廣後的流值回寫到原網路上，再建立當前網路的輔助網路，如此反復，達到最大流。分層的目的是降低尋找增廣路的代價。
演算法的時間復雜度為O(V^2*E)。其中m為弧的數目，是多項式演算法。鄰接表表示圖，空間復雜度為O(V+E)。

2.預流推進演算法
一般性的push-relabel演算法: 時間復雜度達到O(V^2*E)。(*)
relabel-to-front演算法->改進
最高標號預流推進:時間復雜度O(V^2*sqrt(E))

NO2. 最小費用最大流
求解最小費用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟1時選一條非飽和路時，應選代價和最小的路，即最短路。
步驟1. 選定一條總的單位費用最小的路，即要給定最小費用的初始可行流，而不是包含邊數最小的路。
步驟2. 不斷重復求最大流的步驟來進行，直到沒有飽和路存在為止。然後計算每個路的總費用。
和Edmonds-Karp標號演算法幾乎一樣，因為這兩種演算法都使用寬度優先搜索來來尋找增廣路徑，所以復雜度也相同，都是O(V*E^2)。

連續最短路演算法 + 線性規劃對偶性優化的原始對偶演算法(*)
傳說中，沒見過，據說復雜度是O(V^3)

NO3. 有上下屆的最大流和最小流（通過添加點來進行轉化）(*)

NO4. 相關圖論演算法
二分圖最大匹配： 加s和t構造最大流
專用演算法：hungary演算法 O(M*N)

二分圖最佳匹配： 加s和t構造最小費用最大流
專用演算法：KM演算法
樸素的實現方法,時間復雜度為O(n^4)
加上鬆弛函數O(n^3)

最小路徑覆蓋：
頂點數－二分圖的最大匹配

s-t最小邊割集：
最大流最小割定理：最小割等於最大流

普通最小邊割集：
Stoer-Wagner Minimum Cut O(n^3)

二分圖的最大獨立集：
N - 二分圖的最大匹配（POJ monthly）girls and boys
反證法證明
普通圖的最大獨立集是np問題。(*)

4. NP-hard的NP-hard

其中，NP是指非確定性多項式（non-deterministic polynomial，縮寫NP）。所謂的非確定性是指，可用一定數量的運算去解決多項式時間內可解決的問題。NP 問題通俗來說是其解的正確性能夠被「很容易檢查」的問題，這里「很容易檢查」指的是存在一個多項式檢查演算法。相應的，若NP中所有問題到某一個問題是圖靈可歸約的，則該問題為NP困難問題
例如，著名的推銷員旅行問題（Travel Saleman Problem or TSP）：假設一個推銷員需要從香港出發，經過廣州，北京，上海，…，等 n 個城市， 最後返回香港。 任意兩個城市之間都有飛機直達，但票價不等。假設公司只給報銷 C 元錢，問是否存在一個行程安排，使得他能遍歷所有城市，而且總的路費小於 C？
推銷員旅行問題顯然是 NP 的。因為如果你任意給出一個行程安排，可以很容易算出旅行總開銷。但是，要想知道一條總路費小於 C 的行程是否存在，在最壞情況下，必須檢查所有可能的旅行安排！ 這將是個天文數字。
旅行推銷員問題是數圖論中最著名的問題之一，即「已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路」。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效演算法時，每個問題都會有有效演算法。
迄今為止，這類問題中沒有一個找到有效演算法。傾向於接受NP完全問題（NP-Complet或NPC）和NP難題（NP-Hard或NPH）不存在有效演算法這一猜想，認為這類問題的大型實例不能用精確演算法求解，必須尋求這類問題的有效的近似演算法。
此類問題中，經典的還有 子集和問題； Hamilton迴路問題；最大團問題

5. 匈牙利演算法 matlab程序出現問題 運行時出現 Undefined function or variable 'a'.

調用 Edmonds 時，忘了個 實際參數 a（有值得）或數值了。
也可以 用默認參數值。
function [Matching,Cost] = Edmonds(a)
if nargin==0
a=.......;
end
Matching = zeros(size(a));
.........

6. 網路流之最大流，您只需判斷這個代碼是屬於哪一種最大流演算法即可。

Edmonds - Karp 演算法
最簡單的增廣路類演算法，每次用一個 BFS 尋找最短增廣路
while(1) 里前半部分的 for 循環就是 BFS 部分，隊列 que[] 輔助進行 BFS，找到的增廣路存在 pre[i] 中
if(!pre[sink])判斷是否存在可到達匯點的增廣路，不存在就跳出循環
後半部分 for 循環對找到的路徑進行增廣操作。

時間復雜度 O(VE^2)，行數雖少，但效率不是很高的演算法

最後說一句，這代碼風格太差了 = =，只考慮代碼長度完全不顧可讀性

參考資料是自己的 blog 呵呵

7. 最大流演算法中的Edmonds-Karp演算法為什麼用廣度優先搜索增廣路徑

我花了三個晚上，畫了無數的圖，試圖構造出一個深度遍歷之後復雜度會超過ve²，沒能成功

然後用了一下午的時間google，最後發現有個國外的論文，研究員通過遞歸方式構造了一個圖，(也就是教科書上那個傻傻的證明e|f|復雜度的五邊棱形圖，他把這個大棱形對角線那一條邊替換成一個小棱形，然後把小棱形的對角線又替換，迭代n次，每個外層大棱形四邊的流量，都是內層小棱形四邊流量的兩倍，也就是說，最裡面的小棱形對角線游戲是1，四邊流量是1，外面一層的棱形是2，再外面是4，8，16……)

作

8. 求匈牙利演算法的原理

對於一個點x和一個點i，如果x和i匹配，那麼就匹配；如果i已和j匹配，那麼就看j能否和別的點匹配，如果能就可以x和i匹配，匹配數+1。

9. 利用matlab計算多個坐標點，可以互相連接的最短距離

這個問題一般是TSP問題，該回答來自工中號一匹大懶蟲
旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。
TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
旅行推銷員問題是圖論中最著名的問題之一，即「已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路」。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效演算法時，每個問題都會有有效演算法。[1]
迄今為止，這類問題中沒有一個找到有效演算法。傾向於接受NP完全問題（NP-Complete或NPC）和NP難題（NP-Hard或NPH）不存在有效演算法這一猜想，認為這類問題的大型實例不能用精確演算法求解，必須尋求這類問題的有效的近似演算法。
此類問題中，經典的還有 子集和問題； Hamilton迴路問題；最大團問題。