本文系 王曉華 老師 GitChat 【算法應該怎么玩】課程筆記。

1. 窮舉法概念

窮舉法又稱窮舉搜索法，是一種在問題域的解空間中對所有可能的解窮舉搜索，并根據條件選擇最優解的方法的總稱。

數學上也把窮舉法稱為枚舉法，就是在一個由有限個元素構成的集合中，把所有元素一一枚舉研究的方法。

窮舉法一般用來找出符合條件的所有解，但是如果給出最優解的判斷條件，窮舉法也可以用于求解最優解問題。

2. 設計思路

使用窮舉法解決問題，基本上就是以下兩個步驟：

• 確定問題的解（或狀態）的定義、解空間的范圍以及正確解的判定條件；
• 根據解空間的特點來選擇搜索策略，逐個檢驗解空間中的候選解是否正確；

2.1 解空間定義

解空間就是全部可能的候選解的一個約束范圍，確定問題的解就在這個約束范圍內，將搜索策略應用到這個約束范圍就可以找到問題的解。

2.2 窮舉解空間的策略

窮舉解空間的策略就是搜索算法的設計策略，根據問題的類型，解空間的結構可能是線性表、集合、樹或者圖，對于不同類型的解空間，需要設計與之相適應的窮舉搜索算法。

如果選擇一種搜索策略，不帶任何假設的窮舉搜索，不管行不行，眉毛胡子一把抓，把所有可能的解都檢查一遍，這樣的搜索通常被稱為“盲目搜索”。

與之對應的是利用某種策略或計算依據，由啟發函數策動有目的的搜索行為，這些策略和依據通常能夠加快算法的收斂速度，或者能夠劃定一個更小的、最有可能出現解的空間并在此空間上搜索，這樣的搜索通常稱為“啟發性搜索”。

一般來說，為了加快算法的求解，通常會在搜索算法的執行過程中輔助一些剪枝算法，排除一些明顯不可能是正確解的檢驗過程，來提高窮舉的效率。

剪枝一個很形象的比喻，如果某一個狀態節點確定不可能演化出結果，就應該停止從這個狀態節點開始的搜索，相當于狀態樹上這一分枝就被剪掉了。

除了采用剪枝策略，還可以使用限制搜索深度的方法加快算法的收斂，但是限制搜索深度會導致無解，或錯過最優解，通常只在特定的情況下使用，比如博弈樹的搜索。

2.3 剪枝策略

對解空間窮舉搜索時，如果有一些狀態節點可以根據問題提供的信息明確地被判定為不可能演化出最優解，也就是說，從此節點開始遍歷得到的子樹，可能存在正確的解，但是肯定不是最優解，就可以跳過此狀態節點的遍歷，這將極大地提高算法的執行效率，這就是剪枝策略，應用剪枝策略的難點在于如何找到一個評價方法（估值函數）對狀態節點進行評估。

3. 實例

3.1 百錢買雞問題

一百個錢買一百只雞，是個典型的窮舉法應用。問題描述：每只大公雞值 5 個錢，每只母雞值 3 個錢，每 3 只小雞值 1 個錢，現在有 100 個錢，想買 100 只雞，問如何買？有多少種方法？

1. 盲目搜索
   假設買 x 只公雞，y 只母雞，z 只小雞，使用代碼求解如下：

   %%time
   for x in range(1, 100):for y in range(1, 100):for z in range(1, 100):if x + y + z == 100 and 5*x + 3*y + z/3.0 == 100:print x, y, z
   

   輸出結果

   4 18 78
   8 11 81
   12 4 84
   CPU times: user 76.3 ms, sys: 0 ns, total: 76.3 ms
   Wall time: 75.2 ms
   

2. 啟發搜索
   假設買 x 只公雞，y 只母雞，則 x 最大只能是 20 只，y 最大只能是 33 只，而小雞則應該為 100 -x-y 只，使用代碼求解如下：

   %%time
   for x in range(1, 21):for y in range(1, 34):if 5*x + 3*y + (100-x-y)/3.0 == 100:print x, y, 100-x-y
   

   輸出結果

   4 18 78
   8 11 81
   12 4 84
   CPU times: user 4.43 ms, sys: 0 ns, total: 4.43 ms
   Wall time: 2.56 ms
   

可以看出第二種搜索算法比第一種明顯快很多。

3.2 雞兔同籠問題

窮舉法的經典題目：雞兔同籠問題。有雞和兔在一個籠子中，數頭共 50 個頭，數腳共 120 只腳，問：雞和兔分別有多少只？

1. 盲目搜索
   假設買 x 雞，y 只兔，使用代碼求解如下：

   %%time
   for x in range(1, 51):for y in range(1, 51):if x + y == 50 and 2*x + 4*y == 120:print x, y
   

   輸出結果

   40 10
   CPU times: user 0 ns, sys: 3.19 ms, total: 3.19 ms
   Wall time: 2.17 ms
   

2. 啟發搜索
   假設買 x 雞，則兔子數量只能是 50 - x ，使用代碼求解如下：

   %%time
   for x in range(1, 51):if 2*x + 4*(50-x) == 120:print x, 50-x
   

   輸出結果

   40 10
   CPU times: user 190 μs, sys: 0 ns, total: 190 μs
   Wall time: 137 μs
   

同樣也可以看出第二種搜索算法比第一種明顯快很多。

總結

以上是生活随笔為你收集整理的算法设计思想（1）— 穷举法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。