  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-cost path problems in time polynomial in the
branching factor and the number of edges in a minimum-cost path. Thus,
approximating their completely informed heuristic functions with high precision
is NP-hard. We therefore examine recent publications that propose the use of
neural networks for this purpose. We support our claim that these approaches do
not scale to large instance sizes both theoretically and experimentally. Our
first experimental results for three representative NP-hard minimum-cost path
problems suggest that using neural networks to approximate completely informed
heuristic functions with high precision might result in network sizes that
scale exponentially in the instance sizes. The research community might thus
benefit from investigating other ways of integrating heuristic search with
machine learning.
