## 一. 爬山算法 ( Hill Climbing )
???????? 介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡單的貪心搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
???????? 爬山算法實現很簡單，其主要缺點是會陷入局部最優解，而不一定能搜索到全局最優解。如圖1所示：假設C點為當前解，爬山算法搜索到A點這個局部最優解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優的解。
圖1
?
?這題是poj2420，原作者認為是模擬退火，但是并不具備模擬退火的概率事件特點，因此我認為是爬山算法，并借此加入
~~~
<span style="font-size:18px;">#include <iostream>
#include <cmath>
using namespace std;
struct point
{
double x,y;
}p[105];
int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
double getdis(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double allDis(int n , point f)
{
double sum = 0;
for(int i = 0 ; i < n ; i++)
sum += getdis(p[i],f);
return sum;
}
point fermat(int n)
{
double step = 0;
for (int i = 0 ; i < n ; i++)
step += fabs(p[i].x) + fabs(p[i].y);
point f;
f.x = 0;
f.y = 0;
for (int i = 0 ; i < n ; i++)
f.x += p[i].x , f.y +=p[i].y;
f.x /= n;
f.y /= n;
point t;
while(step > 1e-10)
{
for (int i = 0 ; i < 8 ; i++)
{
t.x = f.x + dir[i][0]*step;
t.y = f.y + dir[i][1]*step;
if(allDis(n,t) < allDis(n,f))
f = t;
}
step *=0.7; //步長改動
}
return f;
}
int main(void)
{
int n;
while (cin >> n)
{
for(int i=0; i<n; i++)
cin >> p[i].x >> p[i].y;
double ans = allDis(n, fermat(n));
int t = ans*10;
if (t%10 < 5)
cout << t/10 << endl;
else
cout << t/10+1 << endl;
}
return 0;
}</span>
~~~
## 二. 模擬退火(SA,Simulated Annealing)思想
???????? 爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個當前最優解，因此只能搜索到局部的最優值。模擬退火其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優解，達到全局的最優解。以圖1為例，模擬退火算法在搜索到局部最優解A后，會以一定的概率接受到E的移動。也許經過幾次這樣的不是局部最優的移動后會到達D點，于是就跳出了局部最大值A。
???????? 模擬退火算法描述：
???????? 若J( Y(i+1) )>= J( Y(i) ) ?(即移動后得到更優解)，則總是接受該移動
???????? 若J( Y(i+1) )< J( Y(i) ) ?(即移動后的解比當前解要差)，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低（逐漸降低才能趨向穩定）
這里的“一定的概率”的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。
根據熱力學的原理，在溫度為T時，出現能量差為dE的降溫的概率為P(dE)，表示為：
P(dE) = exp( dE/(kT) )
其中k是一個常數，exp表示自然指數，且dE<0。這條公式說白了就是：溫度越高，出現一次能量差為dE的降溫的概率就越大；溫度越低，則出現降溫的概率就越小。又由于dE總是小于0（否則就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函數取值范圍是(0,1) 。
隨著溫度T的降低，P(dE)會逐漸降低。
我們將一次向較差解的移動看做一次溫度跳變過程，我們以概率P(dE)來接受這樣的移動。
關于爬山算法與模擬退火，有一個有趣的比喻：
爬山算法：兔子朝著比現在高的地方跳去。它找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優值就是全局最優值。
模擬退火：兔子喝醉了。它隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，它漸漸清醒了并朝最高方向跳去。這就是模擬退火。
?
下面給出模擬退火的偽代碼表示。
?
## 三. 模擬退火算法偽代碼
~~~
/*
* J(y)：在狀態y時的評價函數值
* Y(i)：表示當前狀態
* Y(i+1)：表示新的狀態
* r： 用于控制降溫的快慢
* T： 系統的溫度，系統初始應該要處于一個高溫的狀態
* T_min ：溫度的下限，若溫度T達到T_min，則停止搜索
*/
while( T > T_min )
{
dE = J( Y(i+1) ) - J( Y(i) ) ;
if ( dE >=0 ) //表達移動后得到更優解，則總是接受移動
Y(i+1) = Y(i) ; //接受從Y(i)到Y(i+1)的移動
else
{
// 函數exp( dE/T )的取值范圍是(0,1) ，dE/T越大，則exp( dE/T )也
if ( exp( dE/T ) > random( 0 , 1 ) )
Y(i+1) = Y(i) ; //接受從Y(i)到Y(i+1)的移動
}
T = r * T ; //降溫退火 ，0<r<1 。r越大，降溫越慢；r越小，降溫越快
/*
* 若r過大，則搜索到全局最優解的可能會較高，但搜索的過程也就較長。若r過小，則搜索的過程會很快，但最終可能會達到一個局部最優值
*/
i ++ ;
}
~~~
hdu 5017 Ellipsoid
這是我第一次接觸模擬退火，是2014年西安網絡賽的題目
當時想著用計算幾何和解析幾何做，后來學長說用模擬退火可以做
~~~
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const double EPS = 1e-9;
const double INF = 1e18;
const double dx[8] = {1.0, 1.0, 0.0, -1.0, -1.0, -1.0, 0.0, 1.0};
const double dy[8] = {0.0, 1.0, 1.0, 1.0, 0.0, -1.0, -1.0, -1.0};
double a, b, c, d, e, f;
double dis(double x, double y, double z){
return sqrt(x*x + y*y + z*z);
}
double getZ(double x, double y){
double A = c, B = d*y + e*x, C = a*x*x + b*y*y + f*x*y - 1.0;
double delta = B*B - 4.0*A*C;
if(delta < 0.0) return INF;
double z1 = (-B + sqrt(delta)) / (2.0 * A);
double z2 = (-B - sqrt(delta)) / (2.0 * A);
return z1*z1 < z2*z2 ? z1 : z2;
}
void work(){
double x = 0.0, y = 0.0, z = getZ(x, y);
double step = 0.8;
while(step > EPS){
for(int i=0; i<8; i++){
double nx = x + dx[i]*step;
double ny = y + dy[i]*step;
double nz = getZ(nx, ny);
if(nz >= INF) continue;
if(dis(nx, ny, nz) - dis(x, y, z) < 0.0){
x = nx, y = ny, z = nz;
}
}
step *= 0.99;
}
printf("%.7f\n", dis(x, y, z));
}
int main(){
while(scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f) == 6){
work();
}
return 0;
}
~~~
## 四. 使用模擬退火算法解決旅行商問題
旅行商問題 ( TSP , Traveling Salesman Problem ) ：有N個城市，要求從其中某個問題出發，唯一遍歷所有城市，再回到出發的城市，求最短的路線。
旅行商問題屬于所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時間復雜度是O(N!) 。
使用模擬退火算法可以比較快的求出TSP的一條近似最優路徑。（使用遺傳算法也是可以的，我將在下一篇文章中介紹）模擬退火解決TSP的思路：
1. 產生一條新的遍歷路徑P(i+1)，計算路徑P(i+1)的長度L( P(i+1) )
2. 若L(P(i+1)) < L(P(i))，則接受P(i+1)為新的路徑，否則以模擬退火的那個概率接受P(i+1) ，然后降溫
3. 重復步驟1，2直到滿足退出條件
產生新的遍歷路徑的方法有很多，下面列舉其中3種：
1. 隨機選擇2個節點，交換路徑中的這2個節點的順序。
2. 隨機選擇2個節點，將路徑中這2個節點間的節點順序逆轉。
3. 隨機選擇3個節點m，n，k，然后將節點m與n間的節點移位到節點k后面。
?
## 五. 算法評價
?? ? ? ?模擬退火算法是一種隨機算法，并不一定能找到全局的最優解，可以比較快的找到問題的近似最優解。?如果參數設置得當，模擬退火算法搜索效率比窮舉法要高。
