Beam Search

• Of course, we can take advantage of memory.
• Dijkstra uses a lot, but you can combine best first and Dijkstra.
• BFS can lead you into dead ends.
• A variant of BFS is beam search.
• Maintain the best X states.
• This doesn't get you the best result, but it often gets you a good one. This is called a heuristic search. (It usually works and when it doesn't get the best it still usually leads to a good result.)
• You can also have a variable size beam for when there are a lot of similar values.