Directed Research Project Details
Know When To Fold 'Em. The Value of Improved Heuristics in A* Search
| Author: | Tristan Smith |
|---|---|
| Date: | April 08, 2002 |
| Time: | 13:00 |
| Location: | 220 Deschutes |
Abstract
The success of A* search and other heuristic search algorithms is directly tied to the quality of the heuristic. An enormous amount of work is done to improve heuristics and it is generally accepted that small improvements in heuristic accuracy lead to significant improvements in the time-complexity of the algorithm.
I will discuss a real-world example where this is not the case. Analysis of this specific problem suggests a simple general way to understand and predict the effects of heuristic accuracy on the time complexity of the A* algorithm.