Рекурсивный поиск по первому наилучшему совпадению

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

РППНС
Алгоритмы поиска на графах
Назван в честь Поиск по первому наилучшему совпадению
Автор Richard E. Korf[d]
Структура данных граф
Худшее время

Общие положения

Пример реализации алгоритма на псевдокоде

 
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] ← 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

Он имеет структуру, аналогичную структуре рекурсивного поиска в глубину, но вместо бесконечного прохождения вниз по текущему пути данный алгоритм контролирует f-значение лучшего альтернативного пути, доступного с любого предка текущего узла. Если текущий узел превышает заданный предел, то текущий этап рекурсии прекращается и рекурсия продолжается по альтернативному пути. После прекращения данного этапа рекурсии в алгоритме РППНС происходит замена f-значения каждого узла вдоль данного пути наилучшим f-значением его дочернего узла. Благодаря этому в алгоритме РППНС запоминается f-значение лучшего листового узла с забытого поддерева и поэтому в некоторый следующий момент времени может быть принято решение о том, стоит ли снова разворачивать это поддерево[1].

Преимущества и недостатки

Алгоритм РППНС немного более эффективный по сравнению с IDA*, но всё ещё страдает от недостатка, связанного со слишком частым повторным формированием узлов[2]. Такие изменения решения происходят в связи с тем, что при каждом развёртывании текущего наилучшего пути велика вероятность того, что его f-значение увеличится, поскольку функция h обычно становится менее оптимистичной по мере того, как происходит развёртывание узлов, более близких к цели. После того как возникает такая ситуация, особенно в больших пространствах поиска, путь, который был вторым после лучшего, может сам стать лучшим путём, поэтому в алгоритме поиска приходится выполнять возвращения, чтобы пройти по нему. Каждое изменение решения соответствует одной итерации алгоритма IDA* и может потребовать много повторных развёртываний забытых узлов для воспроизведения лучшего пути и развёртывания пути ещё на один узел.

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

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

Примечания
  1. Раздел Применение не написан до конца в статье оригинала, поэтому пока нет смысла вносить его в эту статью.
  2. Здесь должен быть фрагмент
    В примере, приведённом на рис. 1, 2 и 3, алгоритм РППНС сначала следует по пути через узел RimnicuVilcea, затем «меняет решение» и пытается пройти через узел Fagaras, после этого снова возвращается к отвергнутому ранее решению,
    но он ссылается на недописанный раздел Применение в статье оригинала.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.