## 10.4 貪心法 考慮一個應用問題：假設需要在油庫 A 和加油站 B、C、D、E、F、G、H 之間修建輸 油管道，油庫和各加油站的位置如圖 10.6 所示，圖中的虛線表示可能的管道鋪設路線，虛 線旁標注的數值表示所需鋪設的管道的長度（千米）②。例如油庫 A 與加油站 B 之間需要鋪 設 35 千米的管道。  圖 10.6 油庫及加油站位置示意圖 顯然沒有必要在所有可能路線上鋪設管道，而只需要各加油站直接或間接與油庫連通即可。假設人手和資金比較緊張，工程只能分批分期進行，每期建設一條管道。我們該如何規 劃整個工程呢？ > ① 術語稱為引用傳遞，以區別于普通的值傳遞。參見第 6 章。 > ② 此處的長度數據不一定是兩點之間的直線距離，所以不要根據三角不等式（三角形中兩邊之和大于第三 邊）得出數據不合理的結論。 指導思想當然是又快又省錢。一種想法是盡可能快地使加油站投入使用，每一期工程都 使一個加油站能夠供油。那么，第一期必須在油庫 A 與某個加油站之間鋪設管道，問題是 選哪個加油站呢？顯然應該選擇 B，因為在從 A 可直接到達的 B、C、D、E 中，AB 是最短 的管道，可以在最短時間內建成，當然花費也是最少的。接下來考慮第二期工程時，可以選擇一個從 A 或者 B 可到達的加油站，注意此時所選加油站不必與油庫 A 直接相通，間接連 通也能保證供油。C、D、E、G 都是從 A 或 B 可通達的加油站，其中 C 是最近的，因此我 們選擇 C，并鋪設 B 和 C 之間的 15 千米管道。在工程的第三期，需要選擇一個能與 A、B 或 C 可到達的加油站，這次最短的是 C 和 D 之間的 5 千米管道，因此選擇 D 并鋪設 CD 管 道。到目前為止，工程進展如圖 10.7 所示，圖中實線段表示已經鋪設的管道，B、C、D 都 能供油了。  圖 10.7 第三期工程后的狀況 依此類推，在接下去的第四期到第七期工程中，可以分別鋪設 CG、GH、FH 和 FE 之間的管道。至此，所有加油站都通過輸油管道與油庫 A 連通了，如圖 10.8 所示。工程規劃 者一定很滿意，因為他們覺得自己在每一期建設中都選擇了當時情況下最短的線路，從而能 以最快時間完成那一期工程，使一個新加油站投入運營。當工程完工時，鋪設管道的總長度 是 150 千米。  圖 10.8 完工后的狀況 下面考慮另一種工程建設方案。工程規劃者并不追求各加油站盡快投入使用，而一心只想以最小的投資完成工程。這時的指導思想是，每一期工程都盡可能選擇當前所有線路中最 短的線路來鋪設管道，并確保最終能將油庫和所有加油站連通起來。 按照這個思路，首先應該選擇鋪設 CD 管道，因為這條管道的長度是 5 千米，是所有管 道線路中最短的。完成 CD 管道之后，剩余線路中最短的管道是 10 千米的 FH，因此選擇它 作為第二條鋪設的管道。依此類推，接下去應該分別鋪設 BC（15 千米）、GH（20 千米）和 CG（25 千米）等管道，至此工程現狀如圖 10.9 所示。  圖 10.9 鋪設五條最短管道之后的狀況 按照上述思路接下來應該鋪設當前最短的 CF 管道（30 千米），但由于 C 和 F 已經連入 了輸油管道系統，再鋪設 CF 管道屬于重復建設，因此我們放棄 CF 而選擇鋪設 AB 管道（35 千米）。最后一步鋪設 EF 管道（40 千米），至此油庫和所有加油站都連通了，如圖 10.10 所 示。  圖 10.10 完工后的狀況 讀者一定已經發現，第二種以省錢為指導思想的建設方案與第一種以盡快投入運營為指 導思想的建設方案所導致的輸油管道系統是一樣的，兩者都鋪設了總長度為 150 千米的管 道。問題是這兩種建設方案到底是不是最優的呢？會不會有一種管道總長度更小的方案呢？ 讀者不妨試試其他選擇，最終會發現任何其他將油庫和加油站連接在一起的方案都導致總長 度超過 150 千米的管道系統。所以，我們討論的兩種方案都導致了最優的（即總長度最小） 輸油管道系統。 不難看出，實際中的許多問題都可以利用上述方案來解決，如下水道系統、芯片設計、 交通網、通信網等等。這些問題可以抽象成圖論中的“最小支撐樹”問題，上面兩種解決方 案其實是解決最小支撐樹問題的兩個著名算法的應用。 第一種方案稱為 Prim 算法，其思想是從一個地點（如油庫）出發，一個接一個地將其 他地點（如加油站）連入系統，其中每一步都盡可能選擇最短連接路線。Prim 算法的偽代 碼如下： ``` Prim 算法 1\. 初始時所有地點標記為不可通達。 2\. 選擇一個特定地點，標記為可通達。 3\. 重復下列步驟，直至所有地點都被標記為可通達： 選擇距離最近的兩個地點，其中一個地點的標記是可通達，另一個地點的標記是不可通 達。然后將這兩個地點連接起來，并將原先不可通達的地點改標為可通達。 ``` 第二種策略稱為 Kruskal 算法，其思想是每一步將當前距離最近且尚未連通的兩個地點 連接起來。如果某一步的當前最小長度線路所涉及的兩個地點已經連通了，則放棄這個路線， 接著考慮其后線路。算法偽代碼如下： ``` Kruskal 算法 重復以下步驟，直至所有地點都直接或間接地連通： 將當前距離最近并且尚未連通的兩個地點連接起來。 ``` Prim 算法和 Kruskal 算法雖然是不同的解決方法，但他們都能產生最小支撐樹。這兩個 算法其實反映了一個共同的算法設計方法——貪心法。貪心法指的是這樣一種問題求解策 略：在求解過程的每一步都盡量作出在當前情況下局部最優的選擇，以期最終能得到全局最 優解。例如 Prim 算法在每一步都選擇當前與已連通部分最近的地點，Kruskal 算法在每一步 都盡可能選擇當前最短的線路，兩者的最終目標都是構造最小支撐樹。 貪心算法的一般模式是通過迭代（循環）來一步一步地進行貪心選擇，從而產生一個局 部最優解，并將問題簡化為更小的問題，最終的全局解由所有局部解組成。即： ``` 貪心算法模式 算法： 輸入：一個候選對象集合 輸出：由某些候選對象組成的全局解 重復以下步驟，直至得到全局解： 從候選對象中選擇當前最優者，并加入到局部解中 ``` 在迭代的每一步，貪心選擇可以依賴于此前的迭代步驟中已經作出的選擇，但不能依賴 于未來的選擇。打個比方，貪心選擇就像一個每次只計算一步棋的棋手，他總是選擇當前能 獲得最大利益的一步棋，而不考慮這步棋會不會在以后造成損失。顯然，一步棋的好壞不能 只取決于當前利益，而是要著眼全局。在貪心策略下，以后即使認識到前面某一步棋不佳， 也是不允許悔棋的。可見，貪心算法具有“只看眼前利益”和“落子無悔”的兩大特點。 當然，好的棋手是不會采用貪心策略來下棋的，他們會計算未來的很多步棋，然后選擇 全局最優的著法。這說明貪心策略只能對某些問題（如上述最小支撐樹問題）能產生全局最 優解，對另一些問題則不然。不過，貪心算法的優點是能夠較快地找出解法，產生的結果經 常也是接近全局最優解的；而一心追求全局最優解則有可能導致無法在合理的時間內達到目 標，就像棋手如果指望算無遺策，那就要花費大量時間來計算著法，這幾乎是不可能的。 最后順便提一下，在前面的輸油管道問題中，為了從油庫 A 向加油站 E 供油，采用貪 心算法設計出的方案是將 A 經 B、C、G、H、F 來與 E 連通，這條管線的總長度為 145 千 米。而假如直接在 A 和 E 之間修一條管道的話只需要 80 千米！可見，如果待解決的問題是 修建從油庫到每一個加油站的最短管道，前述兩個算法是不合適的。事實上，存在另一個采 用貪心法設計的著名算法——Dijkstra 最短路徑算法，可以很好地解決這個問題。