Skip to yearly menu bar Skip to main content

Workshop: I Can’t Believe It’s Not Better: Understanding Deep Learning Through Empirical Falsification

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

Sumedh Dattaguru Pendurkar · Taoan Huang · Sven Koenig · Guni Sharon

Abstract: The A* algorithm is commonly used to solve NP-hard combinatorial optimization problems. When provided with an accurate heuristic function, A* can solve such problems in time complexity that is polynomial in the solution depth. This fact implies that accurate heuristic approximation for many such problems is also NP-hard. In this context, we examine a line of recent publications that propose the use of deep neural networks for heuristic approximation. We assert that these works suffer from inherent scalability limitations since --- under the assumption that P$\ne$NP --- such approaches result in either (a) network sizes that scale exponentially in the instance sizes or (b) heuristic approximation accuracy that scales inversely with the instance sizes. Our claim is supported by experimental results for three representative NP-hard search problems that show that fitting deep neural networks accurately to heuristic functions necessitates network sizes that scale exponentially with the instance size.

Chat is not available.