Skip to content

Hill Climbing

Introduction

Hill climbing is a local optimization method that uses heuristics to improve upon depth-first search, utilizing feedback information to guide the generation of solution decisions.

In simple terms, when the optimal solution cannot be directly reached, but it is possible to determine which of two solutions is better, a new possible solution is generated based on some feedback information.

Thus, hill climbing iteratively searches for a new solution near the current best solution \( x \). If the new solution \( x' \) is better, the algorithm moves to \( x' \); otherwise, it remains unchanged.

This algorithm is clearly feasible for unimodal functions.

Q: If we already know it's a unimodal function, why not use ternary search?

A: The advantage of hill climbing is that when the correct solution method is not well understood (common in tricky computational geometry and math problems), or when the state space has many dimensions making divide-and-conquer difficult to implement (Example 2 could be solved with binary search for a legitimate solution), it can obtain an optimal solution through very brute-force computation.

However, for most functions that need to be optimized, hill climbing can easily get stuck in a local optimum, as shown in the figure below (the global optimum is \( \color{green}{\Uparrow} \), while hill climbing may find \( \color{red}{\Downarrow} \) as the best solution).

Implementation Details

Hill climbing often introduces a temperature parameter (similar to simulated annealing). By analogy, hill climbing is like a drunk rabbit jumping on a mountain. Each time, it jumps in the direction it believes is higher (often just an inaccurate trend). It might jump to the peak in one go, or it might overshoot and jump to the opposite side. But that's okay—the rabbit will jump back after overshooting. Obviously, this process is inefficient; the rabbit might never find a way out. So, during this process, the rabbit calms down and becomes more cautious with each jump, jumping shorter distances to reach a suitable optimum.

The process of the rabbit gradually sobering up is the cooling process, meaning the temperature parameter continuously decreases during hill climbing.

Regarding cooling: The cooling parameter is a constant slightly less than 1, typically chosen from the range \([0.985, 0.999]\).

Example Problems

「JSOI2008」Spherical Space Generator

Given \( n + 1 \) points in \( n \)-dimensional space, known to lie on the same \( n \)-dimensional sphere, find the sphere's center. \( n \leq 10 \), coordinates have absolute values not exceeding \( 20000 \).

Solution

This is clearly a unimodal function, solvable using hill climbing. The algorithm steps for this problem:

  1. Initialize the sphere's center as the centroid of the given points (i.e., each coordinate is the average of the corresponding coordinates of all given points) to reduce enumeration.
  2. For the current center, compute the average Euclidean distance from each known point to this center.
  3. Iterate through all known points. Record a change value \( \textit{cans} \) (separately for each dimension). For each point's Euclidean distance, if it is greater than the average, add the difference to the change value; otherwise, subtract it. Actually, there's no need to check the magnitude; simply compute using coordinates without considering absolute values. This process can be visualized as a new sphere center being pushed around in space: if a point is too far, pull the center toward it; if too close, push it away.
  4. Multiply the recorded \( \textit{cans} \) by the temperature, update the center, and return to step 2.
  5. Stop when the temperature falls below a given threshold.

Therefore, when updating the center, we do not directly add the change value but rather the product of the change value and the temperature.

Not every hill climbing problem can be specifically solved with temperature; this is just an example.

Reference Code 
 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
#include <cmath>
#include <iomanip>
#include <iostream>
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]);  // Euclidean distance
    tot += dis[i];
  }
  tot /= (n + 1);  // Average
  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;  // Update the modification value for each dimension: Euclidean distance difference * difference contribution
}

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);      // Initialize
  for (double t = 10001; t >= 0.0001; t *= 0.99995) {  // Continuous cooling
    check();
    for (int i = 1; i <= n; i++) ans[i] += cans[i] * t;  // Modify
  }
  cout << fixed << setprecision(3);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}
「BZOJ 3680」Hang XXX

Find the weighted Fermat point for \( n \) points.

Solution

The framework is similar, using some physics knowledge.

Reference Code 
 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
#include <cmath>
#include <iomanip>
#include <iostream>
constexpr 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() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> x[i] >> y[i] >> w[i];
    ansx += x[i], ansy += y[i];
  }
  ansx /= n, ansy /= n;
  hillclimb();
  std::cout << std::fixed << std::setprecision(3) << ansx << ' ' << ansy
            << '\n';
  return 0;
}

Optimization

A common idea is to run hill climbing multiple times to obtain better answers. Methods include modifying the initial state, adjusting the cooling parameter, or changing the initial temperature, while maintaining a global best solution to record the answer. After each hill climbing run, update the global best solution.

A potential issue with this approach is time limits. During official exams, manually generate large datasets to test and tune parameters.

Disadvantages

The disadvantage of hill climbing has already been mentioned: it easily gets stuck in a local optimum. When the objective function is not unimodal, this disadvantage is fatal. Therefore, we introduce Simulated Annealing.

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