概述
-
爬山算法是一种基于局部择优进行转移的近似算法。
-
具体来讲，它尝试利用深度优先搜索的反馈信息，来将搜索过程从盲目的变为启发性的，从而获得效率上的提高（和正确性上的降低）。
-
说人话就是，尽管我们不知道最优状态，但我们根据当前的信息，尽可能地判断出可达的所有状态（可能很宽泛）中，哪个期望意义下（可能是长线）最优，然后转移过去。
实现原理
-
假设我们要对某个多峰函数求最值（单峰用啥模拟算法？），我们把函数类比为山脉，当前的状态类比为爬山者所在的位置。
-
初始的时候随机生成多个初始状态，即向山脉中随机空投复数个伞兵。
-
怎么随机是个大学问...万一正态分布的表现比均匀随机好呢？
-
之所以要多个，是因为爬山算法在状态数少的时候表现超差...（本来就是三大近似算法中最差的一个啦拜托，不要再自废武功了）。
-
-
每轮我们依次枚举所有状态，从它们出发去尝试扩展出下一轮的状态，即伞兵尝试爬山。
-
注意，这个扩展的结果不一定“相邻”。不妨将我们扩展的对象状态和当前状态的差异性称为步长 \(step\)，则一般在开始时给 \(step\) 取充分大的值，然后每轮 \(\times \Delta\)。
-
一般来讲，\(\Delta\in [0.985,0.999]\)（经验结论，唯像模型）。
-
原则上每个状态只能扩展出一个状态，否则又会退化成搜索的指数复杂度。
-
决定哪个状态被扩展出就很重要了。一般使用状态评估函数来决策。
-
-
然后将生成的状态去重，缩短步长，进行下一轮。
-
足够轮数之后，枚举所有状态，取最优者为解。
例题
-
大部分情况下，能爬的一定能退，而爬的表现并不如退。
-
不过如果数据在某种意义上单调/单峰，那么爬山算法的表现还是不错的，此时只需要一个初始状态。
P1337 [JSOI2004] 平衡点
-
题意：求 \(n\) 力平衡的平衡点，这里的每个力是一个大小固定、终点固定的矢量。
-
数据范围：\(n\leqslant 10^3,-10^4\leqslant x_i,y_i\leqslant 10^4,F_i\leqslant 10^3\)。
-
观察到平衡点一定是唯一的，而且越靠近它一定越平衡。
-
于是想到使用爬山算法，每次算出合力后向合力方向转移，直到 \(step<eps\)。
-
算合力显然可以正交分解。
-
不过事实上，如果记平衡点为 \((x,y)\)，显然当其中一者固定时合力 \(F\) 是关于另一者的单谷函数，且严格，即无平台。
-
所以可以三分套三分。不过那种难写的东西...哈。
-
放一下爬山的代码吧。
const ld eps=5e-4,delta=0.990;
ld X=0.01,Y=0.01,step=2e4;
ld dx,dy,dis;
ld fx,fy,F;
il void work(){
while(step>eps){
fx=fy=0;
For(i,1,n){
dx=a[i].x-X;
dy=a[i].y-Y;
dis=sqrtl(dx*dx+dy*dy);
fx+=a[i].w*dx/dis;
fy+=a[i].w*dy/dis;
}
F=sqrtl(fx*fx+fy*fy);
X+=step*fx/F;
Y+=step*fy/F;
step*=delta;
}
printf("%.3Lf %.3Lf",X,Y);
return;
}