High-performance A* search using rapidly growing heuristics

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