## 10.1 枚舉法 問題求解中常用的一種算法設計方法是枚舉策略。給定問題 P，如果知道 P 的可能解構 成一個有限集合 S = {s1, s2, ..., sn}，則可以逐一列舉每個 si，檢驗它是否確實是 P 的解，這 就是枚舉法。枚舉法簡單而直接，算法容易設計實現，但當可能解集合 S 很大時，枚舉策 略的效率很差。實際使用枚舉法時，經常利用各種已知條件來從 S 中排除掉一部分不可能 情形，從而優化枚舉過程。下面通過幾個例子來說明枚舉策略在設計算法中的應用。 線性搜索 首先看一個程序設計中常見的問題——搜索（或稱查找）問題：給定數據集合 D，在 D 中查找指定數據 x。 搜索問題看上去很容易解決，一個顯而易見的做法是：反復從 D 中讀取下一個數據， 看看它是否 x，搜索結果是要么找到 x，要么發現 D 中沒有 x。然而，這個“算法”是有問 題的，因為它需要一個關鍵操作——“讀取取下一個數據”，而“下一個”未必是良定義的。 打個比方，如果一群人站成一排，當我們要從中找出張三時，可以采取按排隊次序逐個詢問 的策略。但如果這群人散亂無規則地站在一起，我們該如何循著一個有條理的過程找出張三 來呢？如何決定“下一個”要詢問的人？ 可見，要想在一個數據集合中找到指定數據，就必須能夠按某種系統化的方式逐個列舉 集合元素，并與指定數據進行比較。這就是枚舉策略在搜索問題中的應用。 如果將大量數據存儲在一個列表中，則使用枚舉策略很合適，因為列表是通過位置索引 來訪問其中數據成員的，“讀取下一個數據”是良定義的操作，只要將當前位置索引加 1 即 可得下一個數據的索引。下面定義的函數 find()實現了這種搜索策略：給定數據列表 list 和 需要查找的數據 x，逐個取出 list 的成員并與 x 進行比較。如果某個成員就是 x，則返回該 成員在列表中的位置索引；如果 list 中沒有 x 則返回-1。 ``` >>> def find(list,x): for i in range(len(list)): if list[i] == x: return i return -1 >>> find([2,4,6,8],6) 2 >>> find([2,4,6,8],7) -1 ``` find()函數對列表 list 從頭到尾進行掃描，掃描過程中檢驗每一個成員是否 x，這個算法 稱為線性搜索（linear search）算法。線性搜索算法很容易設計實現，而且當數據量不太大時，算法的性能也還可以。更重要的是，由于線性搜索是枚舉每一個數據成員，因此適用于 無序數據集合，即數據沒有按特定的大小次序排列。 然而，當數據量很大時，逐個枚舉集合中的數據就變得非常低效。這時只能通過更好地 組織數據，利用額外信息來提高搜索效率，盡量避免逐個檢查所有數據。例如，假設列表數 據從小到大有序排列，那么在枚舉過程中一旦發現當前取出的數據大于 x，就不必再繼續搜 索了，可以直接下結論說找不到 x。這種改進可以提高線性搜索算法的性能，但改善得很有 限。事實上，在數據有序的情況下，存在比線性搜索算法好得多的算法（見 10.2）。 線性搜索算法只適用于“一維”搜索空間，即所有數據排列成一排的情形。考慮在如下 矩陣中查找某個數據的問題：  這時顯然無法直接采用線性搜索算法。在類似矩陣這樣的“二維”搜索空間中，如何枚舉每 一個數據呢？這個問題其實在第 3 章中介紹循環語句時就討論過，為了遍歷（即枚舉）這樣 的二維空間，可以采用嵌套的循環語句。例如下面這個 find2D()函數實現了在 row 行、col 列的矩陣 matrix 中查找數據 x 的枚舉算法： ``` >>> def find2D(matrix,row,col,x): for i in range(row): for j in range(col): if matrix[i][j] == x: return (i+1,j+1) return -1 >>> find2D([[1,2,3],[4,5,6]],2,3,6) (2, 3) >>> find2D([[1,2,3],[4,5,6]],2,3,7) -1 ``` 顯然，這個做法可以擴展到更多維的搜索空間，利用 n 層嵌套循環即可枚舉 n 維搜索空 間中的數據。 求解不定方程 有時問題的所有可能解并沒有像上例那樣明確地存儲在某個具體集合（如列表）中，而 是構成一個無形的搜索空間，那該如何枚舉可能解呢？這需要具體問題具體分析，根據問題 的特點設計枚舉方式。下面是一個典型的例子。 中國古代數學著作中有一道“百錢買百雞”問題：假設公雞每只 5 元錢，母雞每只 3 元錢，雞雛每三只 1 元錢，用一百元錢買了一百只雞，問公雞、母雞和雞雛各買了幾只？具 備初等代數知識的人都不難列出如下方程組來求解這個問題： ``` x + y + z = 100 5x + 3y + z/3 = 100 ``` 其中 x、y、z 分別表示公雞、母雞和雞雛的個數。 此方程組有三個未知數卻只有兩個方程式，屬于數學中所稱的不定方程。人工求解不定 方程通常會利用方程變形、未知數代換以及分析各種約束條件等技巧，而絕不會采用枚舉所 有可能解進行檢驗的方法，因為可能解構成的空間通常非常龐大。然而，計算機的優點恰恰 在于能夠高速地、機械地執行大量的檢驗任務，因此采用枚舉策略來解不定方程是簡單而直 接的做法。問題是如何枚舉各種可能解呢？對于百錢買百雞問題，顯然只需為三個未知數做 各種可能的賦值，然后檢查是否滿足上述兩個方程式即可。各未知數的可能值都在 100 之內（因為只買了 100 只雞），所以利用枚舉法很容易得到下列程序： ``` >>> for x in range(100): for y in range(100): for z in range(100): t = x + y + z m = 5*x + 3*y + z/3 if t == 100 and m == 100: print "x=",x,",y=",y,",z=",z x= 0 ,y= 25 ,z= 75 x= 3 ,y= 20 ,z= 77 x= 4 ,y= 18 ,z= 78 x= 7 ,y= 13 ,z= 80 x= 8 ,y= 11 ,z= 81 x= 11 ,y= 6 ,z= 83 x= 12 ,y= 4 ,z= 84 ``` 采用枚舉策略時應當盡量減小可能解集合，以便提高枚舉效率。上面這個程序的效率顯 然太差，因為三重嵌套循環實際上要枚舉 100×100×100 種 x、y、z 組合。其實稍加思考就 能找到減小需要檢驗的可能解的數目的方法。首先，不需要三層嵌套循環，因為當 x 和 y 的值給定，z 的值就確定了（即 100–x–y），沒有必要再去枚舉 z；其次，x 的可能值不超 過 20（否則錢不夠），同理 y 的可能值不超過 33；最后，依題意每種雞應當都至少買 1 只， 沒有必要考慮等于 0 的情形。將這些分析落實到編程中，即可得效率更高的代碼： ``` >>> for x in range(1,20): for y in range(1,33): z = 100 - x - y m = 5*x + 3*y + z/3 if m == 100: print "x=",x,",y=",y,",z=",z x= 3 ,y= 20 ,z= 77 x= 4 ,y= 18 ,z= 78 x= 7 ,y= 13 ,z= 80 x= 8 ,y= 11 ,z= 81 x= 11 ,y= 6 ,z= 83 x= 12 ,y= 4 ,z= 84 ``` 利用問題中的各種約束條件往往可以減少搜索空間或者優化枚舉過程。例如，假設為 “百錢買百雞”問題附加一個條件“盡量多買公雞”，那么可以這樣優化算法：最外層對 x 的循環中改用 range(20,0,-1)，以便盡快找到滿足條件的值，得到第一個解之后就可以 終止程序，不必再找其他解了。 通過以上例子，我們看到枚舉算法的核心思想是對問題的每一個可能解進行檢驗，看看 是否滿足特定條件，這個枚舉過程在編程時是通過循環語句和條件語句實現的。對于一些復 雜問題，如果嵌套循環的層數不確定或者層數太多，直接使用循環語句和條件語句實現枚舉 檢驗是不合適甚至不可能的，這時可以考慮采用遞歸技術（見 10.2）。 當問題規模較大時，可能解的空間也很大，采用枚舉策略會導致效率很差。但是，鑒于 枚舉算法設計簡單，調試也容易，對于規模較小的問題是很好的策略。即使對于大規模的復 雜問題，枚舉策略也可以作為整體求解算法的子算法出現。 最后總結一下采用枚舉策略設計算法的一般步驟： (1) 確定枚舉對象、枚舉范圍和判定條件； (2) 枚舉各可能解，逐一驗證是否所需的問題解。 (3) 盡量減小枚舉范圍，提高算法效率。