跳转至

爬山算法

簡介

爬山算法是一種局部擇優的方法，採用啓發式方法，是對深度優先搜索的一種改進，它利用反饋信息幫助生成解的決策。

直白地講，就是當目前無法直接到達最優解，但是可以判斷兩個解哪個更優的時候，根據一些反饋信息生成一個新的可能解。

因此，爬山算法每次在當前找到的最優方案 \(x\) 附近尋找一個新方案。如果這個新的解 \(x'\) 更優，那麼轉移到 \(x'\)，否則不變。

這種算法對於單峯函數顯然可行。

Q：都知道是單峯函數了為什麼不三分呢？

A：爬山算法的優勢在於當正解的寫法你並不瞭解（常見於毒瘤計算幾何和毒瘤數學題），或者本身狀態維度很多，無法容易地寫分治（例 2 就可以用二分完成合法正解）時，可以通過非常暴力的計算得到最優解。

但是對於多數需要求解的函數，爬山算法很容易進入一個局部最優解，如下圖（最優解為 \(\color{green}{\Uparrow}\)，而爬山算法可能找到的最優解為 \(\color{red}{\Downarrow}\)）。

具體實現

爬山算法一般會引入温度參數（類似模擬退火）。類比地説，爬山算法就像是一隻兔子喝醉了在山上跳，它每次都會朝着它所認為的更高的地方（這往往只是個不準確的趨勢）跳，顯然它有可能一次跳到山頂，也可能跳過頭翻到對面去。不過沒關係，兔子翻過去之後還會跳回來。顯然這個過程很沒有用，兔子永遠都找不到出路，所以在這個過程中兔子冷靜下來並在每次跳的時候更加謹慎，少跳一點，以到達合適的最優點。

兔子逐漸變得清醒的過程就是降温過程，即温度參數在爬山的時候會不斷減小。

關於降温：降温參數是略小於 \(1\) 的常數，一般在 \([0.985, 0.999]\) 中選取。

例 1 「JSOI2008」球形空間產生器

題意：給出 \(n\) 維空間中的 \(n + 1\) 個點，已知它們在同一個 \(n\) 維球面上，求出球心。\(n \leq 10\)，座標絕對值不超過 \(20000\)。

很明顯的單峯函數，可以使用爬山解決。本題算法流程：

  1. 初始化球心為各個給定點的重心（即其各維座標均為所有給定點對應維度座標的平均值），以減少枚舉量。
  2. 對於當前的球心，求出每個已知點到這個球心歐氏距離的平均值。
  3. 遍歷所有已知點。記錄一個改變值 \(\textit{cans}\)（分開每一維度記錄）對於每一個點的歐氏距離，如果大於平均值，就把改變值加上差值，否則減去。實際上並不用判斷這個大小問題，只要不考慮絕對值，直接用座標計算即可。這個過程可以形象地轉化成一個新的球心，在空間裏推來推去，碰到太遠的點就往點的方向拉一點，碰到太近的點就往點的反方向推一點。
  4. 將我們記錄的 \(\textit{cans}\) 乘上温度，更新球心，回到步驟 2
  5. 在温度小於某個給定閾值的時候結束。

因此，我們在更新球心的時候，不能直接加上改變值，而是要加上改變值與温度的乘積。

並不是每一道爬山題都可以具體地用温度解決，這只是一個例子。

例題參考代碼 
 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
#include <bits/stdc++.h>
using namespace std;
double ans[10001], cans[100001], dis[10001], tot, f[1001][1001];
int n;

void check() {
  tot = 0;
  for (int i = 1; i <= n + 1; i++) {
    dis[i] = 0;
    cans[i] = 0;
    for (int j = 1; j <= n; j++)
      dis[i] += (f[i][j] - ans[j]) * (f[i][j] - ans[j]);
    dis[i] = sqrt(dis[i]);  // 欧氏距离
    tot += dis[i];
  }
  tot /= (n + 1);  // 平均
  for (int i = 1; i <= n + 1; i++)
    for (int j = 1; j <= n; j++)
      cans[j] += (dis[i] - tot) * (f[i][j] - ans[j]) /
                 tot;  // 对于每个维度把修改值更新掉，欧氏距离差*差值贡献
}

int main() {
  cin >> n;
  for (int i = 1; i <= n + 1; i++)
    for (int j = 1; j <= n; j++) {
      cin >> f[i][j];
      ans[j] += f[i][j];
    }
  for (int i = 1; i <= n; i++) ans[i] /= (n + 1);      // 初始化
  for (double t = 10001; t >= 0.0001; t *= 0.99995) {  // 不断降温
    check();
    for (int i = 1; i <= n; i++) ans[i] += cans[i] * t;  // 修改
  }
  for (int i = 1; i <= n; i++) printf("%.3f ", ans[i]);
}

例 2 「BZOJ 3680」吊打 XXX

題意：求 \(n\) 個點的帶權類費馬點。

框架類似，用了點物理知識。

參考代碼 
 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
#include <cmath>
#include <cstdio>
const int N = 10005;
int n, x[N], y[N], w[N];
double ansx, ansy;

void hillclimb() {
  double t = 1000;
  while (t > 1e-8) {
    double nowx = 0, nowy = 0;
    for (int i = 1; i <= n; ++i) {
      double dx = x[i] - ansx, dy = y[i] - ansy;
      double dis = sqrt(dx * dx + dy * dy);
      nowx += (x[i] - ansx) * w[i] / dis;
      nowy += (y[i] - ansy) * w[i] / dis;
    }
    ansx += nowx * t, ansy += nowy * t;
    if (t > 0.5)
      t *= 0.5;
    else
      t *= 0.97;
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &x[i], &y[i], &w[i]);
    ansx += x[i], ansy += y[i];
  }
  ansx /= n, ansy /= n;
  hillclimb();
  printf("%.3lf %.3lf\n", ansx, ansy);
  return 0;
}

優化

很容易想到的是，為了儘可能獲取優秀的答案，我們可以多次爬山。方法有修改初始狀態/修改降温參數/修改初始温度等，然後開一個全局最優解記錄答案。每次爬山結束之後，更新全局最優解。

這樣處理可能會存在的問題是超時，在正式考試時請手造大數據測試調參。

劣勢

其實爬山算法的劣勢上文已經提及：它容易陷入一個局部最優解。當目標函數不是單峯函數時，這個劣勢是致命的。因此我們要引進 模擬退火。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用