High-performance A* search using rapidly growing heuristics
Stephen V. Chenoweth, Henry W. Davis · 1991
In high-performance A* searching to solve satisficing problems, there is a critical need to design heuristics which cause low time-complexity. In order for humans or machines to do this effectively, there must be an understanding of the domain-independent properties that such heuristics have. We snow that, contrary to common belief, accuracy is not critical; the key issue is whether or not heuristic values are concentrated closely near a rapidly growing central function. As an application, we show that, by multiplying heuristics, it is possible to reduce exponential average time-complexity to polynomial. This is contrary to conclusions drawn from previous studies. Experimental and theoretical examples are given.