где h* (п) — истинная стоимость достижения цели из узла п. Почти для всех практически применяемых эвристических функций эта ошибка, по меньшей мере, пропорциональна стоимости пути, и происходящий в связи с этим экспоненциальный рост в конечном итоге превосходит возможности любого компьютера. По этой причине на практике стремление находить оптимальное решение часто не оправдано. Иногда вместо этого целесообразно использовать варианты поиска А*, позволяющие быстро находить неоптимальные решения, а в других случаях — разрабатывать эвристические функции, которые являются более точными, но не строго допустимыми. В любом случае применение хорошей эвристической функции все равно обеспечивает поразительную экономию усилий по сравнению с использованием неинформированного поиска. Вопрос разработки хороших эвристических функций рассматривается в разделе 4.2.

Но большая продолжительность вычислений не является основным недостатком поиска А*. Поскольку при поиске А* все сформированные узлы хранятся в памяти (как и во всех алгоритмах Graph-Search), фактически ресурсы пространства исчерпываются задолго до того, как исчерпываются ресурсы времени. По этой причине поиск А* не является практически применимым при решении многих крупномасштабных задач. Разработанные недавно алгоритмы позволяют преодолеть эту проблему пространства, не жертвуя оптимальностью или полнотой, за счет небольшого увеличения времени выполнения. Эти алгоритмы рассматриваются ниже.