AIOJ

Introduction

The hill-climbing algorithm is a locally greedy method that uses a heuristic. It is an improvement over depth-first search and uses feedback to help make decisions when generating a solution.

In simple terms, when the optimum cannot be reached directly but two solutions can be compared, feedback is used to generate a new candidate solution.

Thus, at each step the algorithm looks for a new solution near the best solution $x$ found so far. If the new solution $x'$ is better, it moves to $x'$ ; otherwise, it stays where it is.

This algorithm is clearly effective for a unimodal function.

Q: If we already know that the function is unimodal, why not use ternary search?

A: The advantage of hill climbing is that when the form of the correct solution is unknown (as is common in difficult computational-geometry and mathematics problems), or when the state has many dimensions and it is difficult to formulate a divide-and-conquer solution (Example 2 can be solved with binary search), brute-force computation can still be used to obtain the optimum.

For most functions that need to be optimized, however, hill climbing can easily get stuck at a local optimum, as shown below (the optimum is marked by $\color{green}{\Uparrow}$ , while the optimum that hill climbing may find is marked by $\color{red}{\Downarrow}$ ).

Implementation

Hill climbing generally introduces a temperature parameter, similarly to simulated annealing. By analogy, hill climbing is like a drunk rabbit jumping around on a mountain: at each step it jumps toward what it believes is higher ground (which is often only an inaccurate trend). It may jump straight to the summit or overshoot and fall to the other side. That is not a problem—the rabbit will jump back. This process is clearly useless because the rabbit can never find a way out, so it gradually calms down and becomes more cautious, making smaller jumps until it reaches a suitable optimum.

The rabbit's gradual recovery is the cooling process: the temperature parameter continually decreases during hill climbing.

For cooling, the parameter is a constant slightly less than $1$ , generally chosen from $[0.985, 0.999]$ .

Examples

「JSOI2008」Spherical Space Generator

Given $n + 1$ points in an $n$ -dimensional space, known to lie on the same $n$ -dimensional sphere, find the sphere's center. $n \leq 10$ , and the absolute value of every coordinate is at most $20000$ .

Solution

This is clearly a unimodal function, so hill climbing can be used. The algorithm is:

Initialize the center to the centroid of the given points (the average of the coordinates in each dimension), reducing the amount of enumeration.
For the current center, calculate the average Euclidean distance from each known point to the center.
Iterate over all known points. Maintain a change value $\textit{cans}$ , recording one value for each dimension. For each point, if its Euclidean distance is greater than the average, add the difference to the change value; otherwise, subtract it. In fact, there is no need to compare the two values: simply omit the absolute value and compute directly from the coordinates. Geometrically, this moves a new center around in space: points that are too far pull it slightly toward themselves, while points that are too close push it slightly in the opposite direction.
Multiply the recorded $\textit{cans}$ by the temperature, update the center, and return to Step 2.
Stop when the temperature is below a given threshold.

Therefore, when updating the center, we must add the product of the change value and the temperature rather than adding the change value directly.

Not every hill-climbing problem can be handled specifically with a temperature parameter; this is just one example.

Reference implementation

#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 change value for each dimension; contribution of the distance difference times the coordinate difference
}

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) {  // Continue cooling
    check();
    for (int i = 1; i <= n; i++) ans[i] += cans[i] * t;  // Update
  }
  cout << fixed << setprecision(3);
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

「BZOJ 3680」Beating XXX

Find the weighted geometric median of $n$ points.

Solution

The framework is similar and uses some physics.

Reference implementation

#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

It is easy to think of running hill climbing multiple times to obtain a better answer. One can change the initial state, the cooling parameter, or the initial temperature, and maintain a global optimum. After each climb, update the global optimum.

This approach may time out. In an actual contest, construct large test cases yourself to tune the parameters.

Disadvantages

The disadvantage of hill climbing has already been mentioned: it can get trapped in a local optimum. When the objective function is not unimodal, this disadvantage is fatal. We therefore introduce simulated annealing.