Ford-Fulkerson 方法——最大流問(wèn)題

最大流&&最小費(fèi)用最大流&&最大二分匹配

中文是2017年8月的筆記，英文是2018.11月的筆記

英文筆記來(lái)自于MIT公開課的筆記，教材為Introduction to Algorithm(Third Edition)，根據(jù)四位作者姓名首字母大寫常稱作CLRS，以下是一些資源：

最大流問(wèn)題

  • 比喻：有一個(gè)自來(lái)水管道運(yùn)輸系統(tǒng)，起點(diǎn)是 s，終點(diǎn)是 t，途中經(jīng)過(guò)的管道都有一個(gè)最大的容量，可以想象每條管道不能被水流“撐爆”。求從 s 到 t 的最大水流量是多少？

  • 應(yīng)用：網(wǎng)絡(luò)最大流問(wèn)題是網(wǎng)絡(luò)的另一個(gè)基本問(wèn)題。許多系統(tǒng)包含了流量問(wèn)題。例如交通系統(tǒng)有車流量，金融系統(tǒng)有現(xiàn)金流，控制系統(tǒng)有信息流等。許多流問(wèn)題主要是確定這類系統(tǒng)網(wǎng)絡(luò)所能承受的最大流量以及如何達(dá)到這個(gè)最大流量。

  • 流網(wǎng)絡(luò)（Flow Networks）：指的是一個(gè)有向圖 G = (V, E)，其中每條邊 (u, v) ∈ E 均有一非負(fù)容量 c(u, v) ≥ 0。如果 (u, v) ? E 則可以規(guī)定 c(u, v) = 0。流網(wǎng)絡(luò)中有兩個(gè)特殊的頂點(diǎn)：源點(diǎn) s （source）和匯點(diǎn) t（sink）。為方便起見(jiàn)，假定每個(gè)頂點(diǎn)均處于從源點(diǎn)到匯點(diǎn)的某條路徑上，就是說(shuō)，對(duì)每個(gè)頂點(diǎn) v ∈ E，存在一條路徑 s --> v --> t。

  • 容量限制(Capacity constraint)：對(duì)于所有的結(jié)點(diǎn) u, v ∈ V，要求 0 ≤ f(u, v) ≤ c(u, v)

  • 流量限制/流量守恒(Flow conservation)：對(duì)于所有的結(jié)點(diǎn) u ∈ V - {s, t}，要求 Σf(v, u) = Σf(u, v)

    We call this property "flow conservation", and it is equivalent to Kirchhoff's current law when the material is electrical current.

    Flow in equals flow out.

  • 當(dāng)(u, v) ? E時(shí)，從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 之間沒(méi)有流，因此f(u, v) = 0。我們稱非負(fù)數(shù)值f(u, v)為從結(jié)點(diǎn) u 到結(jié)點(diǎn) v 的流，定義如下： |f| = Σf(s, v) - Σf(v, s)，也就是說(shuō)，流 f 的值是從源結(jié)點(diǎn)流出的總流量減去流入源結(jié)點(diǎn)的總流量。（有點(diǎn)類似電路中的基爾霍夫定律）

    Here, the |*|notation denotes flow value, not absolute value or cardinality.

具有多個(gè)源結(jié)點(diǎn)和多個(gè)匯點(diǎn)的網(wǎng)絡(luò)

  • 一個(gè)最大流問(wèn)題可能會(huì)包含幾個(gè)源結(jié)點(diǎn)和幾個(gè)匯點(diǎn)，比如{s1, s2, ..., sm} 以及 {t1, t2, ..., tm}，而不僅僅只有一個(gè)源結(jié)點(diǎn)和匯點(diǎn)，其解決方法并不比普通的最大流問(wèn)題難。
  • 加入一個(gè)超級(jí)源結(jié)點(diǎn) s，并對(duì)于多個(gè)源結(jié)點(diǎn)，加入有向邊 (s, si) 和容量 c(s, si) = ∞，同時(shí)創(chuàng)建一個(gè)超級(jí)匯點(diǎn) t，并對(duì)于多個(gè)匯點(diǎn)，加入有向邊 (ti, t) 和容量 c(ti, t) = ∞。
  • 這樣單源結(jié)點(diǎn)能夠給原來(lái)的多個(gè)源結(jié)點(diǎn) si 提供所需要的流量，而單匯點(diǎn) t 則可以消費(fèi)原來(lái)所有匯點(diǎn) ti 所消費(fèi)的流量。

Ford-Fulkerson 方法

We call it a “method” rather than an “algorithm” because it encompasses
several implementations with differing running times.

  • 幾個(gè)重要的概念

    • 殘留網(wǎng)絡(luò)(residual capacity)：容量網(wǎng)絡(luò) - 流量網(wǎng)絡(luò) = 殘留網(wǎng)絡(luò)

      • 具體說(shuō)來(lái)，就是假定一個(gè)網(wǎng)絡(luò) G =（V，E），其源點(diǎn) s，匯點(diǎn) t。設(shè) f 為 G 中的一個(gè)流，對(duì)應(yīng)頂點(diǎn) u 到頂點(diǎn) v 的流。在不超過(guò) C（u，v）的條件下（C 代表邊容量），從 u 到 v 之間可以壓入的額外網(wǎng)絡(luò)流量，就是邊（u，v）的殘余容量（residual capacity）。

      • 殘余網(wǎng)絡(luò) Gf 還可能包含 G 中不存在的邊，算法對(duì)流量進(jìn)行操作的目的是增加總流量，為此，算法可能對(duì)特定邊上的流量進(jìn)行縮減。為了表示對(duì)一個(gè)正流量 f(u ,v) 的縮減，我們將邊 (u, v) 加入到 Gf中，并將其殘余容量設(shè)置為 cf(v, u) = f(u ,v)。也就是說(shuō)，一條邊所能允許的反向流量最多能將其正向流量抵消。

      • 殘存網(wǎng)絡(luò)中的這些反向邊允許算法將已經(jīng)發(fā)送出來(lái)的流量發(fā)送回去。而將流量從同一邊發(fā)送回去等同于縮減該邊的流量，這種操作在很多算法中都是必需的。

    • 增廣路徑(augmenting path): 這是一條不超過(guò)各邊容量的從 s 到 t 的簡(jiǎn)單路徑，向這個(gè)路徑注入流量，可以增加整個(gè)網(wǎng)絡(luò)的流量。我們稱在一條增廣路徑上能夠?yàn)槊織l邊增加的流量的最大值為路徑的殘余容量，cf(p) = min{cf(u,v) : (u,v)∈路徑p}

    • 割：用來(lái)證明 “當(dāng)殘留網(wǎng)絡(luò)中找不到增廣路徑時(shí)，即找到最大流”，最大流最小切割定理，具體證明略。

  • 算法過(guò)程：

    • 開始，對(duì)于所有結(jié)點(diǎn) u, v ∈ V， f(u, v) = 0，給出的初始流值為0。

    • 在每一次迭代中，將 G 的流值增加，方法就是在殘留網(wǎng)絡(luò)　Gf 中尋找一條增廣路徑（一般用 BFS 算法遍歷殘留網(wǎng)絡(luò)中各個(gè)結(jié)點(diǎn)，以此尋找增廣路徑），然后在增廣路徑中的每條邊都增加等量的流值，這個(gè)流值的大小就是增廣路徑上的最大殘余流量。

    • 雖然 Ford-Fulkerson 方法每次迭代都增加流值，但是對(duì)于某條特定邊來(lái)說(shuō)，其流量可能增加，也可能減小，這是必要的，詳情見(jiàn)下文的“反向邊”。

    • 重復(fù)這一過(guò)程，直到殘余網(wǎng)絡(luò)中不再存在增廣路徑為止。最大流最小切割定理將說(shuō)明在算法終結(jié)時(shí)，該算法獲得一個(gè)最大流。

    • 偽代碼：

      FORD-FULKERSON（G，t，s）

1 for each edge(u,v) 屬于 E（G）

2     do f[u,v]=0

3          f[v,u]=0

4 while there exists a path p from s to t in the residual network Gf // 根據(jù)最大流最小切割定理，當(dāng)不再有增廣路徑時(shí)，流 f 就是最大流

5       do cf(p)=min{cf(u,v):(u,v)is in p}  // cf(p)為該路徑的殘余容量

6        for each edge (u,v) in p

7              do f[u,v]=f[u,v]+cf(p)  //為該路徑中的每條邊中注入剛才找到到的殘余容量

8                    f[v,u]=-f[u,v]   //反向邊注入反向流量

    • 反向邊是什么？

      轉(zhuǎn)自（已失效-_-）：http://nano9th.wordpress.com.cn/2009/02/17/%E7%BD%91%E7%BB%9C%E6%B5%81%E5%9F%BA%E7%A1%80%E7%AF%87-edmond-karp%E7%AE%97%E6%B3%95/

      • 假設(shè)沒(méi)有上面?zhèn)未a中最后一步的操作，那么對(duì)于如下的流網(wǎng)絡(luò)：

        image.png

      • 我們第一次找到了 1-2-3-4 這條增廣路，這條路上的最小邊剩余流量顯然是 1。于是我們修改后得到了下面這個(gè)殘留網(wǎng)絡(luò)：

        image.png

      • 這時(shí)候 (1,2) 和 (3,4) 邊上的流量都等于容量了，我們?cè)僖舱也坏狡渌脑鰪V路了，當(dāng)前的流量是 1。但這個(gè)答案明顯不是最大流，因?yàn)槲覀兛梢酝瑫r(shí)走 1-2-4 和 1-3-4，這樣可以得到流量為 2 的流。

      • 這是貪婪算法行不通的一個(gè)例子（摘自《算法與數(shù)據(jù)結(jié)構(gòu) C++語(yǔ)言描述》第四版，但翻譯很差勁，推薦讀原版）

      • 而這個(gè)算法神奇的利用了一個(gè)叫做反向邊的概念來(lái)解決這個(gè)問(wèn)題。即每條邊 (i,j) 都有一條反向邊 (j,i)，反向邊也同樣有它的容量。那么我們剛剛的算法問(wèn)題在哪里呢？問(wèn)題就在于我們沒(méi)有給程序一個(gè)后悔的機(jī)會(huì)，應(yīng)該有一個(gè)不走 (2-3-4) 而改走 (2-4) 的機(jī)制。

      • 我們來(lái)看剛才的例子，在找到 1-2-3-4 這條增廣路之后，把容量修改成如下:

        image.png

      • 這時(shí)再找增廣路的時(shí)候，就會(huì)找到 1-3-2-4 這條可增廣量，即 delta 值為 1 的可增廣路。將這條路增廣之后，得到了最大流 2。

        image.png

      • 解釋：

        事實(shí)上，當(dāng)我們第二次的增廣路走 3-2 這條反向邊的時(shí)候，就相當(dāng)于把 2-3 這條正向邊已經(jīng)是用了的流量給” 退” 了回去，不走 2-3 這條路，而改走從 2 點(diǎn)出發(fā)的其他的路也就是 2-4。（有人問(wèn)如果這里沒(méi)有 2-4 怎么辦，這時(shí)假如沒(méi)有 2-4 這條路的話，最終這條增廣路也不會(huì)存在，因?yàn)樗静荒茏叩絽R點(diǎn)）同時(shí)本來(lái)在 3-4 上的流量由 1-3-4 這條路來(lái)” 接管”。而最終 2-3 這條路正向流量 1，反向流量 1，等于沒(méi)有流量。

      • 這就是這個(gè)算法的精華部分，利用反向邊，使程序有了一個(gè)后悔和改正的機(jī)會(huì)。

        The intuition behind this definition（反向邊） follows the definition of the residual network.
        We increase the flow on (u, v) by f'(u, v) but decrease it by f'(u, v) because pushing flow on the reverse edge in the residual network signifies decreasing the flow in the original network.

        Pushing flow on the reverse edge in the residual network is also known as cancellation.

      • 關(guān)于反向邊的討論——Modeling problems with antiparallel edges

        • Our original assumption: if an edge (v1, v2) ∈ E, then (v2, v1) ? E.

        • What if we violate this assumption? Thus, we have (v2, v1) ∈ E. We call the two edges (v1, v2) and (v2, v1) antiparallel.

        • How to solve this problem? We could convert a graph with antiparallel edges into a graph wihout antiparallel edges:

          • Split (v1, v2) by adding a new vertex v' and replacing edge (v1, v2) with the pair of edge (v1, v') and (v', v2).
          • Set the capacity of both new edges to the capacity of the original edge.
          • Thus, the resulting network satisfies the property that if an edge is in the network, the reverse is not.

        • 總之，antiparallel是允許存在的，引入一個(gè)新節(jié)點(diǎn)即可把帶antiparallel的圖轉(zhuǎn)換為不帶antiparallel的圖

最大流-最小割定理

最大流-最小割定理用來(lái)證明Ford-Fulkson方法的確達(dá)到了最大流

Cuts of flow networks

  • The Ford-Fulkerson method repeatedly augments the flow along augmenting paths until it has found a maximum flow.

    How do we know that when the algorithm terminates, we have actually found a maximum flow?

    The max-flow min-cut theorem, which we shall prove shortly, tells us that a flow is maximum if and only if its residual network contains no augmenting path.

    To prove this theorem, though, we must first explore the notion of a cut of a flow network.

  • You can overview cut theory in my preview note of minimum spanning tree.

  • Definition:

    • If f is a flow, then the net flow f(S, T) across the cut (S, T) is defined to be

      f(S, T) = Σu∈SΣv∈T f(u, v) - Σu∈SΣv∈T f(v, u)

    • The capacity of the cut (S, T) is

      c(S, T) = Σu∈SΣv∈T c(u, v)

    • A minimum cut of a network is a cut whose capacity is minimum over all cuts of the network.

    • Let f be a flow in a flow network G with source s and sink t, and let (S, T) be any cut of G. Then the net flow across (S, T) is

      f(S, T) = |f|

    • The value of any flow f in a flow network G is bounded from above by the capacity of any cut of G

  • Theorem 26.6 (Max-flow min-cut theorem)
    If f is a flow in a flow network G(V, E) with source s and sink t, then the
    following conditions are equivalent:

    1. f is a maximum flow in G.
    2. The residual network Gf contains no augmenting paths.
    3. |f| = c(S, T) for some cut (S, T) of G.

算法的效率及其優(yōu)化—— Edmonds-Karp 算法

  • 如果使用廣度優(yōu)先搜索（BFS）來(lái)尋找增廣路徑，那么可以改善 FORD-FULKERSON 算法的效率，也就是說(shuō)，每次選擇的增廣路徑是一條從 s 到 t 的最短路徑，其中每條邊的權(quán)重為單位距離（即根據(jù)邊的數(shù)量來(lái)計(jì)算最短路徑），我們稱如此實(shí)現(xiàn)的 FORD-FULKERSON 方法為 Edmonds-Karp 算法。其運(yùn)行時(shí)間為 O(VE^2)。

  • 注意 E-K 算法適用于改善 F-F 算法的效率，邊的權(quán)重僅僅還是容量限制，而下文的“最小費(fèi)用最大流”中的每條邊的權(quán)重有兩個(gè)值：（容量限制，單位流量損耗）。

最大流實(shí)例

  • 對(duì)于如下拓?fù)鋱D，給出從S1到S6允許的流的方向和帶寬限制：

    • 求出S1到S6最大可能帶寬（提示Ford-Fulkerson算法）。

    • 畫出流的流向及帶寬分配，使達(dá)到最大可能的帶寬。

    image.png

  • 根據(jù)算法，最大流的值為23（定值），而下圖是一種可能的流量走向：

    image.png

  • 源碼：https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow/maxflow.py

  • 在尋找增廣路徑時(shí)用到了 BFS 算法，以后有時(shí)間再寫寫 BFS、DFS 的文章，注意用到了 Python 中的標(biāo)準(zhǔn)庫(kù)：deque，這是雙端隊(duì)列。

CLRS Exercies

本節(jié)摘錄了一些算法導(dǎo)論上的對(duì)應(yīng)習(xí)題

26.1-5

  • State the maximum-flow problem as a linear-programming problem.

  • Solution:

    max ∑f(s, v) - ∑f(v,s)

    s.t. 0 ≤ f(u, v) ≤ c(u, v)

    ? ∑f(v, u) - ∑f(u, v) = 0

26.1-6

  • Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately both the professor's house and the school are on corners, but beyond that he is not sure if it is going to be possible to send both of his children to the same school. The professor has a map of his town. Show how to formulate the problem of determining whether both his children can go to the same school as a maximum-flow problem.

  • Solution:

    Create a vertex for each corner, and if there is a street between corners u and v, create directed edges (u,v) and (v,u).

    Set the capacity of each edge to 1. Let the source be corner on which the professor's house sits, and let the sink be the corner on which the school is located.

    We wish to find a flow of value 22 that also has the property that f(u,v) is an integer for all vertices u and v.

    Such a flow represents two edge-disjoint paths from the house to the school.

26.1-7

  • Suppose that, in addition to edge capacities, a flow network has vertex capacities. That is each vertex vv has a limit l(v) on how much flow can pass though vv. Show how to transform a flow network G=(V,E) with vertex capacities into an equivalent flow network G′=(V′,E′) without vertex capacities, such that a maximum flow in G′ has the same value as a maximum flow in G. How many vertices and edges does G′ have?

  • Solution:

    We will construct G′ by splitting each vertex v of G into two vertices v1, v2, joined by an edge of capacity l(v). All incoming edges of vv are now incoming edges to v1. All outgoing edges from vv are now outgoing edges from v2.

    More formally, construct G′=(V′,E′) with capacity function c′ as follows. For every v∈V, create two vertices v1, v2 in V′. Add an edge (v1,v2) in E′ with c′(v1,v2)=l(v). For every edge (u,v)∈E, create an edge (u2,v1) in E′ with capacity c′(u2,v1)=c(u,v). Make s1 and t2 as the new source and target vertices in G′. Clearly, |V′|=2|V| and |E′|=|E|+|V|.

    I draw a picture to vividly illustrate the idea.

    image.png

最小費(fèi)用最大流

  • 最小費(fèi)用最大流問(wèn)題是經(jīng)濟(jì)學(xué)和管理學(xué)中的一類典型問(wèn)題。在一個(gè)網(wǎng)絡(luò)中每段路徑都有 “容量” 和 “費(fèi)用” 兩個(gè)限制的條件下，此類問(wèn)題的研究試圖尋找出：流量從 A 到 B，如何選擇路徑、分配經(jīng)過(guò)路徑的流量，可以在流量最大的前提下，達(dá)到所用的費(fèi)用最小的要求。如 n 輛卡車要運(yùn)送物品，從 A 地到 B 地。由于每條路段都有不同的路費(fèi)要繳納，每條路能容納的車的數(shù)量有限制，最小費(fèi)用最大流問(wèn)題指如何分配卡車的出發(fā)路徑可以達(dá)到費(fèi)用最低，物品又能全部送到。

  • 注意：最后得到的流必須是最大流，最大流可能有多種情況，目標(biāo)是找出最小費(fèi)用的那種情況。

  • 解決最小費(fèi)用最大流問(wèn)題，一般有兩條途徑。

    • 一條途徑是先用最大流算法算出最大流，然后根據(jù)邊費(fèi)用，檢查是否有可能在流量平衡的前提下通過(guò)調(diào)整邊流量，使總費(fèi)用得以減少？只要有這個(gè)可能，就進(jìn)行這樣的調(diào)整。調(diào)整后，得到一個(gè)新的最大流。然后，在這個(gè)新流的基礎(chǔ)上繼續(xù)檢查，調(diào)整。這樣迭代下去，直至無(wú)調(diào)整可能，便得到最小費(fèi)用最大流。這一思路的特點(diǎn)是保持問(wèn)題的可行性（始終保持最大流），向最優(yōu)推進(jìn)。

    • 另一條解決途徑和前面介紹的最大流算法思路相類似，一般首先給出零流作為初始流。這個(gè)流的費(fèi)用為零，當(dāng)然是最小費(fèi)用的。然后尋找一條源點(diǎn)至匯點(diǎn)的增流鏈，但要求這條增流鏈必須是所有增流鏈中費(fèi)用最小的一條。如果能找出增流鏈，則在增流鏈上增流，得出新流。將這個(gè)流做為初始流看待，繼續(xù)尋找增流鏈增流。這樣迭代下去，直至找不出增流鏈，這時(shí)的流即為最小費(fèi)用最大流。這一算法思路的特點(diǎn)是保持解的最優(yōu)性（每次得到的新流都是費(fèi)用最小的流），而逐漸向可行解靠近（直至最大流時(shí)才是一個(gè)可行解）。

  • 第二種辦法與前文的 Ford-fulkerson 方法很像，所以選擇它更方便，如何找到費(fèi)用最小的增鏈流呢？可以用最短路徑算法，這里是單源最短路徑，所以選擇 Dijkstra 算法找出最短路徑即可，關(guān)于 Dijkstra 的介紹見(jiàn)：http://www.itdecent.cn/p/8ba71199a65f，里面有 Python 實(shí)現(xiàn)的程序。

最小費(fèi)用最大流實(shí)例

  • 對(duì)于如下拓?fù)鋱D，給出從S1到S6允許的流的方向和帶寬限制，鏈路按帶寬收費(fèi)，以括號(hào)形式表示為（帶寬容量，單位帶寬費(fèi)用）：

    • 求出S1到S6最小費(fèi)用下最大可能帶寬，得出最小費(fèi)用值，并標(biāo)出選路狀況。

    • 寫出對(duì)給出任意拓?fù)鋱D的通用算法描述。

      image.png

  • 源碼：https://github.com/edisonleolhl/DataStructure-Algorithm/blob/master/Graph/MaxFlow/mincostmaxflow.py

  • 運(yùn)行截圖：

    image.png

  • 注意增廣路徑是回溯的，比如第一條增廣路徑，終點(diǎn)為5，path[5]=4，所以它的前驅(qū)是4，path[4]=2，所以4的前驅(qū)是2，2的前驅(qū)是1，1的前驅(qū)是0，所以這條路徑是 0-1-2-4-5，也就是 s1-s2-s3-s5-s6。

  • 注意在尋找增廣路徑時(shí)用到了 Dijkstra 算法，至于為什么用 heapq （最小堆的實(shí)現(xiàn)），因?yàn)樗看?pop 出來(lái)的都是最小的項(xiàng)目，根據(jù) Dijkstra ，每次要從未訪問(wèn)點(diǎn)中找到最小距離的頂點(diǎn)，這樣就可以巧妙實(shí)現(xiàn)。

  • 流量分布情況：

    image.png

最大二分匹配

本節(jié)部分內(nèi)容轉(zhuǎn)自：二分圖的最大匹配、完美匹配和匈牙利算法
、圖的匹配問(wèn)題與最大流問(wèn)題 (五)—— 計(jì)算二分圖的最大匹配

  • 最大匹配定義：給定一個(gè)無(wú)向圖 G = (V, E)，一個(gè)匹配是指：E 的某個(gè)子集 M , 對(duì)于所有的結(jié)點(diǎn) v ∈ V，子集 M 中最多有一條邊與 v 相連，如果子集 M 中的某條邊與 v 相連，那么稱 v 由 M 匹配；否則 v 就是沒(méi)有匹配的。最大匹配是指：對(duì)于所有任意匹配 M'，有 |M| ≥ |M'| 的匹配 M 。

  • 二分圖定義：設(shè) G=(V,E) 是一個(gè)無(wú)向圖，如果頂點(diǎn) V 可分割為兩個(gè)互不相交的子集 (A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn) i 和 j 分別屬于這兩個(gè)不同的頂點(diǎn)集 (i in A,j in B)，則稱圖 G 為一個(gè)二分圖。

  • 完美匹配：如果一個(gè)圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個(gè)點(diǎn)都已經(jīng)匹配，添加一條新的匹配邊一定會(huì)與已有的匹配邊沖突）。但并非每個(gè)圖都存在完美匹配。

  • 應(yīng)用：把機(jī)器集合 L 與任務(wù)集合 R 相匹配， E 中有邊 (u, v) 就說(shuō)明一臺(tái)特定的機(jī)器 u ∈ L 能夠完成一項(xiàng)特定的任務(wù) v ∈ R，最大二分匹配就是讓盡可能多的機(jī)器運(yùn)行起來(lái)，因?yàn)橐慌_(tái)機(jī)器只能同時(shí)做一個(gè)任務(wù)，一個(gè)任務(wù)也只能同時(shí)被一個(gè)機(jī)器完成，所以這里也可理解為讓盡可能多的任務(wù)被完成。

  • 用下圖說(shuō)明，圖 1 是二分圖，為了直觀，一般畫成 2 那樣，3、4 中紅色邊即為匹配，4 是最大匹配，同時(shí)也是完美匹配（所有頂點(diǎn)都是匹配點(diǎn)），圖 5 展示了男孩和女孩暗戀關(guān)系，有連線就說(shuō)明這一對(duì)能成，求最大匹配就是求能成多少對(duì)

    image.png
    image.png
    image.png
    image.png
    image.png

Ford-Fulkson方法解決最大二分匹配

給定如下的二分圖（忽略顏色）：

image.png

把已有的邊設(shè)為單向邊（方向 L -> R），且各邊容量設(shè)為 ∞ ；增加源結(jié)點(diǎn) s 與匯點(diǎn) t，將 s 與集合 L 中各個(gè)結(jié)點(diǎn)之間構(gòu)造單向邊，且各邊容量設(shè)為 1；同樣的，將集合 R 中各個(gè)結(jié)點(diǎn)與 t 之間構(gòu)造單向邊，且各邊容量設(shè)為 1。這時(shí)得到一個(gè)流網(wǎng)絡(luò) G'，如下：

image.png

這時(shí)，最大匹配數(shù)值就等于流網(wǎng)絡(luò) G' 中最大流的值。

匈牙利算法解決二分匹配

推薦文章：趣寫算法系列之 -- 匈牙利算法

關(guān)鍵就是騰挪，迭代地騰挪

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容