随机增量算法

‘壹’ 算法艺术与信息学竞赛的图书目录

第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)上述各方法的综合应用。