Teaching Stochastic Local Search

This paper outlines an experiential approach to teaching stochastic local search. Using the Tale of the Drunken Topographer as a running analogy, students are led from the implementation of a hill descent algorithm through small, motivated modifications to a simple implementation of simulated annealing. Supplementary applets allow students to experiment with temperature and gain understanding of its importance in the annealing process. Challenge problems complete this brief but rich introduction to stochastic local search.