## 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 最短路徑算法,可以很好地解決這個問題。
- 前言
- 第 1 章 計算與計算思維
- 1.1 什么是計算?
- 1.1.1 計算機與計算
- 1.1.2 計算機語言
- 1.1.3 算法
- 1.1.4 實現
- 1.2 什么是計算思維?
- 1.2.1 計算思維的基本原則
- 1.2.2 計算思維的具體例子
- 1.2.3 日常生活中的計算思維
- 1.2.4 計算思維對其他學科的影響
- 1.3 初識 Python
- 1.3.1 Python 簡介
- 1.3.2 第一個程序
- 1.3.3 程序的執行方式
- 1.3.4 Python 語言的基本成分
- 1.4 程序排錯
- 1.5 練習
- 第 2 章 用數據表示現實世界
- 2.1 數據和數據類型
- 2.1.1 數據是對現實的抽象
- 2.1.1 常量與變量
- 2.1.2 數據類型
- 2.1.3 Python 的動態類型*
- 2.2 數值類型
- 2.2.1 整數類型 int
- 2.2.2 長整數類型 long
- 2.2.3 浮點數類型 float
- 2.2.4 數學庫模塊 math
- 2.2.5 復數類型 complex*
- 2.3 字符串類型 str
- 2.3.1 字符串類型的字面值形式
- 2.3.2 字符串類型的操作
- 2.3.3 字符的機內表示
- 2.3.4 字符串類型與其他類型的轉換
- 2.3.5 字符串庫 string
- 2.4 布爾類型 bool
- 2.4.1 關系運算
- 2.4.2 邏輯運算
- 2.4.3 布爾代數運算定律*
- 2.4.4 Python 中真假的表示與計算*
- 2.5 列表和元組類型
- 2.5.1 列表類型 list
- 2.5.2 元組類型 tuple
- 2.6 數據的輸入和輸出
- 2.6.1 數據的輸入
- 2.6.2 數據的輸出
- 2.6.3 格式化輸出
- 2.7 編程案例:查找問題
- 2.8 練習
- 第 3 章 數據處理的流程控制
- 3.1 順序控制結構
- 3.2 分支控制結構
- 3.2.1 單分支結構
- 3.2.2 兩路分支結構
- 3.2.3 多路分支結構
- 3.3 異常處理
- 3.3.1 傳統的錯誤檢測方法
- 3.3.2 傳統錯誤檢測方法的缺點
- 3.3.3 異常處理機制
- 3.4 循環控制結構
- 3.4.1 for 循環
- 3.4.2 while 循環
- 3.4.3 循環的非正常中斷
- 3.4.4 嵌套循環
- 3.5 結構化程序設計
- 3.5.1 程序開發過程
- 3.5.2 結構化程序設計的基本內容
- 3.6 編程案例:如何求 n 個數據的最大值?
- 3.6.1 幾種解題策略
- 3.6.2 經驗總結
- 3.7 Python 布爾表達式用作控制結構*
- 3.8 練習
- 第 4 章 模塊化編程
- 4.1 模塊化編程基本概念
- 4.1.1 模塊化設計概述
- 4.1.2 模塊化編程
- 4.1.3 編程語言對模塊化編程的支持
- 4.2 Python 語言中的函數
- 4.2.1 用函數減少重復代碼 首先看一個簡單的用字符畫一棵樹的程序:
- 4.2.2 用函數改善程序結構
- 4.2.3 用函數增強程序的通用性
- 4.2.4 小結:函數的定義與調用
- 4.2.5 變量的作用域
- 4.2.6 函數的返回值
- 4.3 自頂向下設計
- 4.3.1 頂層設計
- 4.3.2 第二層設計
- 4.3.3 第三層設計
- 4.3.4 第四層設計
- 4.3.5 自底向上實現與單元測試
- 4.3.6 開發過程小結
- 4.4 Python 模塊*
- 4.4.1 模塊的創建和使用
- 4.4.2 Python 程序架構
- 4.4.3 標準庫模塊
- 4.4.4 模塊的有條件執行
- 4.5 練習
- 第 5 章 圖形編程
- 5.1 概述
- 5.1.1 計算可視化
- 5.1.2 圖形是復雜數據
- 5.1.3 用對象表示復雜數據
- 5.2 Tkinter 圖形編程
- 5.2.1 導入模塊及創建根窗口
- 5.2.2 創建畫布
- 5.2.3 在畫布上繪圖
- 5.2.4 圖形的事件處理
- 5.3 編程案例
- 5.3.1 統計圖表
- 5.3.2 計算機動畫
- 5.4 軟件的層次化設計:一個案例
- 5.4.1 層次化體系結構
- 5.4.2 案例:圖形庫 graphics
- 5.4.3 graphics 與面向對象
- 5.5 練習
- 第 6 章 大量數據的表示和處理
- 6.1 概述
- 6.2 有序的數據集合體
- 6.2.1 字符串
- 6.2.2 列表
- 6.2.3 元組
- 6.3 無序的數據集合體
- 6.3.1 集合
- 6.3.2 字典
- 6.4 文件
- 6.4.1 文件的基本概念
- 6.4.2 文件操作
- 6.4.3 編程案例:文本文件分析
- 6.4.4 緩沖
- 6.4.5 二進制文件與隨機存取*
- 6.5 幾種高級數據結構*
- 6.5.1 鏈表
- 6.5.2 堆棧
- 6.5.3 隊列
- 6.6 練習
- 第 7 章 面向對象思想與編程
- 7.1 數據與操作:兩種觀點
- 7.1.1 面向過程觀點
- 7.1.2 面向對象觀點
- 7.1.3 類是類型概念的發展
- 7.2 面向對象編程
- 7.2.1 類的定義
- 7.2.2 對象的創建
- 7.2.3 對象方法的調用
- 7.2.4 編程實例:模擬炮彈飛行
- 7.2.5 類與模塊化
- 7.2.6 對象的集合體
- 7.3 超類與子類*
- 7.3.1 繼承
- 7.3.2 覆寫
- 7.3.3 多態性
- 7.4 面向對象設計*
- 7.5 練習
- 第 8 章 圖形用戶界面
- 8.1 圖形用戶界面概述
- 8.1.1 程序的用戶界面
- 8.1.2 圖形界面的組成
- 8.1.3 事件驅動
- 8.2 GUI 編程
- 8.2.1 UI 編程概述
- 8.2.2 初識 Tkinter
- 8.2.3 常見 GUI 構件的用法
- 8.2.4 布局
- 8.2.5 對話框*
- 8.3 Tkinter 事件驅動編程
- 8.3.1 事件和事件對象
- 8.3.2 事件處理
- 8.4 模型-視圖設計方法
- 8.4.1 將 GUI 應用程序封裝成對象
- 8.4.2 模型與視圖
- 8.4.3 編程案例:匯率換算器
- 8.5 練習
- 第 9 章 模擬與并發
- 9.1 模擬
- 9.1.1 計算機建模
- 9.1.2 隨機問題的建模與模擬
- 9.1.3 編程案例:乒乓球比賽模擬
- 9.2 原型法
- 9.3 并行計算*
- 9.3.1 串行、并發與并行
- 9.3.2 進程與線程
- 9.3.3 多線程編程的應用
- 9.3.4 Python 多線程編程
- 9.3.5 小結
- 9.4 練習
- 第 10 章 算法設計和分析
- 10.1 枚舉法
- 10.2 遞歸
- 10.3 分治法
- 10.4 貪心法
- 10.5 算法分析
- 10.5.1 算法復雜度
- 10.5.2 算法分析實例
- 10.6 不可計算的問題
- 10.7 練習
- 第 11 章 計算+X
- 11.1 計算數學
- 11.2 生物信息學
- 11.3 計算物理學
- 11.4 計算化學
- 11.5 計算經濟學
- 11.6 練習
- 附錄
- 1 Python 異常處理參考
- 2 Tkinter 畫布方法
- 3 Tkinter 編程參考
- 3.1 構件屬性值的設置
- 3.2 構件的標準屬性
- 3.3 各種構件的屬性
- 3.4 對話框
- 3.5 事件
- 參考文獻