[科普中國]-暴力搜索

在計(jì)算機(jī)科學(xué)中，暴力搜索是一個(gè)非常一般的解決問題的技術(shù)，包括系統(tǒng)地枚舉解決方案的所有可能的候選項(xiàng)，以及檢查每個(gè)候選項(xiàng)是否符合問題的描述。

找出自然數(shù)n的約數(shù)的暴力算法將枚舉出從1到n的所有整數(shù)，并檢查它們中的每一個(gè)是否除n后都沒有余數(shù)。針對(duì)八皇后問題的暴力算法會(huì)檢查所有在8X8棋盤上八個(gè)“皇后”可能的擺放方法，并且，對(duì)每一種擺放方法，檢查其每一個(gè)“皇后”是否能攻擊到其它人。

簡介網(wǎng)格算法和窮舉法。兩者都是暴力搜索最優(yōu)點(diǎn)的算法，在很多競賽題中有應(yīng)用，當(dāng)重點(diǎn)討論模型本身而輕視算法的時(shí)候，可以使用這種暴力方案，最好使用一些高級(jí)語言作為編程工具。是數(shù)學(xué)建模十類算法之一。

在信息學(xué)競賽中，暴力搜索不用技巧，類似窮舉，對(duì)于有點(diǎn)難度的題目，暴力搜索一般都會(huì)超時(shí)。

雖然暴力搜索很容易實(shí)現(xiàn)，并且如果解決方案存在它就一定能夠找到，但是它的代價(jià)是和候選方案的數(shù)量成比例的，由于這一點(diǎn)，在很多實(shí)際問題中，消耗的代價(jià)會(huì)隨著問題規(guī)模的增加而快速地增長。因此，當(dāng)問題規(guī)模有限，或當(dāng)存在可用于將候選解決方案的集合減少到可管理大小的針對(duì)特定問題的啟發(fā)式算法時(shí)，通常使用暴力搜索。另外，當(dāng)實(shí)現(xiàn)方法的簡單度比速度更重要的時(shí)候，也會(huì)用到這種方法。

例如，在關(guān)鍵的應(yīng)用中，或當(dāng)用計(jì)算機(jī)證明數(shù)學(xué)定理時(shí)，算法中的任何錯(cuò)誤將會(huì)導(dǎo)致嚴(yán)重的后果。暴力搜索也可在其他基準(zhǔn)化算法和啟發(fā)式算法里用作基準(zhǔn)方法。事實(shí)上，暴力搜索可以被看作最簡單的啟發(fā)式算法。暴力搜索與回溯概念是不相同的，在回溯算法中，大量的解決方案并沒有被列舉而直接被丟棄（例如上文提到的“八皇后問題”的解決方案）。用于在表中查找一個(gè)項(xiàng)目，也就是說順序地檢查表中所有條目的暴力方法被稱為線性搜索。1

基本算法為了將暴力搜索算法應(yīng)用于特定類別的問題，必須實(shí)現(xiàn)四個(gè)步驟：“first”、“next”、“valid”以及“output”。這些步驟應(yīng)該將待解決的問題的特定實(shí)例的數(shù)據(jù)P作為參數(shù)，并且進(jìn)行以下操作：

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

2.next(P,c)：生成當(dāng)前一個(gè)解c之后的下一個(gè)P的候選解；

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

4.output(P,c)：將P的解決方案c應(yīng)用于適當(dāng)?shù)爻绦颉?/p>

另外，“first”步驟也必須在當(dāng)前解之后不再有P的候選解時(shí)給出說明，完成這一點(diǎn)的簡單的方法是返回一個(gè)“空候選項(xiàng)”，即一些不同于真實(shí)候選的常規(guī)數(shù)據(jù)值Λ。同樣地，如果實(shí)例P沒有任何候選項(xiàng)，“first”步驟應(yīng)該返回Λ。暴力搜索可以用以下算法描述：

c←first(P)

whilec≠ Λdo

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

c←next(P,c)

end while

例如，當(dāng)查找整數(shù)n的約數(shù)時(shí)，實(shí)例P就是整數(shù)n。若n>=1，調(diào)用first(n)應(yīng)該返回整數(shù)1，若n=c，調(diào)用next(n,c)應(yīng)該返回c+1，若n=1和c