The Lab · Moore, 1959 · Dijkstra, 1959 · A*, 1968

How to Search

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. Watch them choose.

What to search

Searcher

Race against

3

The grid

25%

Paint with

Drag on the grid to paint. Drag the green start or the red goal to move them.

Searchers

The landscape

40%
3,000

Click the map to choose where the climbers start. Brighter means higher. The highest point is 1,000 m.

Run

Which one should I use?

Every step costs the same and you want the shortest route? Breadth-first. Some ground costs more? Dijkstra. You know where the goal is? A*, which is usually the best pick. Short of memory and any route will do? Depth-first or beam search. In a hurry, and a decent route is fine? Greedy.

One big smooth hill? Plain hill climbing is quick and fine. Lots of little hills? Try random restarts or simulated annealing. Want to explore many places at once? A beam or a population. No method wins on every landscape. That is a real theorem, nicknamed “no free lunch”.