暴力搜索

網格算法和窮舉法。兩者都是暴力搜索最優點的算法，在很多競賽題中有應用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。是數學建模十類算法之一。

在信息學競賽中，暴力搜索不用技巧，類似窮舉，對於有點難度的題目，暴力搜索一般都會超時。

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

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

為了將暴力搜索算法應用於特定類別的問題，必須實現四個步驟：“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)

whilec≠ Λdo

ifvalid(P,c)thenoutput(P,c)

c←next(P,c)

例如，當查找整數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位的十進制數字，那麼搜索將會執行至少條計算機指令，在一台典型的PC機上這將花費幾天的時間。如果n是一個任意的64位自然數，平均就有19個十進制位，那麼搜索將會耗費大約十年的時間。這種隨着數據規模的增加，候選項數量急劇增長的現象發生在所有種類的問題中。舉個例子，如果我們想要一個特殊的10個字母的重排，那麼我們有10!= 3,628,800個待考的候選項，一個典型的PC機可以在1秒內完成生成和測試。然而，增加1個字母——這只是數據規模的10%，將會使候選項數量乘上11——增長1000%。對於20個字母，候選項的數量就是20!，大約是2.4X；並且搜索將會花費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。更一般地來講，假定先前的試驗失敗，搜索空間應該被以下一個候選項更可能有效的方式枚舉，因此，如果有效解在某種意義上是“聚集的”，則每個新的候選項應當儘可能地與先前的候選項相同。相反的話，解決方案可能比預計的偶然分部分散的更加均勻。

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

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