暴力搜尋

  此條目介紹的是電腦科學中的搜尋演算法。關於數學中的窮舉證明法，請見「窮舉法」。關於密碼學中的暴力破解法，請見「蠻力攻擊」。

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

找出自然數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位元的十進制數字，那麼搜尋將會執行至少10¹⁵條電腦指令，在一台典型的電腦上這將花費幾天的時間。如果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。更一般地來講，假定先前的試驗失敗，搜尋空間應該被以下一個候選項更可能有效的方式列舉，因此，如果有效解在某種意義上是「聚集的」，則每個新的候選項應當儘可能地與先前的候選項相同。相反的話，解決方案可能比預計的偶然分部分散的更加均勻。

暴力搜尋的替代方法

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

在密碼學中的應用

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