РППНС Алгоритмы поиска на графах
Назван в честь	Поиск по первому наилучшему совпадению
Автор	Richard E. Korf[вд]
Структура данных	граф
Худшее время	${\displaystyle {\mathcal {O))(b^{2d-1})}$

Рекурсивный Поиск по Первому Наилучшему Совпадению (РППНС) (англ. Recursive Best-First Search — 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] ← 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): даже если бы было доступно больше памяти, алгоритм РППНС не способен ею воспользоваться.

• Стюарт Рассел, Питер Норвиг: Искусственный интеллект: современный подход, 2004 год, Prentice Hall, ISBN 3-8273-7089-2

Алгоритмы поиска на графах
Неинформированные методы	Алгоритм Брона — Кербоша Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжёра