Best First Search

• Instead of using exhausitive techniques, you can use heuristic techniques.
• The simplest heuristic is to just choose the best next option.
• This is called steepest ascent hill climbing or just best first search.
• So, if you have 10 cities, and you're starting at city 1, you choose the closest, let's say 2.
• Then you choose the closest not already visited from 2, say 7.
• You continue until you get to the last city.
• How long does this algorithm take?
• A closely related search is beam search. Here you keep a beam, of say 5, of the best paths.
• The standard exhaustive technique for this is Dijkstra's algorithm. The trucking firms don't use it.