Simulated annealing. Elegant violence.↵
↵
~~ I think it's necessary to excerpt the blurb from the bill of lading ~~↵
↵
## Written by ZX ##↵
↵
## Preface: This piece applies to Introductory-Advanced Simulated Annealing↵
↵
**Simulated Annealing (SA)** is a **randomization** algorithm. We often use simulated annealing to solve a problem when it has a huge number of solutions (even **infinite** ones) and is not a single-peaked function.↵
↵
In general, many problems can be ~~watered through~~ with simulated annealing, known in the OI community as **[elegant violence]**↵
↵
### Getting Started with the Simulated Annealing Algorithm↵
↵
Let's summarize in one sentence (and then borrow from OIWIKI): simulated annealing = modify the answer if the solution in the new state is better, otherwise accept the new state with a certain probability↵
↵
That is, first randomize an answer, if the answer is the current optimal answer, update the optimal answer, otherwise accept the answer with a certain probability that the answer may be closer to the optimal answer.↵
↵
Here's the point: how to **randomize an answer** and **determine the probability of accepting the new state** (and make the randomized answer as close to the optimal solution as possible)↵
↵
This introduces a new concept, **Annealing**.↵
↵
Annealing = the principle of solid annealing, which refers to the cooling of a solid at a high temperature↵
↵
The implementation of simulated annealing also approximates the solid annealing principle, starting with three parameters denoting the initial temperature $T_0$, the cooling coefficient $d$, and the termination temperature $T_k$. Where $T_0$ is a relatively large number, $d$ is a number very close to 1 but less than 1, and $T_k$ is a positive number close to zero.↵
↵
The temperature T is initialized to $T_0$ and $T*=d$ each time until $T$ reaches $T_k$.↵
↵
! [](https://images.cnblogs.com/cnblogs_com/blogs/808855/galleries/2382510/o_240305135531_simulated-annealing.gif)↵
↵
~~OIwiki's diagram~~: ``` ! [](https://oi-wiki.org/misc/images/simulated-annealing.gif)``!↵
↵
Now we start solving how to **randomize an answer** and **determine the probability of accepting a new state**.↵
↵
1. randomize an answer: it varies according to the question, but it is generally randomized, but unlike simple randomization, this answer is generally randomized based on a prior solution (note that it is not necessarily the optimal solution, since there is a certain probability that we accept an answer that may be closer to the optimal answer)↵
↵
2. Determine the probability of accepting the new state: generally more fixed, commonly written as ```if (exp(-delta (randomize an answer - current optimal solution) / t (current temperature)) > (double)rand() / RAND_MAX;) accept the new state```.↵
↵
### Advanced simulated annealing algorithm↵
↵
1. About the parameters↵
↵
The parameters of simulated annealing basically determine the accuracy of the code, ** in general, the higher $T_0$ is, the lower $T_k$ is ($T_k >0$), and the closer $d$ is to $1$, the more accurate the simulated annealing is, ** but the longer it takes, so it is recommended that the parameters be stuck in the simulated annealing code.↵
↵
2. About random numbers↵
↵
The essence of simulated annealing is in the random number, the randomness of the random number, the cycle period basically determines the accuracy, the randomness is poor, the cycle period is short is likely to simulated annealing card card off, [it is recommended to refer to this to optimize the random number](https://oi-wiki.org//misc/random/)↵
↵
3. About time↵
↵
Simulated annealing is a **not very stable** algorithm ~~(who called him random)~~, a single time may not find the optimal solution, the general to run many times, there is a ```clock()``` function, return the program running time, it is recommended that in the case of **Not a timeout** run as much as possible!↵
↵
In general, it can be like this ```while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME (a parameter less than the time limit)) SA() (do simulated annealing);```↵
↵
### Examples of simulated annealing algorithms↵
↵
#### Computational geometry (basic idea: try at the current point)↵
↵
- [P1337 [JSOI2004] Equilibrium point / Hanging XXX](https://www.luogu.com.cn/problem/P1337) ↵
- [P5544 [JSOI2016]Bomb Attack 1](https://www.luogu.com.cn/problem/P5544)↵
- [P4035 [JSOI2008]Spherical Space Generator](https://www.luogu.com.cn/problem/P4035) (watch out for accuracy)↵
- [P4703 Stealing the Internet](https://www.luogu.com.cn/problem/P4703)↵
- [CF2C Commentator problem](https://www.luogu.com.cn/problem/CF2C)↵
- [P4274 [NOI2004] Little H's cabin](https://www.luogu.com.cn/problem/P4274)↵
- [SP4587 FENCE3 — Electric Fences](https://www.luogu.com.cn/problem/SP4587)↵
↵
#### Optimal Sequence (basic idea: reconstruct on current sequence)↵
↵
- [P3936 Coloring](https://www.luogu.com.cn/problem/P3936)↵
- [P2503 [HAOI2006] Mean score data](https://www.luogu.com.cn/problem/P2503)↵
- [P2538 [SCOI2008] Castle](https://www.luogu.com.cn/problem/P2538)↵
- [P3878 [TJOI2010] Score Gold](https://www.luogu.com.cn/problem/P3878)↵
- [P4966 Base building](https://www.luogu.com.cn/problem/P4966)↵
↵
#### Others (usually those with too watery data)↵
↵
- [P4360 [CEOI2004] Sawmill Siting](https://www.luogu.com.cn/problem/P4360) ↵
- [P1742 Minimum Circle Coverage](https://www.luogu.com.cn/problem/P1742) (note precision)↵
↵
### Other (references, etc.)↵
↵
[Ad 1: If you haven't studied simulated annealing, look here](https://oi-wiki.org//misc/simulated-annealing/)↵
↵
[Ad 2: If you haven't studied analog annealing, look here](https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji)↵
↵
### Update log↵
↵
2021:08:05 Correction P4360 data is overwatered and positive solution is not annealed↵
↵
### Add↵
↵
! [](https://images.cnblogs.com/cnblogs_com/blogs/808855/galleries/2382510/o_240305135531_simulated-annealing.gif)↵
↵
This figure shows the essence of simulated annealing very graphically. Look closely, there are multiple peaks in this figure, and the red line is exactly running back and forth to judge the peaks one by one.↵
↵
Let's start with the most basic simulated annealing, which is the two-dimensional plane on the moving image.↵
↵
! [](https://cdn.luogu.com.cn/upload/image_hosting/91vp28y3.png)↵
↵
As shown, this is a plot with multiple peaks, and we want to find the highest peak, the red dot.↵
↵
Then, at the beginning, we will randomize to a point (blue point), at this point it has two ways, one is to spread to both sides (respectively the direction of the arrows, whichever is bigger, this is a greedy strategy), and the other is to randomize to a point, for example, it can just instantly ~~randomly~~~ to another point (green). Between these two methods is **randomizing an answer and determining the probability of accepting the new state**. The answer is then made closer to the optimal solution.↵
↵
Annealing, is a physical term, for the process, see above:↵
↵
> First there are three parameters denoting the initial temperature $T_0$, the coefficient of cooling $d$, and the termination temperature $T_k$. where $T_0$ is a relatively large number, $d$ is a number very close to 1 but smaller than 1, and $T_k$ is a positive number close to 0. The temperature T is initialized to $T_0$, and $T*=d$ each time until $T$ reaches $T_k$.↵
↵
For specific operations, the above is also more detailed.↵
↵
The main point is that the simulated annealing application scenarios.↵
↵
There are several scenarios↵
- Geometric, distance problems↵
- Dp, greedy, in the transfer DP, or in the greedy part, use simulated annealing to solve.↵
- ~~ Messing around ~~↵
↵
The randomization trick is still some help for this :[https://oi-wiki.org//misc/random/](https://oi-wiki.org//misc/random/). I didn't really look at it in detail myself, but anyway, it's just using some tech that is not used in general for tapping, but simulated annealing is very much about randomizing evenly, uniformly.↵
↵
Like, Rocky Valley P1337, someone using tech rand, only ran the simulated annealing once, and passed, while I, also while ...... to the time limit to stop, to anneal, although passed, but it is the same code handed over many times before passing.↵
↵
# Examples↵
↵
[P1337 [JSOI2004] Equilibrium Point / Hanging XXX](https://www.luogu.com.cn/problem/P1337)↵
↵
For this question, it's a board that simulates annealing, straight up crazy annealing, and then this is equivalent to finding the peak on a two-dimensional, where all the previous demos were one-dimensional. All you need to do is for each answer, go ahead and violently calculate its contribution, and then keep simulating annealing, why can this question simulate annealing?↵
In a very large answer, his periphery can not become very small all of a sudden, at most, it will become a little smaller, and may even become larger, so only a multi-peak.↵
PS: By adjusting the parameters, adjusting the step size, to control the simulated annealing, quite interesting, ~~ like the first time I played scartch, adjusting the code parameters to change the game. ~~↵
↵
```cpp↵
↵
int n;↵
struct node{↵
double u,v,w.↵
}a[N],now;↵
double dist(double x,double y){↵
double res=0; for(int i=1;i=n;i++){↵
for(int i=1;i<=n;i++){↵
res+=sqrt((x-a[i].u)*(x-a[i].u) + (y-a[i].v))*(y-a[i].v))*a[i].w; }↵
}return res.↵
}void sa(){↵
now.u=(rand()%10000)*2-10000,now.v=(rand()%10000)*2-10000,now.w=dist(now.u,now.v); ↵
for(double T = 1000;T >= 1e-8;T *= 0.99){↵
double xx=now.u+((rand()%10000)*2-10000)*T;↵
double yy=now.v+((rand()%10000)*2-10000)*T;↵
double ww=dist(xx,yy);↵
if(ww < now.w) now={xx,yy,ww}; else if(exp(-(ww.w)))↵
else if(exp(-(ww-now.w)/T)*RAND_MAX>rand()) now={xx,yy,now.w}; ↵
}↵
}↵
void solve(){↵
cin>>n;↵
for(int i=1;i<=n;i++) cin>>a[i].u>>a[i].v>>a[i].w;↵
↵
while((double)clock()/CLOCKS_PER_SEC<0.99) sa();↵
printf("%.3lf %.3lf",now.u,now.v);↵
}↵
```↵
I use plain rand, but tech is recommended.↵
↵
↵
Translated with www.DeepL.com/Translator (free version)
↵
~~ I think it's necessary to excerpt the blurb from the bill of lading ~~↵
↵
↵
↵
**Simulated Annealing (SA)** is a **randomization** algorithm. We often use simulated annealing to solve a problem when it has a huge number of solutions (even **infinite** ones) and is not a single-peaked function.↵
↵
In general, many problems can be ~~watered through~~ with simulated annealing, known in the OI community as **[elegant violence]**↵
↵
### Getting Started with the Simulated Annealing Algorithm↵
↵
Let's summarize in one sentence (and then borrow from OIWIKI): simulated annealing = modify the answer if the solution in the new state is better, otherwise accept the new state with a certain probability↵
↵
That is, first randomize an answer, if the answer is the current optimal answer, update the optimal answer, otherwise accept the answer with a certain probability that the answer may be closer to the optimal answer.↵
↵
Here's the point: how to **randomize an answer** and **determine the probability of accepting the new state** (and make the randomized answer as close to the optimal solution as possible)↵
↵
This introduces a new concept, **Annealing**.↵
↵
Annealing = the principle of solid annealing, which refers to the cooling of a solid at a high temperature↵
↵
The implementation of simulated annealing also approximates the solid annealing principle, starting with three parameters denoting the initial temperature $T_0$, the cooling coefficient $d$, and the termination temperature $T_k$. Where $T_0$ is a relatively large number, $d$ is a number very close to 1 but less than 1, and $T_k$ is a positive number close to zero.↵
↵
The temperature T is initialized to $T_0$ and $T*=d$ each time until $T$ reaches $T_k$.↵
↵
! [](https://images.cnblogs.com/cnblogs_com/blogs/808855/galleries/2382510/o_240305135531_simulated-annealing.gif)↵
↵
~~OIwiki's diagram~~: ``` ! [](https://oi-wiki.org/misc/images/simulated-annealing.gif)``!↵
↵
Now we start solving how to **randomize an answer** and **determine the probability of accepting a new state**.↵
↵
1. randomize an answer: it varies according to the question, but it is generally randomized, but unlike simple randomization, this answer is generally randomized based on a prior solution (note that it is not necessarily the optimal solution, since there is a certain probability that we accept an answer that may be closer to the optimal answer)↵
↵
2. Determine the probability of accepting the new state: generally more fixed, commonly written as ```if (exp(-delta (randomize an answer - current optimal solution) / t (current temperature)) > (double)rand() / RAND_MAX;) accept the new state```.↵
↵
### Advanced simulated annealing algorithm↵
↵
1. About the parameters↵
↵
The parameters of simulated annealing basically determine the accuracy of the code, ** in general, the higher $T_0$ is, the lower $T_k$ is ($T_k >0$), and the closer $d$ is to $1$, the more accurate the simulated annealing is, ** but the longer it takes, so it is recommended that the parameters be stuck in the simulated annealing code.↵
↵
2. About random numbers↵
↵
The essence of simulated annealing is in the random number, the randomness of the random number, the cycle period basically determines the accuracy, the randomness is poor, the cycle period is short is likely to simulated annealing card card off, [it is recommended to refer to this to optimize the random number](https://oi-wiki.org//misc/random/)↵
↵
3. About time↵
↵
Simulated annealing is a **not very stable** algorithm ~~(who called him random)~~, a single time may not find the optimal solution, the general to run many times, there is a ```clock()``` function, return the program running time, it is recommended that in the case of **Not a timeout** run as much as possible!↵
↵
In general, it can be like this ```while ((double)clock()/CLOCKS_PER_SEC < MAX_TIME (a parameter less than the time limit)) SA() (do simulated annealing);```↵
↵
### Examples of simulated annealing algorithms↵
↵
#### Computational geometry (basic idea: try at the current point)↵
↵
- [P1337 [JSOI2004] Equilibrium point / Hanging XXX](https://www.luogu.com.cn/problem/P1337) ↵
- [P5544 [JSOI2016]Bomb Attack 1](https://www.luogu.com.cn/problem/P5544)↵
- [P4035 [JSOI2008]Spherical Space Generator](https://www.luogu.com.cn/problem/P4035) (watch out for accuracy)↵
- [P4703 Stealing the Internet](https://www.luogu.com.cn/problem/P4703)↵
- [CF2C Commentator problem](https://www.luogu.com.cn/problem/CF2C)↵
- [P4274 [NOI2004] Little H's cabin](https://www.luogu.com.cn/problem/P4274)↵
- [SP4587 FENCE3 — Electric Fences](https://www.luogu.com.cn/problem/SP4587)↵
↵
#### Optimal Sequence (basic idea: reconstruct on current sequence)↵
↵
- [P3936 Coloring](https://www.luogu.com.cn/problem/P3936)↵
- [P2503 [HAOI2006] Mean score data](https://www.luogu.com.cn/problem/P2503)↵
- [P2538 [SCOI2008] Castle](https://www.luogu.com.cn/problem/P2538)↵
- [P3878 [TJOI2010] Score Gold](https://www.luogu.com.cn/problem/P3878)↵
- [P4966 Base building](https://www.luogu.com.cn/problem/P4966)↵
↵
#### Others (usually those with too watery data)↵
↵
- [P4360 [CEOI2004] Sawmill Siting](https://www.luogu.com.cn/problem/P4360) ↵
- [P1742 Minimum Circle Coverage](https://www.luogu.com.cn/problem/P1742) (note precision)↵
↵
### Other (references, etc.)↵
↵
[Ad 1: If you haven't studied simulated annealing, look here](https://oi-wiki.org//misc/simulated-annealing/)↵
↵
[Ad 2: If you haven't studied analog annealing, look here](https://www.luogu.com.cn/blog/Darth-Che/mu-ni-tui-huo-xue-xi-bi-ji)↵
↵
### Update log↵
↵
2021:08:05 Correction P4360 data is overwatered and positive solution is not annealed↵
↵
### Add↵
↵
! [](https://images.cnblogs.com/cnblogs_com/blogs/808855/galleries/2382510/o_240305135531_simulated-annealing.gif)↵
↵
This figure shows the essence of simulated annealing very graphically. Look closely, there are multiple peaks in this figure, and the red line is exactly running back and forth to judge the peaks one by one.↵
↵
Let's start with the most basic simulated annealing, which is the two-dimensional plane on the moving image.↵
↵
! [](https://cdn.luogu.com.cn/upload/image_hosting/91vp28y3.png)↵
↵
As shown, this is a plot with multiple peaks, and we want to find the highest peak, the red dot.↵
↵
Then, at the beginning, we will randomize to a point (blue point), at this point it has two ways, one is to spread to both sides (respectively the direction of the arrows, whichever is bigger, this is a greedy strategy), and the other is to randomize to a point, for example, it can just instantly ~~randomly~~~ to another point (green). Between these two methods is **randomizing an answer and determining the probability of accepting the new state**. The answer is then made closer to the optimal solution.↵
↵
Annealing, is a physical term, for the process, see above:↵
↵
> First there are three parameters denoting the initial temperature $T_0$, the coefficient of cooling $d$, and the termination temperature $T_k$. where $T_0$ is a relatively large number, $d$ is a number very close to 1 but smaller than 1, and $T_k$ is a positive number close to 0. The temperature T is initialized to $T_0$, and $T*=d$ each time until $T$ reaches $T_k$.↵
↵
For specific operations, the above is also more detailed.↵
↵
The main point is that the simulated annealing application scenarios.↵
↵
There are several scenarios↵
- Geometric, distance problems↵
- Dp, greedy, in the transfer DP, or in the greedy part, use simulated annealing to solve.↵
- ~~ Messing around ~~↵
↵
The randomization trick is still some help for this :[https://oi-wiki.org//misc/random/](https://oi-wiki.org//misc/random/). I didn't really look at it in detail myself, but anyway, it's just using some tech that is not used in general for tapping, but simulated annealing is very much about randomizing evenly, uniformly.↵
↵
Like, Rocky Valley P1337, someone using tech rand, only ran the simulated annealing once, and passed, while I, also while ...... to the time limit to stop, to anneal, although passed, but it is the same code handed over many times before passing.↵
↵
# Examples↵
↵
[P1337 [JSOI2004] Equilibrium Point / Hanging XXX](https://www.luogu.com.cn/problem/P1337)↵
↵
For this question, it's a board that simulates annealing, straight up crazy annealing, and then this is equivalent to finding the peak on a two-dimensional, where all the previous demos were one-dimensional. All you need to do is for each answer, go ahead and violently calculate its contribution, and then keep simulating annealing, why can this question simulate annealing?↵
In a very large answer, his periphery can not become very small all of a sudden, at most, it will become a little smaller, and may even become larger, so only a multi-peak.↵
PS: By adjusting the parameters, adjusting the step size, to control the simulated annealing, quite interesting, ~~ like the first time I played scartch, adjusting the code parameters to change the game. ~~↵
↵
```cpp↵
↵
int n;↵
struct node{↵
double u,v,w.↵
}a[N],now;↵
double dist(double x,double y){↵
double res=0; for(int i=1;i=n;i++){↵
for(int i=1;i<=n;i++){↵
res+=sqrt((x-a[i].u)*(x-a[i].u) + (y-a[i].v))*(y-a[i].v))*a[i].w; }↵
}return res.↵
}void sa(){↵
now.u=(rand()%10000)*2-10000,now.v=(rand()%10000)*2-10000,now.w=dist(now.u,now.v); ↵
for(double T = 1000;T >= 1e-8;T *= 0.99){↵
double xx=now.u+((rand()%10000)*2-10000)*T;↵
double yy=now.v+((rand()%10000)*2-10000)*T;↵
double ww=dist(xx,yy);↵
if(ww < now.w) now={xx,yy,ww}; else if(exp(-(ww.w)))↵
else if(exp(-(ww-now.w)/T)*RAND_MAX>rand()) now={xx,yy,now.w}; ↵
}↵
}↵
void solve(){↵
cin>>n;↵
for(int i=1;i<=n;i++) cin>>a[i].u>>a[i].v>>a[i].w;↵
↵
while((double)clock()/CLOCKS_PER_SEC<0.99) sa();↵
printf("%.3lf %.3lf",now.u,now.v);↵
}↵
```↵
I use plain rand, but tech is recommended.↵
↵
↵
Translated with www.DeepL.com/Translator (free version)
