Hill Climbing and Local Minima

• Dijkstra has a problem when you have a lot of states.
• Say you have a million states, and you can get to them all from the initial state. You have to maintain a list of a million.
• Another form of search is best first search.
• In this case, you just move to the best next state.
• This can often work if the topology is suited to it.
• However, it's a greedy strategy.
• Think of the state space as a topological map. You have x and y as inputs, and the height is the output.
• You want to maximize the height.
• If you're standing on Mt. Fuji, you just keep going up, and you eventually reach the top.
• However, if you're in London, you're not going to get up the Gerkin following this strategy.
• You can get caught in local minima (maxima).
• What's a topology?