前言
因為聽說打得一手好随機化搜尋的yyb據佬在考場上D2T3重測前拿下90分怒虐全場，是以蒟蒻也聞風而動了
網上好多部落格都講得十分高大上啊欺負我這種什麼也不會的蒟蒻
于是蒟蒻就想嘗試用一種更淺顯通俗的方式去了解它
算法簡述
模拟退火适用的問題通常是一些求最優解的問題
比如，把問題抽象地看成一個長成這樣的毫無規律的函數，而最優解就是函數的最低點
衆所周知，對于一個沒有辦法在多項式複雜度的算法下完成求解的問題，我們通常會想到一種簡單粗暴的方法——貪心
選擇問題的某一個狀态，然後不斷向更優的情況靠近
比如從A出發，可以獲得局部最優解B，但這顯然不是全局最優解
顯然，這樣做的局限性是，過于局限在局部的一個凹部分而無法跳出去去尋找更優的解
原理
為了解決這一問題，科學家們想到了實體的退火降溫的過程——
一個處于很高溫度的物體，現在要給它降溫，使物體内能降到最低。
我們正常的思維是，越快越好，讓它的溫度迅速地降低。
然而，實際上，過快地降溫使得物體來不及有序地收縮，難以形成結晶。而結晶态，才是物體真正内能降到最低的形态。
正确的做法，是徐徐降溫，也就是退火，才能使得物體的每一個粒子都有足夠的時間找到自己的最佳位置并緊密有序地排列。開始溫度高的時候，粒子活躍地運動并逐漸找到一個合适的狀态。在這過程中溫度也會越降越低，溫度低下來了，那麼粒子也漸漸穩定下來，相較于以前不那麼活躍了。這時候就可以慢慢形成最終穩定的結晶态了。
那麼，我們可不可以把找到最優解，與形成結晶态，這兩個過程聯系在一起呢？
于是，模拟退火誕生了。
實作過程
我們需要設定這幾個參數，模拟退火過程
- \(T\)——溫度
- \(\Delta T\)——溫度變化率，每次溫度等于上一次溫度乘上\(\Delta T\)，實際應用時一般取\(0.95-0.99\)，模拟徐徐降溫
再定義一些量
- \(x\)——目前選擇的解
- \(\Delta x\)——解變動值
- \(x_1\)——目前的目标解，等于\(x+\Delta x\)
- \(\Delta f\)——目前解的函數值與目标解函數值之差，等于\(f(x)-f(x_1)\)
我們給一個初始解\(x\)，并讓它不斷變動。要模拟變動的大小随溫度的降低而降低，我們每次的\(\Delta x\)應該在一個大小與\(T\)成正比的值域内随機取值。
這時候我們就要考慮是否将目前解變為目标解。因為我們還是需要貪心，是以如果\(f(x_1)<f(x)\)，那麼接受目标解，\(x=x_1\)
那如果\(f(x_1)>f(x)\)呢？我們當然要以一定機率接受它啦，這樣才能跳出局部的限制，去搜尋更優的解，彌補貪心的局限性。那麼這個機率應該是多少呢？同樣要模拟變動的大小随溫度的降低而降低。科學家經過理論分析，得出這個機率應該是\(e^{\Delta f \over T}\)
如此反複選擇直到\(T\)趨近于0（可以設一個EPS）這時候我們認為我們目前的\(x\)就是最優解
用圖檔來描述的話，就拿上面那個圖像尋找最優解為例
首先經過大幅波動，目前解由A->B->C，找到了一個比較滿意的解。
但還不能滿足。由于溫度還比較大，此時接受了一些不比目前解優的目标解，C->D->E，成功地爬了上去。而溫度還在慢慢減小。
終于，發現了一個更優解F，成功跳出了那個非常寬的局部凹函數
這時候，溫度越來越小了，很難再次接受不比目前解優的目标解，再次翻出去。解終于漸漸趨于穩定，并最終到達了G，找到了最優解
如此看來，基于随機的模拟退火能很大程度上提高正确率，但也不可能完全正确。上面的例子隻是随意模拟出的一個情況。是以要多跑幾遍，取每一次得到的解的最優值。
關于參數
衆所周知，模拟退火最麻煩的地方在調參，隻有合适的參數才能在一定的時間内很大機率跑出最優解。
蒟蒻的經驗暫時還不足呢qwq，不過也随便談談吧。
首先，根據資料範圍和精度要求，可以基本确定EPS的大小了，不過也需要嘗試手動微調。
比較麻煩的是溫度和變動率。首先不必顧慮，都開大一點，先把最優解跑出來。
然後，手動二分吧，注意每個二分的值要多跑幾遍，因為模拟退火有偶然性，一次跑出最優解不代表大部分時候都能。
不過因為有兩個量，還不能直接二分，應該二分套二分比較合适
update:考試的時候寫提答，總結了一種方法：觀察法
一邊退火一邊輸出目前的溫度、解等資訊，通過觀察大緻感受一下解的降低速率
一般來說，如果解的降低速率比較均勻，跑出來的最優解也就好一些
不均勻的話，就調整參數，将解的降低速率較快的時間段的\(\Delta T\)變大一點，速率就能減慢一點。反之同理。
題目
洛谷P1337 【[JSOI2004]平衡點 / 吊打XXX】
模拟退火并不是正解，不過是一道入手好題，因為各部分實作都很友善
題解
更新中！
轉載于:https://www.cnblogs.com/flashhu/p/8884132.html