基本介紹
- 中文名：暴力搜尋
- 外文名：Violent search
- 又稱：窮舉搜尋、生成與測試
簡介,基本算法,組合爆炸,加速暴力搜尋,重新排序搜尋空間,暴力搜尋的替代方法,在密碼學中的套用,
簡介
格線算法和窮舉法。兩者都是暴力搜尋最優點的算法，在很多競賽題中有套用，當重點討論模型本身而輕視算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具。是數學建模十類算法之一。
在信息學競賽中，暴力搜尋不用技巧，類似窮舉，對於有點難度的題目，暴力搜尋一般都會逾時。
雖然暴力搜尋很容易實現，並且如果解決方案存在它就一定能夠找到，但是它的代價是和候選方案的數量成比例的，由於這一點，在很多實際問題中，消耗的代價會隨著問題規模的增加而快速地增長。因此，當問題規模有限，或當存在可用於將候選解決方案的集合減少到可管理大小的針對特定問題的啟發式算法時，通常使用暴力搜尋。另外，當實現方法的簡單度比速度更重要的時候，也會用到這種方法。
例如，在關鍵的套用中，或當用計算機證明數學定理時，算法中的任何錯誤將會導致嚴重的後果。暴力搜尋也可在其他基準化算法和啟發式算法里用作基準方法。事實上，暴力搜尋可以被看作最簡單的啟發式算法。暴力搜尋與回溯概念是不相同的，在回溯算法中，大量的解決方案並沒有被列舉而直接被丟棄（例如上文提到的“八皇后問題”的解決方案）。用於在表中查找一個項目，也就是說順序地檢查表中所有條目的暴力方法被稱為線性搜尋。
基本算法
為了將暴力搜尋算法套用於特定類別的問題，必須實現四個步驟：“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)
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位的十進制數字，那么搜尋將會執行至少條計算機指令，在一台典型的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。更一般地來講，假定先前的試驗失敗，搜尋空間應該被以下一個候選項更可能有效的方式枚舉，因此，如果有效解在某種意義上是“聚集的”，則每個新的候選項應當儘可能地與先前的候選項相同。相反的話，解決方案可能比預計的偶然分部分散的更加均勻。
暴力搜尋的替代方法
對於各不同門類的知識，存在很多的搜尋方法或元啟發式算法能求得解決方案，啟發式方法也可用於提前截斷搜尋的部分。這樣的一個例子就是搜尋遊戲樹的最小化原則，其在搜尋的早期消除了許多子樹。在某些領域，例如語言分析中，一些技術例如圖解法可以利用問題中的約束條件將指數複雜度的問題簡化到多項式複雜度的問題。在很多情況下，如在約束滿足問題中，通過約束傳播可以極大地減小搜尋空間，這一點在約束程式語言中被高效實現了。問題的搜尋空間可以通過用簡化版本代替完整的問題來實現。例如，在計算機象棋中，並不是計算遊戲剩餘部分所有移動可能的極大極小樹，而是計算有限範圍內的極大極小可能性的樹，即由完整樹以特定的移動步數修剪得到，而且這個樹須和靜態評估函式近似。
在密碼學中的套用
在密碼學中，暴力攻擊與系統地檢查所有的密鑰直到找出正確的密鑰有關。這個策略在理論上可以用於在攻擊者無法利用加密系統中任何弱點時攻擊任何加密的數據（除了一次一密），否則破譯密碼的任務會更加容易。 加密中使用的密鑰長度決定了執行暴力攻擊的實際可行性，其中較長的密鑰比較短的更難以破解。可以通過混淆編碼數據的方法降低暴力攻擊的有效性，這種方法就是讓攻擊者更難意識到他已經破解了密碼。衡量加密系統的標準之一就是理論上攻擊者成功地暴力破解密碼所需花費時間的長短。
