最大網路流 Max (Network) Flow

Presentation on theme: "最大網路流 Max (Network) Flow"— Presentation transcript:

1 最大網路流 Max (Network) Flow
北一女中 資訊選手培訓營 最大網路流 Max (Network) Flow Nan

2 什麼是最大網路流問題？ A 10 C 5 6 4 5 S 7 D 6 T 6 8 15 8 B 3 E F 10 給你一張有向圖，有起點和終點，邊有權重，代表「容量限制」。 要請你找出從起點究竟能有多少「流」到終點。 (可以把那些邊都想成水管，這個流就變成水流。)

3 兩個要遵守的原則 流量限制原則(Capacity Law) 流過任何邊的流都不可以超過上限
流量守恆原則(Conservation Law) 一個點流入的流量恆等於流出的流量

4 剩餘網路的概念 當水流流過去了一條邊，我們就產生一條相對應容量的反向邊在圖上，並把原邊減去那個容量。 A C B E F D 5 7 4 3
8 6 S T 15 1 10 A C B E F D 5/10 7 5 4 3 8 6 S T 5/5 15 5/6 10

5 Max-Flow的一種解法 從起點(source)開始，找到一條路徑到達終點(target) 將這條路徑流滿(找到路徑上剩下最少容量的邊)
建出剩餘網路 對剩餘網路，重複1~4的動作，直到沒路可走

6 A 10 C 5 6 4 5 S 7 D 6 T 6 8 15 8 B 3 E F 10

7 找到一條路徑 A C B E F D 5/10 7 5 4 3 8 6 S T 5/5 15 5/6 10 建出剩餘網路 A C B E F D 5 7 4 3 8 6 S T 15 1 10

8 找到一條路徑 A C B E F D 5 7 4 3/3 8 6 S T 3/15 1 3/10 3/8 建出剩餘網路 A C B E F D 5 7 4 3 8 6 S T 1 12

9 A C B E F D 5 7 4 3 8 6 S T 1 12 找不到可到終點的路徑了！ 最大流是5+3=8

10 剛剛找路徑的動作 最初這個演算法被發明的時候，用的是DFS 後來Edmonds&Karp改良他，用BFS去跑
其名為Ford-Fulkerson’s algorithm 複雜度是O(Ef)，f為max-flow的值 f可能很大，不能說是多項是時間的演算法 後來Edmonds&Karp改良他，用BFS去跑 每次都跑“最短路徑”(用邊的數量做距離) Edmonds-Karp’s Algorithm: 複雜度O(VE)

11 為什麼要有反向邊？ 因為有些時候一開始流的那條可能占掉了別條的空間，所以要讓他有機會反向取消。 例子？自己想想看XD 提示：某一條流先流在某個點有兩條路可以走，但它選了擋住了另一條的空間的那條。

12 關於剩餘網路 其實不需要新增一張圖，如果有流過i->j，流過的量是f，那麼只需要 map[i][j]去扣掉f
map[j][i]去加上f 就等於是加上反向邊&扣掉正向邊的容量 =新的剩餘網路。

13 #include <string.h> // 為了用memset這個function所以要include這個
#define INF // 用int的最大值做為無限大 int map[N][N]; // 假設我們有N個點。這裡存的是邊(i->j)的容量上限(有向邊) // 沒有邊時的容量就是0 int queue[N]; // 用來跑BFS用的 int qTail; // =queue裡現在的元素個數 int last[N]; // 紀錄BFS來的上一個點是誰 int min[N]; // 紀錄BFS來到這個點的一路上邊容量最小為多少 int visited[N]; // 跑BFS紀錄那些點被跑過了 int max_flow; // 我們要的解 int edmonds_karp(int src, int tar){ // 整張圖的起點編號src，終點tar max_flow = 0; int new_flow = 0; // 下去一直找path，找到找不到(回傳值為零)為止。 do{ new_flow = find_path_bfs(src, tar); max_flow += new_flow; }while ( new_flow != 0 ); return max_flow; }

14 int find_path_bfs(int src, int tar){ // 找路用，回傳值為這次找到的大小，起點編號src，終點tar
// 用memset歸零 memset(visited, 0, sizeof(visited)); // src本身要做BFS前的初始化 min[src] = INF; last[src] = -1; visited[src] = 1; // 將src放入queue queue[0] = src; qTail = 1; int qHead, i; for ( qHead = 0 ; qHead < qTail ; qHead++ ){ if ( queue[qHead] == tar ) break; // 找到了 int cur = queue[qHead]; // 目前處理的點的編號 for ( i = 0 ; i < N ; i++ ){ if ( visited[i] == 0 && map[cur][i] != 0 ){ queue[qTail++] = i; min[i] = (min[cur] < map[cur][i]) ? min[cur] : map[cur][i]; last[i] = cur; visited[i] = 1; } // 沒路了就會qHead == qTail，直接結束 if ( qHead == qTail ) return 0; build_residual_network(tar); return min[tar]; void build_residual_network(int tar){ // 建剩餘網路 int flow = min[tar]; // 此次流的flow量 int cur = tar; while ( last[cur] != -1 ){ map[ last[cur] ][ cur ] -= flow; // 正向邊減少 map[ cur ][ last[cur] ] += flow; // 反向邊增加 cur = last[cur]; }

15 Max-Flow應用：二分圖匹配 (Bipartite Matching)
給你Group A和Group B，他們之間要配對，但只能一對一，請你找出配對總數最多的配對法。 Ex: Group A=組員；Group B=工作 他們之間的配對=組員擅長的工作

16 二分圖：可以把圖分成兩群，所有的邊都在群間，也就是群內無邊。
1 A 2 B 3 C 4 D 5 E 6 7

17 轉換法：把所有邊變成單向、並加上一個起點跟終點，且所有邊容量為1
A B C D E 1 2 3 4 5 6 7 A B C D E 1 2 3 4 5 6 7 T S 去做max-flow，找出來的flow量就是最大配對數

18 看完影片你要知道的是 什麼是最大網路流問題 網路流兩個必須遵守的原則 剩餘網路的概念 Max-Flow演算法的操作流程(EK法)