simulated annealing (idea)

Below is a template for simulated annealing programs:

Start with initial state si;
t := T0;   //initial temperature

REPEAT
	REPEAT
		choose neighbor state sj
		compute DeltaC = C(si) - C(sj); 
		IF tDeltaC > ran(0,1) THEN si := sj 
	UNTIL equilibrium();

	t := alpha * t; //reduce temperature
UNTIL frozen();

The important bits here are: C() which is a "cost function" that evaluates how good a given solution is. equilibrium() determines how long the SA runs at a given temperature. T₀ is the initial temperature, while alpha is a value that decreases the temperature at every iteration.

Simulated annealing is similar to Hill Climbing approaches in that it is a local search strategy. However, unlike hill climbing (also called Directed Walk), simulated annealing allows you to "escape" local optima.