隨機增量演算法

『壹』 演算法藝術與信息學競賽的圖書目錄

第1章 演算法與數據結構 1
1.1 編程的靈魂——數據結構+演算法=程序 1
1.2 基本演算法 8
1.2.1 枚舉 8
1.2.2 貪心法 13
1.2.3 遞歸與分治法 19
1.2.4 遞推 28
1.3 數據結構（1）——入門 34
1.3.1 棧和隊列 35
1.3.2 串 44
1.3.3 樹和二叉樹 50
1.3.4 圖及其基本演算法 59
1.3.5 排序與檢索基本演算法 67
1.4 數據結構（2）——拓寬和應用舉例 79
1.4.1 並查集 80
1.4.2 堆及其變種 88
1.4.3 字典的兩種實現方式：哈希表、二叉搜索樹 96
1.4.4 兩個特殊樹結構：線段樹和Trie 107
1.5 動態規劃 113
1.5.1 動態規劃的兩種動機 113
1.5.2 常見模型的分析 122
1.5.3 若干經典問題和常見優化方法 149
1.6 狀態空間搜索 159
1.6.1 狀態空間 159
1.6.2 盲目搜索演算法 160
1.6.3 啟發式搜索演算法 168
1.6.4 博弈問題演算法 175
1.6.5 剪枝 180
*1.6.6 專題：路徑尋找問題 188
*1.6.7 約束滿足問題 192
第2章 數學方法與常見模型 203
2.1 代數方法和模型 203
2.2 數論基礎 216
2.2.1 素數和整除問題 216
2.2.2 進位制 224
2.2.3 同餘模算術 228
2.3 組合數學初步 239
2.3.1 鴿籠原理和Ramsey定理 239
2.3.2 排列組合和容斥原理 240
2.3.3 群論與Pólya定理 245
2.3.4 遞推關系與生成函數 254
2.3.5 離散變換與反演 262
2.4 圖論基本知識和演算法 268
2.4.1 基本概念和定理 268
2.4.2 可行遍性問題簡介 272
2.4.3 平面圖 280
2.4.4 圖的基本演算法與應用舉例 285
2.5 圖論基本演算法 299
2.5.1 生成樹問題 299
2.5.2 最短路問題 304
2.5.3 網路流問題 315
2.5.4 二分圖相關問題和模型 329
第3章 計算幾何初步 346
3.1 位置和方向的世界——計算幾何的基本問題 346
3.1.1 從相交到左右——基本問題的轉化 348
3.1.2 左右和前後——叉積和點積 350
3.2 多邊形和多面體的相關問題 361
3.2.1 衛兵問題——多邊形和多面體的概念 361
3.2.2 求多邊形、多面體的容積和重心；高維情形 367
3.2.3 判點在形內形外形上；多面體的情形 378
3.3 打包裹與製造合金——凸包及其應用 387
3.3.1 凸包的普遍性和廣泛應用性；凸的定義與優美性質 387
3.3.2 凸包的實現 391
3.3.3 凸包演算法正確性與時間效率 396
3.3.4 應用舉例 401
3.3.5 凸多邊形的深入討論 405
3.4 幾種常用的特殊演算法 410
3.4.1 蛋糕被切成幾塊？——離散化法 410
3.4.2 切蛋糕的周長和面積——掃除法 412
3.4.3 凸包與快速排序——分治法 414
3.4.4 凸包的又一種求法——增量法 416
3.4.5 專題——隨機增量演算法 417
參考文獻 424

『貳』 常見演算法有哪些

模擬
擬陣
暴力
貪心
二分法
整體二
三分法
一般動規與遞推
斯坦納樹
動態樹分治
2-SAT
並查集
差分約束
最短路
最小割
費用流
最大流
有上下界網路流
虛樹
矩陣樹定理
最小生成樹
點分治
樹鏈剖分
prufer編碼
哈夫曼樹
拉格朗日乘數法
BSGS
博弈論
矩陣乘法
高斯消元
容斥原理
抽屜原理
模線性方程組
莫比烏斯反演
快速傅里葉變換
擴展歐幾里得演算法(
裴蜀定理
dfs序
深度搜索
迭代深搜
廣度搜索
雙向廣搜
啟發式搜索
dancing link
迴文自動機
KMP
字典樹
後綴數組
AC自動機
後綴自動機
manacher
凸包
掃描線
三角剖分
旋轉卡殼
半平面交
cdq分治
莫隊演算法
爬山演算法
分數規劃
模擬退火
朱劉演算法
隨機增量法
倍增演算法

『叄』 演算法的四種描述方法是什麼

#include<stdio.h>
#include<time.h>
#include<math.h>
#include<malloc.h>

void BubbleSort(int *L,int N)
{ //冒泡
int i,j;
int t;

for(i=1;i<=N;i++)
{
for(j=N;j>i;j--)
if(L[j]<L[j-1])
{
t=L[j];
L[j]=L[j-1];
L[j-1]=t;
}
}
}

int SelectMinKey(int *L,int N,int n)
{
int i,min=n;

for(i=n+1;i<=N;i++)
if(L[i]<L[min])
min=i;

return min;
}

void SelectSort(int *L,int N)
{ //選擇
int i,j;
int t;

for(i=1;i<N;i++)
{
j=SelectMinKey(L,N,i);
if(i!=j)
{
t=L[i];
L[i]=L[j];
L[j]=t;
}
}
}

void InsertSort(int *L,int N)
{ //插入
int i,j;

for(i=2;i<=N;i++)
{
if(L[i]<L[i-1])
{
L[0]=L[i];
L[i]=L[i-1];
for(j=i-2;L[0]<L[j];j--)
L[j+1]=L[j];
L[j+1]=L[0];
}
}
}

void ShellInsert(int *L,int N, int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法對演算法10.1作了以下修改：
// 1. 前後記錄位置的增量是dk，而不是1；
// 2. r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。
int i,j;
for(i=dk+1;i<=N;++i)
if(L[i]<L[i-dk])
{ // 需將L.r[i]插入有序增量子表
L[0]=L[i]; // 暫存在L.r[0]
for(j=i-dk;(j>0&&L[0]<L[j]);j-=dk)
L[j+dk]=L[j]; // 記錄後移，查找插入位置
L[j+dk]=L[0]; // 插入
}
} // ShellInsert

void ShellSt(int *L,int N, int dlta[], int t)
{ // 演算法10.5
// 按增量序列dlta[0..t-1]對順序表L作希爾排序。
for(int k=0;k<t;++k)
ShellInsert(L,N, dlta[k]); // 一趟增量為dlta[k]的插入排序
} // ShellSort

void ShellSort(int *L,int N)
{ //希爾
int t=(int)log(N);
int k,*dlta;

dlta=(int*)malloc(t*4); //產生增量序列
for(k=0;k<t;k++)
dlta[k]=(int)pow(2,t-k)-1;

ShellSt(L,N,dlta,t);
}

int main()
{
int N=250;
int i,j,k;
int t;
int ti[16];
int *L;

srand(time(NULL));

printf("長度\t|冒泡\t|選擇\t|插入\t|希爾\n");
printf("--------+-------------------------------------------------------------");
for(j=0;N<100000;j++)
{
L=(int *)malloc((N+1)*4);

t=0;

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
BubbleSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
SelectSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
InsertSort(L,N);
ti[t++]=clock();

for(i=1;i<=N;i++)
L[i]=rand();
ti[t++]=clock();
ShellSort(L,N);
ti[t++]=clock();

printf("\n%d\t",N);
for(k=0;k<4;k++)
printf("| %d\t",(ti[2*k+1]-ti[2*k]));

N*=5;
}
printf("\n\n");
}

//這是我們當年學數據結構時我自己寫的，給你改了一下，輸出是對隨機產生一些數，對四種演算法進行比較，有問題可以hi我啊
另外,站長團上有產品團購,便宜有保證

『肆』 數值隨機化演算法求非線性方程組

參見博文：http://blog.csdn.net/liufeng_king/article/details/9029091
//隨機化演算法 解線性方程組
#include "stdafx.h"
#include "RandomNumber.h"
#include <iostream>
using namespace std;

bool NonLinear(double *x0,double *dx0,double *x,double a0,
double epsilon,double k,int n,int Steps,int M);
double f(double *x,int n);

int main()
{
double *x0, //根初值
*x, //根
*dx0, //增量初值
a0 = 0.0001, //步長
epsilon = 0.01, //精度
k = 1.1; //步長變參
int n = 2, //方程個數
Steps = 10000, //執行次數
M = 1000; //失敗次數

x0 = new double[n+1];
dx0 = new double[n+1];
x = new double[n+1];

//根初值
x0[1] = 0.0;
x0[2] = 0.0;

//增量初值
dx0[1] = 0.01;
dx0[2] = 0.01;

cout<<"原方程組為："<<endl;
cout<<"x1-x2=1"<<endl;
cout<<"x1+x2=3"<<endl;

cout<<"此方程租的根為："<<endl;

bool flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);
while(!flag)
{
flag = NonLinear(x0,dx0,x,a0,epsilon,k,n,Steps,M);
}
for(int i=1; i<=n; i++)
{
cout<<"x"<<i<<"="<<x[i]<<" ";
}
cout<<endl;

return 0;
}

//解非線性方程組的隨機化演算法
bool NonLinear(double *x0,double *dx0,double *x,double a0,
double epsilon,double k,int n,int Steps,int M)
{
static RandomNumber rnd;
bool success; //搜索成功標志
double *dx,*r;

dx = new double[n+1]; //步進增量向量
r = new double[n+1]; //搜索方向向量
int mm = 0; //當前搜索失敗次數
int j = 0; //迭代次數
double a = a0; //步長因子

for(int i=1; i<=n; i++)
{
x[i] = x0[i];
dx[i] = dx0[i];
}

double fx = f(x,n); //計算目標函數值
double min = fx; //當前最優值

while(j<Steps)
{
//(1)計算隨機搜索步長
if(fx<min)//搜索成功
{
min = fx;
a *= k;
success = true;
}
else//搜索失敗
{
mm++;
if(mm>M)
{
a /= k;
}
success = false;
}

if(min<epsilon)
{
break;
}

//(2)計算隨機搜索方向和增量
for(int i=1; i<=n; i++)
{
r[i] = 2.0 * rnd.fRandom()-1;
}

if(success)
{
for(int i=1; i<=n; i++)
{
dx[i] = a * r[i];
}
}
else
{
for(int i=1; i<=n; i++)
{
dx[i] = a * r[i] - dx[i];
}
}

//(3)計算隨機搜索點
for(int i=1; i<=n; i++)
{
x[i] += dx[i];
}

//(4)計算目標函數值
fx = f(x,n);
j++;
}

if(fx<=epsilon)
{
return true;
}
else
{
return false;
}
}

double f(double *x,int n)
{
return (x[1]-x[2]-1)*(x[1]-x[2]-1)
+(x[1]+x[2]-3)*(x[1]+x[2]-3);
}

『伍』 計算增量自相關參數設置

自相關矩陣是只與時間增量有關的函數，則隨機過程為嚴平穩隨機過程。直觀點描述滿足R（t，t+a）=E[x(t)x(t+a)]=f(a)的隨機過程x（t）為嚴平穩隨機過程。同時，嚴平穩隨機過程的協方差矩陣也滿足該特性。同時略微注意下，自相關矩陣和協方差矩陣的這兩個條件都是充要條件。如果要度量平穩性並且給出和自相關矩陣的關系應該不是很簡單的課題，建議您查找一下這個方向的文獻。

『陸』 證明演算法：隨機快排比確定性快排的時間代價低 是證明不是代碼

一般來說是相同的時間復雜度O(nlogn)
但是我們知道確定性快排存在最差復雜度(已經排序完成的數列)O(n^2)，以及從最優復雜度
到最差復雜度的漸變
同時如果是隨機快排完全不存在這種情況，理論復雜度是穩定的O(nlogn)
隨機化應用有很廣泛的應用。比方說隨機增量法做的各種演算法，都是為了優化特例的極端最差復雜度而出現的。因此是比確定的演算法要快

『柒』 Delaunay triangulation 分治演算法

隨機增量法較為簡單，遵循增量法的一貫思路，即按照隨機的順序依次插入點集中的點，在整個過程中都要 維護並更新一個與當前點集對應的Delaunay三角剖分。考慮插入vi點的情況，由於前面插入所有的點v1,v2,...,vi-1構成的DT(v1, v2,...,vi-1)已經是Delaunay三角剖分，只需要考慮插入vi點後引起的變化，並作調整使得DT(v1,v2,...,vi-1) U vi成為新的Delaunay三角剖分DT(v1,v2,...,vi)。
(插入調整過程：首先確定vi落在哪個三角形中（或邊上），然後將vi與三角形三個頂點連接起來構成三個三角形（或與共邊的兩個三角形的對頂點連接起來構 成四個三角形），由於新生成的邊以及原來的邊可能不是或不再是Delaunay邊，故進行邊翻轉來調整使之都成為Delaunay邊，從而得出DT (v1,v2,...,vi)。)

其Pseudocode如下：

Algorithm IncrementalDelaunay(V)
Input: 由n個點組成的二維點集V
Output: Delaunay三角剖分DT
1.add a appropriate triangle boudingbox to contain V ( such as: we can use triangle abc, a=(0, 3M), b=(-3M,-3M), c=(3M, 0), M=Max({|x1|,|x2|,|x3|,...} U {|y1|,|y2|,|y3|,...}))
2.initialize DT(a,b,c) as triangle abc
3.for i <- 1 to n
do (Insert(DT(a,b,c,v1,v2,...,vi-1), vi))
4.remove the boundingbox and relative triangle which cotains any vertex of triangle abc from DT(a,b,c,v1,v2,...,vn) and return DT(v1,v2,...,vn).

Algorithm Insert(DT(a,b,c,v1,v2,...,vi-1), vi)
1.find the triangle vavbvc which contains vi // FindTriangle()
2.if (vi located at the interior of vavbvc)
3. then add triangle vavbvi, vbvcvi and vcvavi into DT // UpdateDT()
FlipTest(DT, va, vb, vi)
FlipTest(DT, vb, vc, vi)
FlipTest(DT, vc, va, vi)
4.else if (vi located at one edge (E.g. edge vavb) of vavbvc)
5. then add triangle vavivc, vivbvc, vavdvi and vivdvb into DT (here, d is the third vertex of triangle which contains edge vavb) // UpdateDT()
FlipTest(DT, va, vd, vi)
FlipTest(DT, vc, va, vi)
FlipTest(DT, vd, vb, vi)
FlipTest(DT, vb, vc, vi)
6.return DT(a,b,c,v1,v2,...,vi)

Algorithm FlipTest(DT(a,b,c,v1,v2,...,vi), va, vb, vi)
1.find the third vertex (vd) of triangle which contains edge vavb // FindThirdVertex()
2.if(vi is in circumcircle of abd) // InCircle()
3. then remove edge vavb, add new edge vivd into DT // UpdateDT()
FlipTest(DT, va, vd, vi)
FlipTest(DT, vd, vb, vi)

復雜度分析

問題的規模為點集中的點的總個數n（沒有重合的點），循環內的基本的操作有：
1.尋找插入點所在的三角形(FindTriangle())
2.測試點是否在外接圓內(InCircle())
3.更新三角網(UpdateDT())
4.尋找共測試邊的第三頂點(FindThirdVertex())

考慮最壞情況：

時間復雜度T ＝ T(addboudingbox()) + Sum(T(insert(i), i=1,2,...,n)) + T(removeboundingbox)
因為addboudingbox()和removeboundingbox不隨n變化，是個常量。T(addboudingbox()) = O(1), T(removeboundingbox()) = O(1).

T = Sum(T(insert(i), i=1,2,...,n)) + O(1) + O(1).

考慮插入第i個的點的時間:
T(insert(i)) = T(FindTriangle(i)) + T(UpdateDT(i)) + K*T(FlipTest(i)) (K為常數)

故T = Sum(T(FindTriangle(i)), i=1,2,..,n) + Sum(T(UpdateTD(i)), i=1,2,..,n) + K*Sum(T(FlipTest(i)), i=1,2,..,n)

挨個考慮：
FindTriangle(i)是要找出包含第i個點的三角形，由歐拉公式知道，平面圖的面數F是O(n), n為頂點數，故此時總的三角形數是O(i)的。所以問題相當於在O(i)個記錄中查找目標記錄，如果不藉助特殊的數據結構，按照一般順序查找，需要O (i)的時間。
T(FindTriangle(i)) = O(i),故：Sum(T(FindTriangle(i)), i=1,2,..,n) = O(n*n)

UpdateTD(i)是更新三角網數據結構，插入和刪除三角形到當前的三角網是個常量操作，因為已經知道插入和刪除的位置。
T(UpdateDT(i)) = O(1),故：Sum(T(UpdateTD(i)), i=1,2,..,n) = O(n)

FlipTest(i)比較復雜些，是個遞歸過程。細分為：T(FlipTest(i)) = T(FindThirdVertex(i)) + T(InCircle(i)) + T(UpdateDT(i)) + 2*T(FlipTest(j))。(這里，用j來區分不同的深度)
因為InCircle(i)是測試點是否在外接圓內，是個常量操作，不隨點數變化而變化。故T(InCircle(i)) = O(1), 又T(UpdateDT(i) = O(1)(見上)
FindThirdVertex(i)是查找目標點，在O(i)個記錄中查找目標記錄，如果不藉助特殊的數據結構，按照一般順序查找需要O(i)的時間。T(FindThirdVertex(i)) = O(i).
剩下的是遞歸調用FlipTest的過程，不過還好，因為FlipTest的遞歸深度只有常數級(設為K)。正比於點在三角網中的度數(degree)。故FlipTest(i)最多調用的次數為2*2*,...,2 = K',還是常數。
故T(FlipTest(i)) = O(i) + O(1) + O(1) + K'*(O(i) + O(1) + O(1)) = O(i) + O(1) + O(1) .
Sum(T(FlipTest(i)), i=1,2,..,n) = O(n*n) + O(n) + O(n)

綜上，最壞情況下演算法總時間復雜度 T = O(n*n) + O(n) + K*(O(n*n) + O(n) + O(n)) + O(1) + O(1) = O(n*n)
其中，關鍵的操作是FindTriangle()和FindThirdVertex()，都是n*n次的。

在網上很多資料說隨機增量法是O(nlogn)的，但是分析下來，卻是O(n*n)的。後來看到別人的實 現，原來是用的別的數據結構來存儲三角網，減少了FindTriangle()和FindThirdVertex()的復雜度。使得某次查找三角形和共邊 三角形的第三頂點能在O(logn)，而非O(n)的時間內實現。這樣，總的查找的時間為 O(log1)+O(log2)+,...+O(logn) = O(nlogn)。程序=演算法+數據結構，看來一點沒錯。
比如說用DAG，Quad-edge等，都能達到O(nlogn)的復雜度。

分治法（Divide and Conquer）

據說是現在實際表現最好的。

『捌』 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入：

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中

（1）用大根堆排序的基本思想

先將初始數組建成一個大根堆，此對為初始的無序區；

再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；

由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；

..........

直到無序區只有一個元素為止；

4.4：應用

尋找M個數中的前K個最小的數並保持有序；

時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

（1）基本思想

先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；

（2）適用場景

比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；

6.歸並排序

（1）基本思想

首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；

（2）適用場景

若n較大，並且要求排序穩定，則可以選擇歸並排序；

7.簡單選擇排序

（1）基本思想

第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；

第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；

...........

第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；

以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；

『玖』 如何根據這個公式算遞增求和如,已知:K=A*3.14+2A為任意數字求:n∑ ...

兄台,你的增量是什麼?當A取定某個值後就是定值,通項也不含有增量,例如i如果你是一種統計的觀點來計算,那就不能使用公式來求和了.公式求和是有規律的表達式總結出來的求和公式,而你這個因為A完全是隨機的,所以Ki也是隨機的.不具有任何規律（不過從理論上來說是正態分布的,但那樣的計算沒有什麼意義.抽樣是部分的.全部計算就不是抽樣了）所以.綜合考慮,還是直接計算吧.道標了抽樣,也反映了統計的觀點.事實上也沒有公式可計算!

『拾』 C語言中退火模擬

模擬退火法 模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis准則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制參數初值t開始，對當前解重復「產生新解→計算目標函數差→ 接受或舍棄」的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schele)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。

退火演算法
Simulate Anneal Arithmetic (SAA,模擬退火演算法) 模擬退火演算法 模擬退火演算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis准則，粒子在溫度T時趨於平衡的概率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火演算法：由初始解i和控制參數初值t開始，對當前解重復「產生新解→計算目標函數差→接受或舍棄」的迭代，並逐步衰減t值，演算法終止時的當前解即為所得近似最優解，這是基於蒙特卡羅迭代求解法的一種啟發式隨機搜索過程。退火過程由冷卻進度表(Cooling Schele)控制，包括控制參數的初值t及其衰減因子Δt、每個t值時的迭代次數L和停止條件S。 模擬退火演算法起源於物理退火。 􀂄物理退火過程： （1） 加溫過程 （2） 等溫過程 （3） 冷卻過程 1 . 模擬退火演算法的模型 模擬退火演算法可以分解為解空間、目標函數和初始解三部分。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態S(是演算法迭代的起點)， 每個T值的迭代次數L (2) 對k=1，……，L做第(3)至第6步： (3) 產生新解S′ (4) 計算增量Δt′=C(S′)-C(S)，其中C(S)為評價函數 (5) 若Δt′<0則接受S′作為新的當前解，否則以概率exp(-Δt′/T)接受S′作為新的當前解. (6) 如果滿足終止條件則輸出當前解作為最優解，結束程序。 終止條件通常取為連續若干個新解都沒有被接受時終止演算法。 (7) T逐漸減少，且T->0，然後轉第2步。 演算法對應動態演示圖： 模擬退火演算法新解的產生和接受可分為如下四個步驟： 第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。 第三步是判斷新解是否被接受,判斷的依據是一個接受准則，最常用的接受准則是Metropo1is准則: 若Δt′<0則接受S′作為新的當前解S，否則以概率exp(-Δt′/T)接受S′作為新的當前解S。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。 模擬退火演算法與初始值無關，演算法求得的解與初始解狀態S(是演算法迭代的起點)無關；模擬退火演算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂於全局最優解的全局優化演算法；模擬退火演算法具有並行性。 2 模擬退火演算法的簡單應用 作為模擬退火演算法應用，討論貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。 求解TSP的模擬退火演算法模型可描述如下： 解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1，……，n}的所有循環排列的集合，S中的成員記為(w1,w2 ,……，wn)，並記wn+1= w1。初始解可選為(1，……，n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數： 我們要求此代價函數的最小值。 新解的產生 隨機產生1和n之間的兩相異數k和m，若k (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變為： (w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn). 如果是k>m，則將 (w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn) 變為： (wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk). 上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。 也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。 代價函數差 設將(w1, w2 ,……，wn)變換為(u1, u2 ,……，un), 則代價函數差為： 根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序： Procere TSPSA: begin init-of-T; { T為初始溫度} S={1，……，n}; {S為初始值} termination=false; while termination=false begin for i=1 to L do begin generate(S′form S); { 從當前迴路S產生新迴路S′} Δt:=f(S′))-f(S);{f(S)為路徑總長} IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1]) S=S′; IF the-halt-condition-is-TRUE THEN termination=true; End; T_lower; End; End 模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 3 模擬退火演算法的參數控制問題 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點： (1) 溫度T的初始值設置問題。 溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。 (2) 退火速度問題。 模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。 (3) 溫度管理問題。 溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式： T(t+1)＝k×T(t) 式中k為正的略小於1.00的常數，t為降溫的次數 4、模擬退火演算法的優缺點 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。 缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。 經典模擬退火演算法的缺點： (1)如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢; (2)如果降溫過程過快，很可能得不到全局最優解。 􀂄 模擬退火演算法的改進 (1) 設計合適的狀態產生函數，使其根據搜索進程的需要 表現出狀態的全空間分散性或局部區域性。 (2) 設計高效的退火策略。 (3) 避免狀態的迂迴搜索。 (4) 採用並行搜索結構。 (5) 為避免陷入局部極小，改進對溫度的控制方式 (6) 選擇合適的初始狀態。 (7) 設計合適的演算法終止准則。 也可通過增加某些環節而實現對模擬退火演算法的改進。 主要的改進方式包括： (1) 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。 (2) 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。 (3) 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。 (4) 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。 (5) 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。 (6)上述各方法的綜合應用。