Algorithm::模擬退火

模擬退火算是一種搜尋的算法,可以用來解決一些例如座標的搜尋問題。

模擬退火是這次去枝幹學會的,最基本的例題就是找一點到其他N個點,使他們到該點距離和最短。
這種題目有幾種做法,三分搜、爬山法等等,但是寫完之後覺得模擬退火效率不錯而且不會很難寫。

模擬退火的意思就是模擬金屬冷卻時原子的運動狀況,也許有點像擴散作用吧,就是你給他攪一攪他就會往比較鬆的地方跑,原子會往能量比較低還是什麼的地方鑽….等等。

講到這裡感覺很麻煩,其實做法不難,只要先從一個點開始,寫一個函數判斷某一個座標的值是多少,比如這題就枚舉所有點算出答案,之後定一個適當的轉移距離,並隨機一個方向,看看那個位置的值有沒有比現在好,有的話就走過去,沒有的話,便縮短距離,持續收練,慢慢的就會走向正解,可以想像是一顆粒子隨機震動並慢慢停止。

整個演算法的瓶頸應該會落在轉移狀態的運算上,對於時間要求比較緊的題目可以裡用狀態轉移取代重新運算來加速。

比較有趣的是,當題目需要搜尋兩個點的時候,要怎麼做才可以比較容易搜到好解。
初步的實驗,是先震動一個點,之後就把他當成只有一個點的來解,解出來的解是第一個點這樣移動之後的值,如果沒有比較好,則兩個點都回到原位。
實驗了一下發現,第二個點如果不回到原位,會讓解的誤差變大,其實這應該可以推出來,因為之前的最優解是建立在兩個點在某個位置時的解,不讓第二個點規位等於破壞原本的最優解。

感覺比三分搜好寫多了XD,隨機方向可以利用cmath的三角函數,直接random一個整數塞進去就可以了,非常方便,大致上應該夠隨機了。縮短距離可以直接乘0.9,中止條件可以看距離小於多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//尋找和所有點距離和最小的點
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 1010
using namespace std;
int X[N],Y[N],n;
inline double pow2(double x){
return x*x;
}
double check(double x,double y){
double ans=0;
F(n)ans+=sqrt(pow2(x-X[i])+pow2(y-Y[i]));
return ans;
}
int main(){
scanf("%*d");
while(~scanf("%d",&n)){
F(n)scanf("%d%d",X+i,Y+i);
double x=0,y=0,tx,ty,tans,l=10000,ans;
ans=check(x,y);
while(l>1e-4){
int tmp=rand();
tx=x+l*cos(tmp);ty=y+l*sin(tmp);
tans=check(tx,ty);
if(tans<ans)ans=tans,x=tx,y=ty;
else l*=0.9;
}
printf("%.9f\n",2*ans);
}
}
//尋找兩個點使他們跟給定的四個點最小生成樹最小
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define N 10
using namespace std;
int X[N],Y[N],n,F[N],e;
struct E{
int a,b;
double c;
}G[N*2];
struct V{
double x,y;
V operator+(double l){
int tmp=rand();
return (V){x+l*cos(tmp),y+l*sin(tmp)};
}
}v[N];
int find(int x){
return x==F[x]?x:F[x]=find(F[x]);
}
inline double pow2(double x){
return x*x;
}
double check(V s1,V s2){
double ans=0;
e=0;v[4]=s1,v[5]=s2;
F(5)Fl(j,i+1,6)
G[e++]=(E){i,j,sqrt(pow2(v[i].x-v[j].x)+pow2(v[i].y-v[j].y))};
F(6)F[i]=i;
sort(G,G+e,[](E a,E b){return a.c<b.c;});
F(e){
if(find(G[i].a)!=find(G[i].b)){
ans+=G[i].c;
F[find(G[i].a)]=find(G[i].b);
}
}
return ans;
}
int main(){
scanf("%d",&n);
while(n--){
F(4)scanf("%lf%lf",&v[i].x,&v[i].y);
double ttans,tans,ans,l1=10000,l2;
V s1=(V){0,0},s2=(V){0,0},ts1,ts2,tmp;
ans=check(s1,s2);
while(l1>1e-3){
l2=10000;
ts1=s1+l1;
tans=check(ts1,s2);
tmp=s2;
while(l2>1e-3){
ts2=s2+l2;
ttans=check(ts1,ts2);
if(ttans<tans)tans=ttans,s2=ts2;
else l2*=0.9;
}
if(tans<ans)ans=tans,s1=ts1;
else l1*=0.9,s2=tmp;
}
printf("%f\n",2*ans);
}
}