Простейший способ сокращения потребностей в памяти для поиска А* состоит в применении идеи итеративного углубления в контексте эвристического поиска. Реализация этой идеи привела к созданию алгоритма А* с итеративным углублением (Iterative-Deepening А* — IDA*). Основное различие между алгоритмом IDA* и стандартным алгоритмом итеративного углубления состоит в том, что применяемым условием останова развертывания служит f-стоимость (g+h), а не глубина; на каждой итерации этим остановочным значением является минимальная f-стоимость любого узла, превышающая остановочное значение, достигнутое в предыдущей итерации. Алгоритм IDA* является практически применимым для решения многих задач с единичными стоимостями этапов и позволяет избежать существенных издержек, связанных с подцержкой отсортированной очереди узлов. К сожалению, этот алгоритм характеризуется такими же сложностями, связанными с использованием стоимостей с действительными значениями, как и итеративная версия поиска по критерию стоимости, которая описана в упр. 3.11. В данном разделе кратко рассматриваются два более современных алгоритма с ограничением памяти, получивших названия RBFS и МА*.

Рекурсивный поиск по первому наилучшему совпадению (Recursive Best-First Search — RBFS) — это простой рекурсивный алгоритм, в котором предпринимаются попытки имитировать работу стандартного поиска по первому наилучшему совпадению, но с использованием только линейного пространства. Этот алгоритм приведен в листинге 4.1. Он имеет структуру, аналогичную структуре рекурсивного поиска в глубину, но вместо бесконечного следования вниз по текущему пути данный алгоритм контролирует f-значение наилучшего альтернативного пути, доступного из любого предка текущего узла. Если текущий узел превышает данный предел, то текущий этап рекурсии отменяется и рекурсия продолжается с альтернативного пути. После отмены данного этапа рекурсии в алгоритме RBFS происходит замена f-значения каждого узла вдоль данного пути наилучшим f-значением его дочернего узла. Благодаря этому в алгоритме RBFS запоминается f-значение наилучшего листового узла из забытого поддерева и поэтому в некоторый последующий момент времени может быть принято решение о том, стоит ли снова развертывать это поддерево. На рис. 4.4 показано, как с помощью алгоритма RBFS происходит поиск пути в Бухарест.