Полный алгоритм слишком сложен для того, чтобы его можно было воспроизвести в данной книге, но заслуживает упоминания один его нюанс. Как уже было сказано выше, в алгоритме SMA* развертывается наилучший листовой узел и удаляется наихудший листовой узел. А что происходит, если все листовые узлы имеют одинаковое f-значение? В таком случае может оказаться, что алгоритм выбирает для удаления и развертывания один и тот же узел. В алгоритме SMA* эта проблема решается путем развертывания самого нового наилучшего листового узла и удаления самого старого наихудшего листового узла. Эти два узла могут оказаться одним и тем же узлом, только если существует лишь один листовой узел; в таком случае текущее дерево поиска должно представлять собой единственный путь от корня до листового узла, заполняющий всю память. Это означает, что если данный листовой узел не является целевым узлом, то решение не достижимо при доступном объеме памяти, даже если этот узел находится в оптимальном пути решения. Поэтому такой узел может быть отброшен точно так же, как и в том случае, если он не имеет преемников.

Алгоритм SMA* является полным, если существует какое-либо достижимое решение, иными словами, если d, глубина самого поверхностного целевого узла, меньше чем объем памяти (выраженный в хранимых узлах). Этот алгоритм оптимален, если достижимо какое-либо оптимальное решение; в противном случае он возвращает наилучшее достижимое решение. С точки зрения практики алгоритм SMA* вполне может оказаться наилучшим алгоритмом общего назначения для поиска оптимальных решений, особенно если пространство состояний представляет собой граф, стоимости этапов не одинаковы, а операция формирования узлов является более дорогостоящей в сравнении с дополнительными издержками сопровождения открытых и закрытых списков.

Однако при решении очень сложных задач часто возникают ситуации, в которых алгоритм SMA* вынужден постоянно переключаться с одного пути решения на другой в пределах множества возможных путей решения, притом что в памяти может поместиться только небольшое подмножество этого множества. (Такие ситуации напоминают проблему пробуксовки в системах подкачки страниц с жесткого диска.) В таком случае на повторное формирование одних и тех узлов затрачивается дополнительное время, а это означает, что задачи, которые были бы фактически разрешимыми с помощью поиска А* при наличии неограниченной памяти, становятся трудноразрешимыми для алгоритма SMA*. Иными словами, из-за ограничений в объеме памяти некоторые задачи могут становиться трудноразрешимыми с точки зрения времени вычисления. Хотя отсутствует теория, позволяющая найти компромисс между затратами времени и памяти, создается впечатление, что зачастую избежать возникновения этой проблемы невозможно. Единственным способом преодоления такой ситуации становится частичный отказ от требований к оптимальности решения.