Перегляд вихідного коду сторінки RBFS

{{Картка_алгоритм
|клас=[[Алгоритми пошуку]], [[Алгоритми на графах]]
|зображення=
|дані=[[Граф (математика)|граф]]
|час=<math>\mathcal{O}(b^{2d-1})</math>
|пропуски=
|оптимальний=так
}}
'''Рекурсивний пошук по першому найкращому збігу''' ({{lang-en|Recursive Best-First Search — RBFS}})&nbsp;— це простий рекурсивний алгоритм, в якому робляться спроби імітувати роботу стандартного пошуку за першим найкращим збігом, але з використанням тільки лінійного простору.

== Загальні положення ==

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

 '''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-межі для кожного рекурсивного виклику показано над кожним поточним вузлом:


<div style="clear:both">


<div style="clear:both">


<div style="clear:both">

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

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

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

== Література ==

* Stuart Russell, Peter Norvig: ''[http://aima.cs.berkeley.edu/ Artificial Intelligence: A Modern Approach] {{Webarchive|url=https://web.archive.org/web/20110228023805/http://aima.cs.berkeley.edu/ |date=28 лютого 2011 }}'', 2004, Prentice Hall, ISBN 3-8273-7089-2

[[Категорія:Алгоритми]]