The (Un)Scalability of Heuristic Approximators for NP-Hard Search Problems

Sumedh Pendurkar, Taoan Huang, Sven Koenig +1

The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with a completely informed heuristic function, A* solves many NP-hard minimum-…