Главная arrow Поиск arrow Эвристический поиск
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Эвристический поиск Печать

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

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


Алгоритм рекурсивного поиска по первому наилучшему совпадению

function Recursive-Best-First-Search(problem) returns решение result
  или индикатор неудачи failure
  RBFS(problem, Make-Node(Initial-State[problem] ) , ∞)

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, ∞

  for each s in successors do
    f[s] <r- max(g(s) +h(s) , f [node] )
  repeat
  best <— узел с наименьшим f-значением в множестве successors
  if f[best] > f_limit then return failure, f[best]
    alternative <— второе после наименьшего f-значение
    в множестве successors
    result, f[best] <- RBFS{problem, best,
    min{f_limit, alternative))
  if result Ф failure then return result


После развертывания узлов Arad, Sibiu и Vilcea 


После возврата к узлу Sibiu и развертывания узла Fagaras


После переключения снова на узел Rimnicu Vilcea и развертывания узла Pitesti


Этапы поиска кратчайшего маршрута в Бухарест с помощью алгоритма RBFS. Значение f-предела для каждого рекурсивного вызова показано над каждым текущим узлом: путь через узел RimnicuVilcea, который следует до текущего наилучшего листового узла fPitesti,), имеет значение, худшее по сравнению с наилучшим альтернативным путем fFagaras,) (а); рекурсия продолжается и значение наилучшего листового узла забытого поддерева D17) резервируется в узле RimnicuVilcea; затем развертывается узел Fagaras, в результате чего обнаруживается наилучшее значение листового узла, равное 450 (б); рекурсия продолжается и значение наилучшего листового узла забытого поддерева D50) резервируется в узле Fagaras; затем развертывается узел RimnicuVilcea; на этот раз развертывание продолжается в сторону Бухареста, поскольку наилучший альтернативный путь (через узел Timisoara,) стоит, по меньшей мере, 447(e)

Алгоритм RBFS является немного более эффективным по сравнению с IDA*, но все еще страдает от недостатка, связанного со слишком частым повторным формированием узлов. В примере, приведенном на рисунке, алгоритм RBFS вначале следует по пути через узел RimnicuVilcea, затем «меняет решение» и пытается пройти через узел Fagaras, после этого снова возвращается к отвергнутому ранее решению. Такие смены решения происходят в связи с тем, что при каждом развертывании текущего наилучшего пути велика вероятность того, что его f-значение увеличится, поскольку функция h обычно становится менее оптимистической по мере того, как происходит развертывание узлов, более близких к цели. После того как возникает такая ситуация, особенно в больших пространствах поиска, путь, который был вторым после наилучшего, может сам стать наилучшим путем, поэтому в алгоритме поиска приходится выполнять возврат, чтобы проследовать по нему. Каждое изменение решения соответствует одной итерации алгоритма IDA* и может потребовать многих повторных развертываний забытых узлов для воссоздания наилучшего пути и развертывания пути еще на один узел.

Как и алгоритм поиска A*, RBFS является оптимальным алгоритмом, если эвристическая функция h(n) допустима. Его пространственная сложность равна O(bd), но охарактеризовать временную сложность довольно трудно: она зависит и от точности эвристической функции, и от того, насколько часто происходила смена наилучшего пути по мере развертывания узлов. И алгоритм IDA*, и алгоритм RBFS подвержены потенциальному экспоненциальному увеличению сложности, связанной с поиском в графах (см. раздел 3.5), поскольку эти алгоритмы не позволяют определять наличие повторяющихся состояний, отличных от тех, которые находятся в текущем пути. Поэтому данные алгоритмы способны много раз исследовать одно и то же состояние.

Алгоритмы IDA* и RBFS страдают от того недостатка, что в них используется слишком мало памяти. Между итерациями алгоритм IDA* сохраняет только единственное число — текущий предел f-стоимости. Алгоритм RBFS сохраняет в памяти больше информации, но количество используемой в нем памяти измеряется лишь значением O(bd): даже если бы было доступно больше памяти, алгоритм RBFS не способен ею воспользоваться.

Поэтому представляется более разумным использование всей доступной памяти. Двумя алгоритмами, которые осуществляют это требование, являются поиск МА* (Memory-bounded А* — поиск А* с ограничением памяти) и SMA* (Simplified МА* — упрощенный поиск МА*). В данном разделе будет описан алгоритм SMA*, который действительно является более простым, чем другие алгоритмы этого типа. Алгоритм SMA* действует полностью аналогично поиску А*, развертывая наилучшие листовые узлы до тех пока, пока не будет исчерпана доступная память. С этого момента он не может добавить новый узел к дереву поиска, не уничтожив старый. В алгоритме SMA* всегда уничтожается наихудший листовой узел (тот, который имеет наибольшее f-значение). Как и в алгоритме RBFS, после этого в алгоритме SMA* значение забытого (уничтоженного) узла резервируется в его родительском узле. Благодаря этому предок забытого поддерева позволяет определить качество наилучшего пути в этом поддереве. Поскольку имеется данная информация, в алгоритме SMA* поддерево восстанавливается, только если обнаруживается, что все другие пути выглядят менее многообещающими по сравнению с забытым путем. Иными словами, если все потомки узла n забыты, то неизвестно, каким путем можно следовать от n, но все еще можно получить представление о том, есть ли смысл куда-либо следовать от n.

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

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

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