5.4 動(dòng)態(tài)規(guī)劃：尋找最短路徑的有效方法

????編輯距離是動(dòng)態(tài)規(guī)劃很好的應(yīng)用，用O(n^2)的時(shí)間復(fù)雜度解決了指數(shù)難度的問題。

主干網(wǎng)的建設(shè)

????因?yàn)楣饫w上下水平移動(dòng)，可有兩結(jié)論：

????1）當(dāng)直線在所有點(diǎn)上方，向下平移時(shí)，N個(gè)點(diǎn)到直線的距離之和是越來越小

????2）當(dāng)直線在所有點(diǎn)下方，向下平移時(shí)，N個(gè)點(diǎn)到直線的距離之和是越來越大

? ? 而當(dāng)直線上方點(diǎn)的個(gè)數(shù)小于下方點(diǎn)的個(gè)數(shù)時(shí)，直線繼續(xù)下移導(dǎo)致其上方點(diǎn)到其距離之和的增加小于其下方點(diǎn)到其距離之和的減少，因此當(dāng)直線上下點(diǎn)的數(shù)量一致（N/2）時(shí)，直線繼續(xù)下移導(dǎo)致上方點(diǎn)距離的增加和下方點(diǎn)距離的減少相互抵消，此時(shí)的一段區(qū)間都可以放置光纖。

????當(dāng)然，這是在N為偶數(shù)的情況下。若N為奇數(shù)，使所有點(diǎn)向垂直坐標(biāo)系投影后，取中間的那一點(diǎn)，穿過這一點(diǎn)的直線即為所求。

? ? 總結(jié)：動(dòng)態(tài)規(guī)劃的問題很多都很巧妙，著名的Dijkstra算法也是其中之一，詳情可見這個(gè)B站視頻：11-3: Dijkstra 算法 尋找有權(quán)圖中最短路

5.5 最大流：解決交通問題的方法

????如圖，求從S到T的最大流量，可以將S和T置于兩個(gè)不同組中，組間進(jìn)行切割，L1～L4是不同的切割方式，其中L2是所有切割方式中的最小切割（Minimum S-T cut），也是整個(gè)網(wǎng)絡(luò)S到T的最大流（Maximum flow）：8+3+4+9=24。

????從任意初始流量分布開始，如果系統(tǒng)中S到T還未到達(dá)最小割（或最大流），可以證明能夠不斷找到一條從 S -> T 的流量可以增加的增廣路徑（Augmenting Path）

????可以看出，在最小割L2上的邊的流量都已經(jīng)飽和了，因此該有向連通圖的流量不可能再增加了。該算法即為Ford-Fulkerson Algorithm，見偽代碼（或系列視頻：13-1: 網(wǎng)絡(luò)流問題基礎(chǔ) Network Flow Problems）：

????對(duì)于有權(quán)圖G=(V,E)，如果(u,v)屬于E，它的權(quán)重為capacity(u,v)，表示該邊容量。需要另一個(gè)數(shù)組flow(u,v)，表示每條邊已分配的流量（初始化為0）。此外還需要一個(gè)臨時(shí)數(shù)組remaining(u,v)，表示每條邊還剩余可分配的流量。由remaining這個(gè)數(shù)組和節(jié)點(diǎn)的集合構(gòu)成一個(gè)剩余流量圖Gr。如果u,v之間沒有剩余流量了，則(u,v)這條原屬于圖G的邊，就不在Gr中。

????福特-富爾克森（Ford-Fulkerson）算法的優(yōu)點(diǎn)是，當(dāng)網(wǎng)絡(luò)中各邊容量相近時(shí)，收斂快。但當(dāng)存在邊容量相差好幾個(gè)數(shù)量級(jí)時(shí)，收斂慢。基于此，改進(jìn)算法埃德蒙茲-卡普（Edmonds-Karp）算法可以解決，因?yàn)槠鋾r(shí)間復(fù)雜度與各邊容量無關(guān)。

5.6 最大配對(duì)-流量問題的擴(kuò)展

????在二分圖的配對(duì)應(yīng)用中，往往我們需要達(dá)到最大配對(duì)，比如婚戀配對(duì)最多或者網(wǎng)約車司機(jī)和乘客配對(duì)最大，這樣可以利益最大化：

????可以使用前面所說的最大流-最小割來解決該問題，只要認(rèn)為添加源點(diǎn)S和終點(diǎn)T即可，邊的最大容量和最小容量都是1，那么有幾對(duì)能匹配，最大流量就是幾：

????此外，《算法導(dǎo)論》中，還有介紹針對(duì)二分圖配對(duì)時(shí)增廣路徑的“交替路徑”方法。