Simulated annealing

Simulated annealing is an optimization strategy borrowed straight from metallurgy: to grow a flawless crystal, a smith heats metal until atoms jiggle freely, then cools it slowly so they settle into a low-energy, near-perfect lattice. The algorithm mimics this — it explores a problem's solution space by making random changes, and crucially, at high 'temperature' it sometimes ACCEPTS a worse solution. That willingness to step backwards is what lets it escape the shallow valleys (local minima) that trap greedy methods, and find a far better global arrangement.

A move that improves the cost is always taken; a move that worsens it by ΔE is accepted with probability e^(−ΔE/T). As the temperature T is cooled on a schedule, bad moves grow rarer and the search freezes into a good solution. For decades this was the heart of the legendary TimberWolf placer and is still the engine behind many floorplanners and FPGA placers (VPR), where the search space is too rugged for analytical methods. Its charm is generality — you only need a cost function and a way to perturb a solution — but it pays in runtime, so it is favored for smaller, gnarlier sub-problems.