模拟退火
解决问题——数值计算
一般解决步骤
多元方程:
\[\begin {cases} {f_{1L}}(x)={f_{1R}}(x)\\ {f_{2L}}(x)={f_{2R}}(x)\\ \ \ \ \ \ \ \ \ \dots\dots\\ {f_{nL}}(x)={f_{nR}}(x)\\ \end {cases} \]评价函数:
\[\Huge {\rm{A = }}\sum\limits_{i = 1}^n {} \frac{{{{({f_{iL}}(x) - {f_{iR}}(x))}^2}}}{{{f_{iL}}{{(x)}^2} + {f_{iR}}{{(x)}^2}}} \]结束标识
当 \(A<\Large\epsilon\)，其中\(\epsilon\)是一个极小的数字可以是
1e-7左右。
或者
当逼近程序运行次数\(\large n\small> N\)时(\(N\)取一个极大的数字)
原理
模拟退火主要想要解决的是，在一些方程组中无法求得各元的解析解时，可以通过不断逼近的方法求得数值解。但是在使用逼近法计算评价函数的时候，可能会陷入局部最优解的困局，而模拟退火算法就可以以概率P跳出局部最优解，达到最优解。
重要变量
非优接受概率P——解决局部最优解问题
非优接受概率是指，当随机设立的增量(\(\Delta x)\)加上当前状态(\(x\))，即\(x+\Delta x\)带入的评价函数算出的评价值\(A\)变小了，但是不采纳该次x的概率。
即 有 \(x+\Delta x\) 满足较优解时，
则取
其中\(p\)就是非优接受概率,\(P\)为\([0,1]\)内随机数。
步长缩小量——解决逼近程度过小问题
步长缩小量是指增量\(\Delta x(Step)\)的大小变化，\(\Delta x\)的变化可以选取以下两种形式:
1.指数型缩小 \(\Large\rightarrow\) 每次选取的 \(\Delta x_{i+1}=0.9\Delta x_{i}\);
2.分数型缩小 \(\Large\rightarrow\) \(s=\frac{\Large s_{\tiny 0}}{\Large t}\) \(s_0\)是指初始步长(\(\Delta x_0\))，\(t\)为迭代次数(\(n\));
样题
题目——A Star not a Tree?（**模拟退火）
Description
Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allow you to connect any number of computers together in a linear arrangement. Luke is particulary proud that he solved a nasty NP-complete problem in order to minimize the total cable length.
Unfortunately, Luke cannot use his existing cabling. The 100mbs system uses 100baseT (twisted pair) cables. Each 100baseT cable connects only two devices: either two network cards or a network card and a hub. (A hub is an electronic device that interconnects several cables.) Luke has a choice: He can buy 2N-2 network cards and connect his N computers together by inserting one or more cards into each computer and connecting them all together. Or he can buy N network cards and a hub and connect each of his N computers to the hub. The first approach would require that Luke configure his operating system to forward network traffic. However, with the installation of Winux 2007.2, Luke discovered that network forwarding no longer worked. He couldn't figure out how to re-enable forwarding, and he had never heard of Prim or Kruskal, so he settled on the second approach: N network cards and a hub.
Luke lives in a loft and so is prepared to run the cables and place the hub anywhere. But he won't move his computers. He wants to minimize the total length of cable he must buy.
输入
The first line of input contains a positive integer N <= 100, the number of computers. N lines follow; each gives the (x,y) coordinates (in mm.) of a computer within the room. All coordinates are integers between 0 and 10,000.
输出
Output consists of one number, the total length of the cable segments, rounded to the nearest mm.
| Sample Input | Sample Output |
|---|---|
| 4 | 28284 |
| 0 0 | |
| 0 10000 | |
| 10000 10000 | |
| 10000 0 |
样码
点击查看代码
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
const double PI = acos(-1.0);
int n;
double x[110], y[110];
double dist(double cx, double cy) {//目标函数
double r = 0.0;
for (int i = 0; i < n; i++)
r += sqrt((cx-x[i]) * (cx-x[i]) + (cy-y[i]) * (cy-y[i]));
return r;
}
int main() {
double tx, ty, r, dx, dy, step, s0, P;
double a, b, c, d;
int t = 0;
scanf("%d", &n);
a = c = 1e9;
b = d = 0;
for (int i = 0; i < n; i++) { // 输入, 同时确定包围盒[a,b]*[c,d]
scanf("%lf%lf", &x[i], &y[i]);
if (x[i] < a)
a = x[i];
if (x[i] > b)
b = x[i];
if (y[i] < c)
c = y[i];
if (y[i] > d)
d = y[i];
}
srand(100);
s0 = (b - a > d - c ? b - a : d - c);
step = s0;
tx = (a + b) / 2;
ty = (c + d) / 2;
r = dist(tx, ty);
while (step > 1e-3 && t < 1000) {
double theta = (rand() / 32768.0) * PI * 2; // 选随机方向(角度)
dx = step * cos(theta);
dy = step * sin(theta);
double r1 = dist(tx + dx, ty + dy);//位移向量
P = 0.05; // 非优接受概率0.02~0.07
if (r1 < r || (rand() / 32768.0) < P) {
r = r1;
tx += dx, ty += dy;
}
step *= 0.95; // 指数型缩小
// step = s0 / (1 + t); // 倒数型缩小
t++;
}
printf("%d\n", (int)(r + 0.5));
return 0;
}
//rand()/32768.0—[0,1]随机浮点数