Heuristic Search¶
There is another problem with the breadth-first search strategy we started with - all the effort involved in checking every possible path. Consider a situation in which each move leads to 20 new moves. In one step we have 20 options to worry about. After 2 steps, we have 20 x 20 = 400 options we need to consider. By seven moves we have over a billion possibilities!
Step # |
1 |
2 |
3 |
4 |
5 |
6 |
|---|---|---|---|---|---|---|
# of Options |
20 |
400 |
8,000 |
160,000 |
3,200,000 |
64,000,000 |
What we need is a way to constrain the search - to explore the “good” possibilities before we worry about the crazy looking ones. Imagine you were doing the cat → dog word ladder. You would probably say something like “hmmm, I could turn cat into cot and that looks like it is closer to dog”. You then would look at where cot could take you before backtracking and trying something like cat → bat or any other possible moves that seemed to take you further away from dog. If at some point you got stuck, you would then go back and try some of those moves that you initially ignored.
Searching in this manner, where we use some kind of intuition about which direction looks most promising to guide our exploration, gives us a heuristic search algorithm. A heuristic is simply a rule of thumb - a shortcut that hopefully allows us to solve a problem more rapidly. For the word ladder, our mental heuristic would be something like “first try words that have more letters that match the target”. Because cot is only 2 letters off from dog we would explore it before we worried about bat which is 3 letters off from dog.
To experiment with using heuristic search, try the Search Playground again. This time, check the box that says “Allow Intuition”. Now you will get to see where the destination is, and you are not forced to explore unpromising looking routes. Try searching through a few different maps. Can you successfully find the shortest path without exploring everything?
How would you describe the heuristic (intuition or rule of thumb) you used while exploring maps? It was probably something like “pick the location that is closest to the destination”. Did it always work? Or did you sometimes get greedy and skip over options you should have explored? (Try typing in 3142 for the Map Number and then press Reload Map for an example of one that is easy to get fooled on).