Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Рекурсивний пошук по першому найкращому збігу (англ. 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 є трохи ефективнішим в порівнянні з , але все ще страждає від недоліку, пов'язаного із занадто частим повторним формуванням вузлів. У прикладі, наведеному на рис. 1, 2, 3, алгоритм RBFS спочатку слідує по шляху через вузол RimnicuVilcea, потім «змінює рішення» і намагається пройти через вузол Fagaras, після цього знову повертається до відкинутого раніше рішенням. Такі зміни рішення відбуваються у зв'язку з тим, що при кожному розгортанні поточного найкращого шляху велика ймовірність того, що його f-значення збільшиться, оскільки функція h зазвичай стає менш оптимістичною в міру того, як відбувається розгортання вузлів, більш близьких до мети. Після того як виникає така ситуація, особливо у великих просторах пошуку, шлях, який був другим після найкращого, може сам стати найкращим шляхом, тому в алгоритмі пошуку доводиться виконувати повернення, щоб пройти по ньому. Кожна зміна рішення відповідає одній ітерації алгоритму і може вимагати багато повторних розгортань забутих вузлів для відтворення найкращого шляху і розгортання шляху ще на один вузол.
Як і алгоритм пошуку A*, RBFS є оптимальним алгоритмом, якщо евристична функція h(n) допустима. Його просторова складність дорівнює 0 (bd), але охарактеризувати тимчасову складність досить важко: вона залежить і від точності евристичної функції, і від того, наскільки часто відбувалася зміна найкращого шляху в міру розгортання вузлів. І алгоритм , і алгоритм RBFS схильні до потенційного експоненціального збільшення складності, пов'язаної з пошуком в графах, оскільки ці алгоритми не дозволяють визначати наявність повторюваних станів, відмінних від тих, які знаходяться в поточному шляху. Тому дані алгоритми здатні багато разів досліджувати один і той же стан.
Алгоритми і RBFS страждають від того недоліку, що в них використовується занадто мало пам'яті. Між ітераціями алгоритм зберігає тільки єдине число — поточний межа f-вартості. Алгоритм RBFS зберігає в пам'яті більше інформації, але кількість використовуваної в ньому пам'яті виміряється лише значенням O (bd): навіть якщо б було доступно більше пам'яті, алгоритм RBFS не здатний нею скористатися.
Література
- Stuart Russell, Peter Norvig: Artificial Intelligence: A Modern Approach [ 28 лютого 2011 у Wayback Machine.], 2004, Prentice Hall,
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rekursivnij poshuk po pershomu najkrashomu zbigu angl Recursive Best First Search RBFS ce prostij rekursivnij algoritm v yakomu roblyatsya sprobi imituvati robotu standartnogo poshuku za pershim najkrashim zbigom ale z vikoristannyam tilki linijnogo prostoru RBFSKlasAlgoritmi poshuku Algoritmi na grafahStruktura danihgrafNajgirsha shvidkodiyaO b 2 d 1 displaystyle mathcal O b 2d 1 OptimalnijtakZagalni polozhennyaPriklad realizaciyi algoritmu na psevdokodi function Recursive Best First Search problem returns rishennya result abo indikator nevdachi failure RBFS problem Make Node Initial State problem function RBFS problem node f limit returns rishennya result abo indikator nevdachi failure i novij mezha f vartosti f limit if Goal Test problem State node then return vuzel node successors Expand node problem if mnozhina vuzliv nastupnikiv successors pusta then return failure for each s in successors do f s max g s h s f node repeat best vuzol z najmenshim f znachennyam v mnozhini successors if f best gt f limit then return failure f best alternative druge pislya najmenshogo f znachennya v mnozhini successors result f best RBFS problem best min f limit alternative if result failure then return result Vin maye strukturu analogichnu strukturi rekursivnogo poshuku v glibinu ale zamist neskinchennogo prohodzhennya vniz po potochnomu shlyahu danij algoritm kontrolyuye f znachennya najkrashogo alternativnogo shlyahu dostupnogo z bud yakogo predka potochnogo vuzla Yaksho potochnij vuzol perevishuye zadanu mezhu to potochnij etap rekursiyi skasovuyetsya i rekursiya prodovzhuyetsya z alternativnogo shlyahu Pislya skasuvannya danogo etapu rekursiyi v algoritmi RBFS vidbuvayetsya zamina f znachennya kozhnogo vuzla vzdovzh danogo shlyahu najkrashim f znachennyam jogo dochirnogo vuzla Zavdyaki comu v algoritmi RBFS zapam yatovuyetsya f znachennya najkrashogo listovogo vuzla z zabutogo piddereva i tomu v deyakij nastupnij moment chasu mozhe buti prijnyato rishennya pro te chi varto znovu rozgortati ce pidderevo Zastosuvannya Podivimos yak za dopomogoyu algoritmu RBFS vidbuvayetsya poshuk shlyahu v Buharest Etapi poshuku najkorotshogo marshrutu v Buharest za dopomogoyu algoritmu RBFS Znachennya f mezhi dlya kozhnogo rekursivnogo vikliku pokazano nad kozhnim potochnim vuzlom Perevagi ta nedoliki Algoritm RBFS ye trohi efektivnishim v porivnyanni z ale vse she strazhdaye vid nedoliku pov yazanogo iz zanadto chastim povtornim formuvannyam vuzliv U prikladi navedenomu na ris 1 2 3 algoritm RBFS spochatku sliduye po shlyahu cherez vuzol RimnicuVilcea potim zminyuye rishennya i namagayetsya projti cherez vuzol Fagaras pislya cogo znovu povertayetsya do vidkinutogo ranishe rishennyam Taki zmini rishennya vidbuvayutsya u zv yazku z tim sho pri kozhnomu rozgortanni potochnogo najkrashogo shlyahu velika jmovirnist togo sho jogo f znachennya zbilshitsya oskilki funkciya h zazvichaj staye mensh optimistichnoyu v miru togo yak vidbuvayetsya rozgortannya vuzliv bilsh blizkih do meti Pislya togo yak vinikaye taka situaciya osoblivo u velikih prostorah poshuku shlyah yakij buv drugim pislya najkrashogo mozhe sam stati najkrashim shlyahom tomu v algoritmi poshuku dovoditsya vikonuvati povernennya shob projti po nomu Kozhna zmina rishennya vidpovidaye odnij iteraciyi algoritmu i mozhe vimagati bagato povtornih rozgortan zabutih vuzliv dlya vidtvorennya najkrashogo shlyahu i rozgortannya shlyahu she na odin vuzol Yak i algoritm poshuku A RBFS ye optimalnim algoritmom yaksho evristichna funkciya h n dopustima Jogo prostorova skladnist dorivnyuye 0 bd ale oharakterizuvati timchasovu skladnist dosit vazhko vona zalezhit i vid tochnosti evristichnoyi funkciyi i vid togo naskilki chasto vidbuvalasya zmina najkrashogo shlyahu v miru rozgortannya vuzliv I algoritm i algoritm RBFS shilni do potencijnogo eksponencialnogo zbilshennya skladnosti pov yazanoyi z poshukom v grafah oskilki ci algoritmi ne dozvolyayut viznachati nayavnist povtoryuvanih staniv vidminnih vid tih yaki znahodyatsya v potochnomu shlyahu Tomu dani algoritmi zdatni bagato raziv doslidzhuvati odin i toj zhe stan Algoritmi i RBFS strazhdayut vid togo nedoliku sho v nih vikoristovuyetsya zanadto malo pam yati Mizh iteraciyami algoritm zberigaye tilki yedine chislo potochnij mezha f vartosti Algoritm RBFS zberigaye v pam yati bilshe informaciyi ale kilkist vikoristovuvanoyi v nomu pam yati vimiryayetsya lishe znachennyam O bd navit yaksho b bulo dostupno bilshe pam yati algoritm RBFS ne zdatnij neyu skoristatisya Literatura Stuart Russell Peter Norvig Artificial Intelligence A Modern Approach 28 lyutogo 2011 u Wayback Machine 2004 Prentice Hall ISBN 3 8273 7089 2