暴力搜索

**暴力搜尋**或**窮舉搜尋**，在電腦科學中也稱**生成與測試**，是一種非常低效的解決問題的技術，方法包括了系統地列舉解決方案的所有可能候選項，以及檢查每個候選項是否符合問題描述。

找出自然數 n 的約數的暴力搜尋演算法將列舉出從 1 到 n 的所有整數，並檢查它們中的每一個是否除 n 後沒有餘數。針對八皇后問題的暴力搜尋演算法會檢查所有在 8X8 棋盤上八個「皇后」可能的擺放方法，並且，對每一種擺放方法，檢查其每一個「皇后」是否能攻擊到其它人。

雖然暴力搜尋很容易實現，並且如果解決方案存在，它就一定能夠找到。但是它的代價是和候選方案的數量成正比，由於這一點，在很多實際問題中，消耗的代價會隨著問題規模的增加而快速地增長。因此，當問題規模有限，或當存在可用於將候選解決方案的集合減少到可管理大小的針對特定問題的啟發式演算法時，通常使用暴力搜尋。另外，當實現方法的簡單度比速度更重要的時候，也會用到這種方法。

例如，在關鍵的應用中，或當用電腦證明數學定理時，演算法中的任何錯誤將會導致嚴重的後果。暴力搜尋也可在其他基準化演算法和啟發式演算法里用作基準方法。事實上，暴力搜尋可以被看作最簡單的啟發式演算法。暴力搜尋與回溯概念是不相同的，在回溯演算法中，大量的解決方案並沒有被列舉而直接被丟棄（例如上文提到的「八皇后問題」的解決方案）。用於在表中尋找一個專案，也就是說順序地檢查表中所有條目的暴力方法被稱為線性搜尋。

## 實現

### 基本演算法

為了將暴力搜尋演算法應用於特定類別的問題，必須實現四個步驟：「first」、「next」、「valid」以及「output」。這些步驟應該將待解決的問題的特定實例的資料 P 作為參數，並且進行以下操作：

1.first (P)：生成用於 P 的第一個候選解決方案；

2.next (P,c)：生成當前一個解 c 之後的下一個 P 的候選解；

3.valid (P,c)：檢查候選項 c 是否為 P 的解；

4.output (P,c)：將 P 的解決方案 c 應用於適當地程式。

另外，「first」步驟也必須在當前解之後不再有 P 的候選解時給出說明，完成這一點的簡單的方法是返回一個「空候選項」，即一些不同於真實候選的常規資料值 Λ。同樣地，如果實例 P 沒有任何候選項，「first」步驟應該返回 Λ。暴力搜尋可以用以下演算法描述：

_c_ ← _first_(_P_)

**while** _c_ ≠ Λ **do**

**if** _valid_(_P_,_c_) **then** _output_(_P_, _c_)

_c_ ← _next_(_P_,_c_)

**end while**

例如，當尋找整數 n 的約數時，實例 P 就是整數 n。若 n>=1，呼叫 first (n) 應該返回整數 1，若 n<1 返回 Λ；若 n>=c，呼叫 next (n,c) 應該返回 c+1，若 n<c 則返回 Λ；並且 valid (n,c) 應該返回 true 若且唯若 c 是 n 的約數。（實際上，如果我們選定 n+1 作為 Λ，那麼檢測 n>=1 和 c<n 就是不必要的。）上面的暴力搜尋演算法會為每一個作為給定實例 P 的解的候選項呼叫 output。該演算法很容易被修改以在找到第一個解或指定數目的解之後停止，或者在測試指定數量的候選項之後，或者在花費給定量的 CPU 時間之後。

## 組合爆炸

暴力搜尋的主要缺點是，對於許多現實世界中的問題，自然候選項的數量大得驚人。例如，就像上文描述的，如果尋找一個數的約數，待測的候選項的數量將是給定的數字 n，所以如果 n 是 16 位元的十進位數字，那麼搜尋將會執行至少 1015 條電腦指令，在一台典型的電腦上這將花費幾天的時間。如果 n 是一個任意的 64 位元自然數，平均就有 19 個十進位，那麼搜尋將會耗費大約十年的時間。這種隨著資料規模的增加，候選項數量急劇增長的現象發生在所有種類的問題中。舉個例子，如果我們想要一個特殊的 10 個字母的重排，那麼我們有 10! 共 3,628,800 個待考的候選項，一個典型的電腦可以在 1 秒內完成生成和測試。然而，增加 1 個字母 —— 這只是資料規模的 10%，將會使候選項數量乘上 11—— 增長 1000%。對於 20 個字母，候選項的數量就是 20!，大約是 $2.4\times 10^{18}$ ；並且搜尋將會花費 10 年的時間，這種不受歡迎的現象通常被稱為組合爆炸或維數災難。

## 加速暴力搜尋

加快暴力搜尋的一種方法是通過使用具體問題類的啟發式方法減小搜尋空間，也就是減小候選解決方案的集合。例如，在「八皇后問題」中，挑戰就是將八個皇后放置在標準的棋盤上，以致沒有皇后能夠攻擊到其它任何皇后。因為每一個皇后可以被放在 64 個方格中的任何一個上，理論上來講就有 = 281,474,976,710,656 個待測的可能性。然而，因為所有皇后都是相似的，而且任意兩個都不能放在同一個方格中，候選項為從所有 64 個方格集合中選出的 8 個方格集合的所有可能的方式，這就意味著 64 選 8，即 64!/56!/8! = 4,426,165,368 個候選解決方案 —— 約為先前估計的 1/60,000。更進一步，在同一行或同一列上放兩個皇后的安排不是解決方案。因此，我們可以進一步約束那些放置方法的候選項集合。

正如這個例子所示，一點點的分析經常會導致候選方案的數量大幅減少，而且可能將一個棘手的問題變得很普通。

在一些情況下，分析可能會減小有效的候選解決方案的集合，也就是說，它可以產生直接列舉所有期望解的演算法（或適當地找到一個解），而不將時間浪費在生成和測試無效的候選項上。舉個例子，對於「找出所有 1 與 1,000,000 之間的能被 417 整除的所有整數」這個問題，一個簡單的暴力搜尋方法是產生這個範圍內所有整數並測試每一個能否被整除。然而，這個問題可以採用從 417 開始並且每次增加 417 直到超出 1,000,000 這種辦法從而被更高效地解決，而這種辦法只需要 2398 (=1,000,000÷417) 步而且不需要測試。

## 重新排序搜尋空間

在只需要一個解決方案而不是全部的應用程式中，暴力搜尋的期望執行時間通常依賴於候選項測試的順序。作為一般規則，應該首先測試最有希望的候選項。例如，當搜尋亂數 n 的適當約數時，以遞增的順序即從 2 到 n-1 列舉候選約數比相反的順序更好，因為 c 能被 n 整除的概率是 1/c。此外，候選項有效的概率經常會受之前失敗的試驗影響。例如，考慮在給定的 1000 位的字串中找到」1」的問題，在這種情況下，候選解決方案是 1 到 1000 的索引，並且如果 P [c] = 1 的話候選項 c 就是有效的。現在，假定 P 的第一位為 0 或 1 的可能性相同，但是之後每一位跟前一位相等的概率為 90%。如果候選項被以遞增的順序列舉，即從 1 到 1000，在成功之前待測的候選項數量 t 平均大約是 6。另外，如果候選項被以下面的順序列舉：1,11,21,31,…,991,2,12,22,32…，t 的期望值將僅稍大於 2。更一般地來講，假定先前的試驗失敗，搜尋空間應該被以下一個候選項更可能有效的方式列舉，因此，如果有效解在某種意義上是「聚集的」，則每個新的候選項應當儘可能地與先前的候選項相同。相反的話，解決方案可能比預計的偶然分部分散的更加均勻。

## 暴力搜尋的替代方法

對於各不同門類的知識，存在很多的搜尋方法或元啟發演算法能求得解決方案，啟發式方法也可用於提前截斷搜尋的部分。這樣的一個例子就是搜尋遊戲樹的最小化原則，其在搜尋的早期消除了許多子樹。在某些領域，例如語言分析中，一些技術例如圖解法可以利用問題中的約束條件將指數複雜度的問題簡化到多項式複雜度的問題。在很多情況下，如在約束滿足問題中，通過約束傳播可以極大地減小搜尋空間，這一點在約束程式語言中被高效實現了。問題的搜尋空間可以通過用簡化版本代替完整的問題來實現。例如，在電腦象棋中，並不是計算遊戲剩餘部分所有移動可能的極大極小樹，而是計算有限範圍內的極大極小可能性的樹，即由完整樹以特定的移動步數修剪得到，而且這個樹須和靜態評估函式近似。

## 在密碼學中的應用

在密碼學中，暴力攻擊與系統地檢查所有的金鑰直到找出正確的金鑰有關。這個策略在理論上可以用於在攻擊者無法利用加密系統中任何弱點時攻擊任何加密的資料（除了一次性密碼），否則破譯密碼的任務會更加容易。
加密中使用的金鑰長度決定了執行暴力攻擊的實際可行性，其中長度較長的金鑰相比長度較短的更難以被破解。可以通過混淆編碼資料的方法降低暴力攻擊的有效性，這種方法就是讓攻擊者更難意識到他已經破解了密碼。衡量加密系統的標準之一就是理論上攻擊者暴力破解密碼所需時間的長短。

## 參考資料