Can you summarize the following document?
        
  

  為了將暴力搜尋演算法應用於特定類別的問題,必須實現四個步驟:“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!,大約是formula_1;並且搜尋將會花費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。更一般地來講,假定先前的試驗失敗,搜尋空間應該被以下一個候選項更可能有效的方式列舉,因此,如果有效解在某種意義上是“聚集的”,則每個新的候選項應當儘可能地與先前的候選項相同。相反的話,解決方案可能比預計的偶然分部分散的更加均勻。

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

  在密碼學中,暴力攻擊與系統地檢查所有的金鑰直到找出正確的金鑰有關。這個策略在理論上可以用於在攻擊者無法利用加密系統中任何弱點時攻擊任何加密的資料(除了一次性密碼),否則破譯密碼的任務會更加容易。 加密中使用的金鑰長度決定了執行暴力攻擊的實際可行性,其中較長的金鑰比較短的更難以破解。可以通過混淆編碼資料的方法降低暴力攻擊的有效性,這種方法就是讓攻擊者更難意識到他已經破解了密碼。衡量加密系統的標準之一就是理論上攻擊者成功地暴力破解密碼所需花費時間的長短。
在電腦科學中,暴力搜尋或者說窮舉搜尋,也稱為生成與測試,是一種非常低效的解決問題的技術,方法包括了系統地列舉解決方案的所有可能候選項,以及檢查每個候選項是否符合問題描述。