別著急，干貨在最后面！！！
（本文用c++實作，可以在評論區討論，后面還有情況的話還會更新，有問題歡迎指正哦~）
可以在右上角看目錄，左下角點歌哦（不行的話重繪一下就好了~）
很多人都學過貪心，但是貪心在一些情況并不適用，比如：
已知我們從黃色出發，找最小值，
貪心策略當然是一直往函式大小減小的地方偏移——但是，萬一不是單谷呢？我們會陷入如圖的藍色中無法自拔，
肯能你會想到：隨機找一個點出發，然后貪心找最小值？多隨機幾遍，然后求全域最小值？
你會發現復雜度暴增！！！！！！！！——所以如何處理這種問題呢？
模擬退火：啊，對對對~
是的！模擬退火就是一種類似于隨機化貪心的一個演算法，在OI界也小有名氣（冥器）！（如題[NOIP2021] 方差 ）
原理圖：
如圖：在物理應用中分子排布可能是紊亂的，如果我們將它升溫然后緩慢降溫，就可以生成完美的晶形！
而對于我們求解的：
怎么形象描述它呢？
一個有自己一定卡路里的人爬山，他想翻山找遠方的草藥給自己心愛的妻子，但是他并不知道山的那頭是什么，所以他會在卡路里多的時候盡量去遠方探險，但是每次會花費他的卡路里以至于他后面不能翻過太高的山丘，而且他的背包蠻大的，裝填著無數愛的草藥而芳香四溢，
所以我們立刻（啊，對對對~）能設定模擬退火的引數：
1.初始溫度 T （1000-7000）
2.末尾溫度 P（1e-6~1e-15）
3.降溫系數 K (0.91~0.9975)
4.狀態空間（被降溫物體） S
5.當前能量 E ( new )
6.全域能量 E （ old ）
一：Metropolis準則
以概率接受新狀態：
這就是物理（化學）方面類似的推論——一定概率的更新，
什么意思呢？
我們已知：當前能量 E ( new ) ， 全域能量 E （ old ），那么我們的目標是什么，不就是減少目前的能量嗎？
所以：當當前能量少于全域能量（即更新前的能量），那么我們有概率為 1 的更新概率；
當當前能量大于全域能量（即更新前的能量），那么我們有概率為 exp（ - (E( new )-E( old ))/T） 的更新概率 ( T為當前溫度) [exp(x)函式：e的x次方的函式 如 exp(1)表示e的1次方=e=2.718281828… exp(0)表示e的0次方=1 exp(2)表示e的平方=7.3890561… e是一個常數，等于2.718281828…]；
注意：有時候也不一定以以上方式更新，這只是比較妥的做法，概率方面是可以自己定的，但是一定以當前能量與全域能量的關系來設定的，（除非直接暴力的隨機演算法）
二：生成新溫度
那么怎么生成新的當前溫度呢？，以生成小數為例：
當前將更新溫度=全域溫度+(rand()*2-RAND_MAX)*t; if(不在狀態空間內){ 當前將更新溫度=fmod(當前將更新溫度,狀態空間大小) }
即：在當前狀態的鄰域結構內以一定概率方式（均勻分布、正態分布、指數分布等）產生，
三：溫度更新函式
若固定每一溫度，演算法均計算至平穩分布，然后下降溫度，則稱為時齊演算法；
若無需各溫度下演算法均達到平穩分布，但溫度需按一定速率下降，則稱為非時齊演算法，
本人用的：
T*=K;
四：外回圈終止準則
本人使用的：
(t>1e-15)//可以改大一點
其他常用方法：
（1）設定終止溫度的閾值，
（2）設定外回圈迭代次數，
（3）演算法搜索到的最優值連續若干步保持不變，
（4）概率分析方法，
五：實作流程圖：
六：關于其他類似演算法的優缺點比較和模擬退火的應用場景（做題）
遺傳演算法：其優點是能很好地處理約束，跳出區域最優，最終得到全域最優解，缺點是收斂速度慢，區域搜索能力弱，運行時間長，容易受到引數的影響，
模擬退火：具有區域搜索能力強、運行時間短的優點，缺點是全域搜索能力差，容易受到引數的影響，
爬山演算法：顯然爬山演算法簡單、效率高，但在處理多約束大規模問題時，往往不能得到較好的解決方案，
應用場景：求最優解且不能直接貪心也不知道怎么做的時候
七：退火口訣：
初始溫度小心設(1000-3000)，又粗又大wa一臉
多次sa更保險，忘了卡時直接T[if((double)clock()/CLOCKS_PER_SEC>=0.993)]（七遍模擬退火也行）
退火系數大膽設，不過0.9975會很厄
全域、狀態不一樣，全域必須菊部優
百年騙分一場空，不開srand見祖宗
退火需謹慎，退火不規范，靈封兩行淚
然后是[NOIP2021]方差的實作（玄學萬歲）：
#include <bits/stdc++.h> using namespace std; #define LL long long const int N=1e5+10; const double dw=0.9975; int a[N],n,c[N]; long long ans; bool cmp(int a,int b){ return a>b; } LL en(){ LL em=0; LL ranss=0; for(int i=2;i<=n;i++){ a[i]=a[i-1]+c[i]; } for(int i=1;i<=n;i++){ em+=(long long)a[i]*a[i]; }em=(long long)em*n; for(int i=1;i<=n;i++){ ranss=(long long)ranss+a[i]; }ranss=(long long)ranss*ranss; return (long long)(em-ranss); } void sa(){ double t=1000; while(t>1e-15){ if((double)clock()/CLOCKS_PER_SEC>=0.993){ cout<<ans; exit(0); } int x=rand()%(n-1)+2,y=rand()%(n-1)+2; while(x==y)x=rand()%(n-1)+2; swap(c[x],c[y]); LL m=en(),dt=ans-m; if(dt>0){ ans=m; }else if((double)rand()>=(double)RAND_MAX*(double)exp((double)dt/t)){ swap(c[x],c[y]); } t*=dw; } } int main(){ srand((unsigned)time(0)); cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); c[i]=a[i]-a[i-1]; } sort(c+2,c+n/2+1,cmp); sort(c+n/2+1,c+n+1); ans=en(); while(1)sa(); }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421335.html
標籤：其他
上一篇：寒假集訓一補題與題解