Simulated Annealing (SA) is a probabilistic optimization algorithm inspired by the physical annealing process in metallurgy.

The Physical Annealing Process

Annealing involves heating a material to a specific temperature and then cooling it down gradually. During this process, the internal energy of crystalline molecules tends to decrease. The molecular arrangement transitions through various states. If a new state has lower energy than the current one, it is accepted unconditionally. How ever, if the new state has higher energy, it may still be accepted with a probability that decreases as temperature drops. This acceptance mechanism is the core principle underlying simulated annealing.

Randomness in Computation

The C++ standard library provides the rand() function from <cstdlib> for generating pseudo-random numbers. These random numbers can simulate probabilistic events in algorithms. While custom random number generators are possible, the built-in implementation is usually sufficient for most applications.

When Simulated Annealing Applies

For monotonic problems, binary search suffices. For unimodal functions, ternary search handles optimization effectively. However, certain problems present exponentially large or factorial-level solution spaces where traditional approaches fail.

Consider combinatorial construction problems where the goal is to arrange a sequence satisfying specific constraints. The search space becomes factorial in size. Depth-first search will certainly time out, and even with pruning, achieving acceptable performance proves challenging. Heuristic methods like A* require significant expertise to implement correctly.

In these scenarios, simulated annealing offers a practical alternative, trading guaranteed optimality for reasonable runtime performance.

Algorithm Framework

Simulated annealing simulates the annealing process computationally. The algorithm begins from an arbitrary state. For construction-type problems, one can randomly swap two positions and evaluate whether the change improves the solution. If improvement occurs, the new state is accepted. Otherwise, the algorithm accepts the worse state with probability exp(-ΔE/(kT)), where E represents enternal energy at temperature T, ΔE denotes the change in energy, and k is a configurable constant.

Practical Example

Balanced Point Problem

Problem Description: Given three points with coordinates (0,0), (0,2), and (1,1), find a point that balances the system.

Sample Input:

3
0 0 1
0 2 1
1 1 1

Sample Output:

0.577 1.000

Solution Approach: This is a classic simulated annealing application. The strategy involves randomly sampling candidate points in the plane and evaluating whether each candidate improves the current best solution.

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;
};

double energy(const Point& p, const vector<Point>& masses) {
    double sum = 0.0;
    for (const auto& m : masses) {
        double dx = p.x - m.x;
        double dy = p.y - m.y;
        sum += sqrt(dx * dx + dy * dy) * m.w;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    
    vector<Point> masses(n);
    for (int i = 0; i < n; i++) {
        cin >> masses[i].x >> masses[i].y >> masses[i].w;
    }
    
    Point current = {0.0, 0.0};
    double currentEnergy = energy(current, masses);
    
    double temperature = 1000.0;
    double coolingRate = 0.997;
    
    while (temperature > 1e-8) {
        Point candidate;
        candidate.x = current.x + (rand() * 2.0 / RAND_MAX - 1.0) * temperature;
        candidate.y = current.y + (rand() * 2.0 / RAND_MAX - 1.0) * temperature;
        
        double candidateEnergy = energy(candidate, masses);
        double delta = candidateEnergy - currentEnergy;
        
        if (delta < 0 || exp(-delta / temperature) > (double)rand() / RAND_MAX) {
            current = candidate;
            currentEnergy = candidateEnergy;
        }
        
        temperature *= coolingRate;
    }
    
    cout << fixed << setprecision(3) << current.x << " " << current.y << "\n";
    return 0;
}

Implementation Notes: Parameter tuning significantly impacts performance. Small adjustments to cooling rate or initial temperature can cause the algorithm to either fail to converge or take excessive time.