The Metropolis Algorithm: Theory and Examples

The Metropolis algorithm is a Markov Chain Monte Carlo optimization technique of stunningly broad applicability.

This short monograph quickly develops the underlying theory of ergodic Markov chains, explains the algorithm in general terms, and presents eight specific applications ranging from a Sudoku puzzle solver to the Traveling Salesman Problem.

All the applications are implemented with the accompanying source code freely downloadable on GitHub at https://github.com/CDouglasHoward13/Metropolis

It's also the foundation of a very good estimator for global illumination! See https://en.wikipedia.org/wiki/Metropolis_light_transport . It used to achieve state of the art quality on scenes with caustics and/or tough indirect-light dominated scenes (eg. veach door).