暴力搜尋
維基百科,自由的 encyclopedia
暴力搜尋或窮舉搜尋,在電腦科學中也稱生成與測試是一種非常低效的解決問題的技術,方法包括了系統地列舉解決方案的所有可能候選項以及檢查每個候選項是否符合問題描述。
此條目需要補充更多來源。 (2022年6月11日) |
找出自然數n的約數的暴力搜尋演算法將列舉出從1到n的所有整數,並檢查它們中的每一個是否除n後沒有餘數。針對八皇后問題的暴力搜尋演算法會檢查所有在8X8棋盤上八個「皇后」可能的擺放方法並且對每一種擺放方法,檢查其每一個「皇后」是否能攻擊到其它人。
雖然暴力搜尋很容易實現,並且如果解決方案存在,就一定能夠找到,但是它的代價和候選方案的數量成正比,由於這一點,在很多實際問題中,消耗的代價會隨着問題規模的增加而快速地增長。因此,當問題規模有限,或當存在可用於將候選解決方案的集合減少到可管理大小的針對特定問題的啟發式演算法時,通常使用暴力搜尋。另外,當實現方法的簡單度比速度更重要的時候,也會用到這種方法。
例如,在關鍵的應用中,或當用電腦證明數學定理時,演算法中的任何錯誤將會導致嚴重的後果。暴力搜尋也可在其他基準化演算法和啟發式演算法里用作基準方法。事實上,暴力搜尋可以被看作最簡單的啟發式演算法。暴力搜尋與回溯概念是不相同的,在回溯演算法中,大量的解決方案並沒有被列舉而直接被丟棄(例如上文提到的「八皇后問題」的解決方案)。用於在表中尋找一個專案,也就是說順序地檢查表中所有條目的暴力方法被稱為線性搜尋。