Эвристический поиск с ограничением объема памяти
Простейший способ сокращения потребностей в памяти для поиска А* состоит в применении идеи итеративного углубления в контексте эвристического поиска. Реализация этой идеи привела к созданию алгоритма А* с итеративным углублением (Iterative-Deepening А* — IDA*). Основное различие между алгоритмом IDA* и стандартным алгоритмом итеративного углубления состоит в том, что применяемым условием останова развертывания служит f-стоимость (д+л), а не глубина; на каждой итерации этим остановочным значением является минимальная f-стоимость любого узла, превышающая остановочное значение, достигнутое в предыдущей итерации. Алгоритм IDA* является практически применимым для решения многих задач с единичными стоимостями этапов и позволяет избежать существенных издержек, связанных с поддержкой отсортированной очереди узлов. К сожалению, этот алгоритм характеризуется такими же сложностями, связанными с использованием стоимостей с действительными значениями, как и итеративная версия поиска по критерию стоимости, которая описана в упр. 3.11. В данном разделе кратко рассматриваются два более современных алгоритма с ограничением памяти, получивших названия RBFS и МА*.
Рекурсивный поиск по первому наилучшему совпадению (Recursive Best-First Search — RBFS) — это простой рекурсивный алгоритм, в котором предпринимаются попытки имитировать работу стандартного поиска по первому наилучшему совпадению, но с использованием только линейного пространства. Этот алгоритм приведен в листинге 4.1. Он имеет структуру, аналогичную структуре рекурсивного поиска в глубину, но вместо бесконечного следования вниз по текущему пути данный алгоритм контролирует f-значение наилучшего альтернативного пути, доступного из любого предка текущего узла. Если текущий узел превышает данный предел, то текущий этап рекурсии отменяется и рекурсия продолжается с альтернативного пути. После отмены данного этапа рекурсии в алгоритме RBFS происходит замена f-значения каждого узла вдоль данного пути наилучшим f-значением его дочернего узла. Благодаря этому в алгоритме RBFS запоминается f-значение наилучшего листового узла из забытого поддерева и поэтому в некоторый последующий момент времени может быть принято решение о том, стоит ли снова развертывать это поддерево. На рис. 4.4 показано, как с помощью алгоритма RBFS происходит поиск пути в Бухарест.
Листинг 4.1. Алгоритм рекурсивного поиска по первому наилучшему совпадению
function Recursive-Best-First-Search(problem) returns решение result или индикатор неудачи failure
RBFS(problem, Make-Node(Initial-State[problem]), °o)
function RBFS(problem, node, f_limit) returns решение result
или индикатор неудачи failure и новый предел f-стоимости f_limit if Goal-Test[problem] (State[node]) then return узел node successors <— Expand(node, problem) if множество узлов-преемников successors пусто
then return failure, °o for each s in successors do
f[s] <— max(g(s)+h(s),f[node]) repeat
best <— узел с наименьшим f-значением в множестве successors if f[best] > f_limit then return failure, f[best]
Алгоритм RBFS является немного более эффективным по сравнению с IDA*, но все еще страдает от недостатка, связанного со слишком частым повторным формированием узлов. В примере, приведенном на рис. 4.4, алгоритм RBFS вначале следует по пути через узел RimnicuVilcea, затем "меняет решение" и пытается пройти через узел Fagaras, после этого снова возвращается к отвергнутому ранее решению. Такие смены решения происходят в связи с тем, что при каждом развертывании текущего наилучшего пути велика вероятность того, что его f-значение увеличится, поскольку функция h обычно становится менее оптимистической по мере того, как происходит развертывание узлов, более близких к цели. После того как возникает такая ситуация, особенно в больших пространствах поиска, путь, который был вторым после наилучшего, может сам стать наилучшим путем, поэтому в алгоритме поиска приходится выполнять возврат, чтобы проследовать по нему. Каждое изменение решения соответствует одной итерации алгоритма IDA* и может потребовать многих повторных развертываний забытых узлов для воссоздания наилучшего пути и развертывания пути еще на один узел.
Как и алгоритм поиска A*, RBFS является оптимальным алгоритмом, если эвристическая функция я (л) допустима. Его пространственная сложность равна О (bd), но охарактеризовать временную сложность довольно трудно: она зависит и от точности эвристической функции, и от того, насколько часто происходила смена наилучшего пути по мере развертывания узлов. И алгоритм IDA*, и алгоритм RBFS подвержены потенциальному экспоненциальному увеличению сложности, связанной с поиском в графах (см. раздел 3.5), поскольку эти алгоритмы не позволяют определять наличие повторяющихся состояний, отличных от тех, которые находятся в текущем пути. Поэтому данные алгоритмы способны много раз исследовать одно и то же состояние.
Алгоритмы IDA* и RBFS страдают от того недостатка, что в них используется слишком мало памяти. Между итерациями алгоритм IDA* сохраняет только единственное число — текущий предел f-стоимости. Алгоритм RBFS сохраняет в памяти больше информации, но количество используемой в нем памяти измеряется лишь значением O(bd): даже если бы было доступно больше памяти, алгоритм RBFS не способен ею воспользоваться.
Поэтому представляется более разумным использование всей доступной памяти. Двумя алгоритмами, которые осуществляют это требование, являются поиск МА* (Memory-bounded А* — поиск А* с ограничением памяти) и SMA* (Simplified МА* — упрощенный поиск МА*). В данном разделе будет описан алгоритм SMA*, который действительно является более простым, чем другие алгоритмы этого типа. Алгоритм SMA* действует полностью аналогично поиску А*, развертывая наилучшие листовые узлы до тех пока, пока не будет исчерпана доступная память. С этого момента он не может добавить новый узел к дереву поиска, не уничтожив старый. В алгоритме SMA* всегда уничтожается наихудший листовой узел (тот, который имеет наибольшее f-значение). Как и в алгоритме RBFS, после этого в алгоритме SMA* значение забытого (уничтоженного) узла резервируется в его родительском узле. Благодаря этому предок забытого поддерева позволяет определить качество наилучшего пути в этом поддереве. Поскольку имеется данная информация, в алгоритме SMA* поддерево восстанавливается, только если обнаруживается, что все другие пути выглядят менее многообещающими по сравнению с забытым путем. Иными словами, если все потомки узла л забыты, то неизвестно, каким путем можно следовать от л, но все еще можно получить представление о том, есть ли смысл куда-либо следовать от п.
Полный алгоритм слишком сложен для того, чтобы его можно было воспроизвести в данной книге5, но заслуживает упоминания один его нюанс. Как уже было сказано выше, в алгоритме SMA* развертывается наилучший листовой узел и удаляется наихудший листовой узел. А что происходит, если все листовые узлы имеют одинаковое f-значение? В таком случае может оказаться, что алгоритм выбирает для удаления и развертывания один и тот же узел. В алгоритме SMA* эта проблема решается путем развертывания самого нового наилучшего листового узла и удаления самого старого наихудшего листового узла. Эти два узла могут оказаться одним и тем же узлом, только если существует лишь один листовой узел; в таком случае текущее дерево поиска должно представлять собой единственный путь от корня до листового узла, заполняющий всю память. Это означает, что если данный листовой узел не является целевым узлом, то решение не достижимо при доступном объеме памяти, даже если этот узел находится в оптимальном пути решения. Поэтому такой узел может быть отброшен точно так же, как и в том случае, если он не имеет преемников.
Алгоритм SMA* является полным, если существует какое-либо достижимое решение, иными словами, если d, глубина самого поверхностного целевого узла, меньше чем объем памяти (выраженный в хранимых узлах). Этот алгоритм оптимален, если достижимо какое-либо оптимальное решение; в противном случае он возвращает наилучшее достижимое решение. С точки зрения практики алгоритм SMA* вполне может оказаться наилучшим алгоритмом общего назначения для поиска оптимальных решений, особенно если пространство состояний представляет собой граф, стоимости этапов не одинаковы, а операция формирования узлов является более дорогостоящей в сравнении с дополнительными издержками сопровождения открытых и закрытых списков.
Однако при решении очень сложных задач часто возникают ситуации, в которых алгоритм SMA* вынужден постоянно переключаться с одного пути решения на другой в пределах множества возможных путей решения, притом что в памяти может поместиться только небольшое подмножество этого множества. (Такие ситуации напоминают проблему пробуксовки в системах подкачки страниц с жесткого диска.) В таком случае на повторное формирование одних и тех узлов затрачивается дополнительное время, а это означает, что задачи, которые были бы фактически разрешимыми с помощью поиска А* при наличии неограниченной памяти, становятся трудноразрешимыми для алгоритма SMA*. Иными словами, из-за <= ограничений в объеме памяти некоторые задачи могут становиться трудноразрешимыми с точки зрения времени вычисления. Хотя отсутствует теория, позволяющая найти компромисс между затратами времени и памяти, создается впечатление, что зачастую избежать возникновения этой проблемы невозможно. Единственным способом преодоления такой ситуации становится частичный отказ от требований к оптимальности решения.