暴搜的美學
- 2019 年 11 月 5 日
- 筆記
暴搜的美學
引言：在noip，csp的比賽中一般情況下都會有大量的部分分可拿，某些題可以通過暴搜AC，甚至於還可以吊打標稱。。。在某些弱省，拿滿暴力分就有省一的說。。。。
然而，不管怎樣，本文所述的就好比教你如何讓你的弓箭射得更准，長矛投得更遠，即使你掌握的再好，也比不過好比電磁炮，激光槍的其他優秀算法。 本文的意圖就在於分享一些比較使用的搜索小技巧，展示搜索的精妙之處，在考場上遇到不會的題時可以寫寫暴力騙騙分。電磁炮，激光槍偶爾也會有出故障的時候。
真正的oier的思維是不會局限於暴搜的，所以當你因為用了一些本文中所提到的搜索技巧而AC了某些題目時，請放下你的暴搜，去領悟題目的美。學習暴搜，運用暴搜，並且脫離暴搜。
Part.1 暴搜的定義
本文所講的暴搜是指在可承受的數據規模內，利用計算機的高速運算能力，對題目所求的答案進行尋找。一般來說，有兩種風格不同的搜索。DFS和BFS。DFS即為深度優先搜索，一般是遞歸調用自己，利用函數的參數進行狀態轉移。BFS主要是橫向地討論每一個可能的狀態，一般利用隊列維護其狀態。
DFS 和 BFS 該如何決策呢？
總的來說 DFS 的上鏡率遠高於BFS，所以一般首選DFS
一般情況下，求最優解的情況可以考慮BFS，因為BFS的搜素順序是橫向發展的，所以第一個搜到的值一定是最優值，但BFS正因為是橫向搜索所以不方便進行剪枝的優化
同時，DFS也可以通過像迭代加深等操作來模擬橫向搜索，所以，推薦盡量使用DFS；本文也同樣會花大篇幅講DFS的各類優化。
Part.2 DFS的剪枝優化
在DFS的搜索樹上存在着許多無用的子樹，這些子樹要麼不是最優解，要麼甚至不合法，為了縮小搜索的範圍，達到騙分的目的，在這裡給出幾種常用的剪枝優化
一，記憶化剪枝
顧名思義，記憶化剪枝就是將已經搜索計算過的狀態先存下來，如過需要再次使用的時候就可以拿出來用了，這樣做會大大地提高搜索的效率，可以感性理解為搜索一次後就可以一勞永逸，當下一次搜索到該狀態時直接拿出來用就行了。該剪枝是所有剪枝中優化最明顯的，當然記憶化剪枝其實和DP之間有着密切的聯繫，這會等到後文在詳細的講述。
二，可行性剪枝
如果搜索到目前狀態發現該狀態已經不合法了，就完全不用繼續花時間搜索下去了，直接就可以return掉搜索其餘的狀態,比如說你媽要求你每天最多玩1min的電腦，然後你發現開機都用了一分鐘，你就可也return掉滾回去學習了。。
三，最優化剪枝
這個可以利用放縮法，如果假設當前的搜索狀態繼續下去，且每次都按照一個最優值都不能達到目的的話，也可以return掉，舉個例子，假設你估計了下剩下的作業和天數，發現你每天就算做24h也無法完成剩下的作業，你就可以大膽return掉了（這不是你不寫作業的理由）
四，拉斯維加斯剪枝
眾所周知，拉斯維加斯是一個賭城。。該剪枝的意義就是當你發現程序要超時了，就把當前搜索到的最優值當做全局最優值輸出。。。這是迫不得已的賭徒行為。
但能不能騙分其實真的不好說。。。。 看情況使用即可。代碼實現很簡單，記錄一個Cnt，每遞歸一次就Cnt++；Cnt大於某個值時就return
五，概率剪枝
這是一種玄學算法，能否AC取決於你的臉。。。。 模擬退火算法就是一種概率剪枝，大概的意思是說每次搜索都有一定的概率繼續往下搜索，隨着搜索的深入，往下搜索的概率就會變小，類似於物理上的退火過程，當然繼續搜索的概率是由自己來設定，也可以搞一個什麼估價函數來計算當前繼續搜索下去的概率。。。。。都是玄學，有機會以後再細談。
其他還有一些剪枝的技巧，如啟發式搜索啦之類的，將在分類講主流優化搜索時詳細講述。
Part 3.一些優秀的搜索技巧
一，Meet in the middle 雙向DFS
