RBFS

RBFS

Клас	Алгоритми пошуку, Алгоритми на графах
Структура даних	граф
Найгірша швидкодія	${\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-значення найкращого альтернативного шляху, доступного з будь-якого предка поточного вузла. Якщо поточний вузол перевищує задану межу, то поточний етап рекурсії скасовується і рекурсія продовжується з альтернативного шляху. Після скасування даного етапу рекурсії в алгоритмі RBFS відбувається заміна f-значення кожного вузла вздовж даного шляху найкращим f-значенням його дочірнього вузла. Завдяки цьому в алгоритмі RBFS запам'ятовується f-значення найкращого листового вузла з забутого піддерева і тому в деякий наступний момент часу може бути прийнято рішення про те, чи варто знову розгортати це піддерево.

Застосування

Подивимось як за допомогою алгоритму RBFS відбувається пошук шляху в Бухарест. Етапи пошуку найкоротшого маршруту в Бухарест за допомогою алгоритму RBFS. Значення f-межі для кожного рекурсивного виклику показано над кожним поточним вузлом:

Переваги та недоліки

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

Як і алгоритм пошуку A*, RBFS є оптимальним алгоритмом, якщо евристична функція h(n) допустима. Його просторова складність дорівнює 0 (bd), але охарактеризувати тимчасову складність досить важко: вона залежить і від точності евристичної функції, і від того, наскільки часто відбувалася зміна найкращого шляху в міру розгортання вузлів. І алгоритм IDA*, і алгоритм RBFS схильні до потенційного експоненціального збільшення складності, пов'язаної з пошуком в графах, оскільки ці алгоритми не дозволяють визначати наявність повторюваних станів, відмінних від тих, які знаходяться в поточному шляху. Тому дані алгоритми здатні багато разів досліджувати один і той же стан.

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

Література

• Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach [Архівовано 28 лютого 2011 у Wayback Machine.], 2004, Prentice Hall, ISBN 3-8273-7089-2