Every search keeps a list of places it could look next. The only real difference between one search and another is which place it picks next.
Race breadth-first against A* on random walls. Both find a path with the fewest steps, but A* looks at far fewer cells, because it knows roughly which way the goal is. Now pick the Trap and race greedy against A*: greedy dashes for the goal, slips into the cup and has to take the long way round. Try Mud with breadth-first against Dijkstra: breadth-first counts steps, so it wades straight through, while Dijkstra counts cost and walks round. Set beam search to width 1 on a maze and watch it give up.
Then switch to Climb a landscape. Plain hill climbing stops on the first hilltop it reaches. Random restarts, a cooling annealer or a crowd of guesses can do better. Turn the bumpiness up and see which methods cope. For annealing at work on a real puzzle, try Retaining Water.
Breadth-first search was described by Edward F. Moore in 1959, for finding the shortest way through a maze; Konrad Zuse had used the same idea in the 1940s, in work that was not published until 1972. Edsger Dijkstra worked out his shortest-path algorithm in 1956, reportedly in about twenty minutes at a café in Amsterdam, and published it in 1959. In 1968 Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute published A*, built to help Shakey the robot plan its routes; it is still the standard choice in video games. Simulated annealing was introduced by Scott Kirkpatrick, Daniel Gelatt and Mario Vecchi in 1983. It borrows its idea from metalworkers, who cool metal slowly so its atoms settle into a strong, low-energy arrangement.
And in 1997 David Wolpert and William Macready proved the "no free lunch" theorems: averaged over every possible problem, no search method beats any other. The trick is always to know something about your problem, the way A* knows which way the goal is.
