По́шук «Найкра́щий — пе́рший» — це алгоритм пошуку, який досліджує граф шляхом розширення найперспективніших вузлів, які обираються відповідно до визначеного правила.
Загальні відомості
(англ. Judea Pearl) описав пошук «Найкращий — перший», взявши як оцінку вузла n значення деякої оцінки f(n), яка, взагалі кажучи, може залежати від опису вузла n, опису мети, інформації, яка зібрана пошуком на даний момент, і головне, від будь-яких додаткових знань про предметну галузь».
Деякі автори використовували пошук «Найкращий — перший» спеціально для опису пошуку з евристикою, щоб спробувати передбачити, наскільки близько знаходимося до фінального стану, так що шляхи, які мають найкращу евристичну оцінку, розглядаються першими. Цей специфічний тип пошуку називається жадібним пошуком «Найкращий — перший».
Ефективний вибір поточного найкращого кандидата для розширення пошуку, як правило, реалізується за допомогою .
Алгоритм пошуку A* (А-star) є прикладом оптимального пошуку «Найкращий — перший». Алгоритм «Найкращий — перший» часто використовуються для пошуку шляху у комбінаторному пошуку.
Алгоритм
1. OPEN = [Початковий стан] 2. поки OPEN не є порожнім, повторювати: 2.1. Видалити найкращий вузол з OPEN, назвемо його N. 2.2. Якщо N цільовий стан, робимо трасування шляху назад до початкового вузла (через записи до батьків від N) і повертаємо шлях. 2.3. Створити список нащадків вузла N. 2.4. Оцінюємо кожного нащадка, додаємо його в OPEN, і записуємо N як його батька. 3. закінчити
Зверніть увагу, що ця версія алгоритму не є повною, тобто в ньому не завжди можливо знайти шлях між двома вузлами, навіть якщо він є. Наприклад, алгоритм «застряє» в циклі, якщо він заходить в глухий кут, тобто вузол з нащадком, який є його батьком. Алгоритм повернеться до свого батька, додасть тупиковий вузол нащадка в список OPEN і перейде на нього ще раз, і так далі. Наступна версія розширює алгоритм, використовуючи додаткові список CLOSE, що містить всі вузли, які були оцінені, і не будуть переглянуті знову. Це дозволяє уникнути повторної оцінки будь-якого вузла, і не породжувати нескінченні цикли.
1. OPEN = [початковий стан] 2. CLOSE = [] 3. поки OPEN не є порожнім повторювати: 3.1. Видалити найкращий вузол з OPEN, назвемо його N, додати його в CLOSE. 3.2. Якщо N цільовий стан, робимо трасування шляху назад до початкового вузла (через записи до батьків від N) і повертаємо шлях. 3.3. Створити список нащадків вузла N. 3.4. Для кожного нащадка повторювати: 3.4.1. Якщо нащадка немає в списку CLOSE: Оцінюємо його, додаємо його в OPEN, і записуємо N як його батька. 3.4.2. Інакше: якщо це новий шлях кращий, ніж попередній, змінюємо запис на батька. 4. закінчити
Також зверніть увагу, що даний псевдокод, обох версій, просто припиняється, коли шлях не знайдений. Фактичні реалізації, звичайно, вимагають спеціальної обробки цієї ситуації.
Жадібний пошук «Найкращий — перший»
Використання жадібного алгоритму розширює першого нащадка батьків. Після генерації нащадків: Якщо евристична оцінка нащадка краща, ніж у його батька, нащадок вставляється вперед черги (з батьками повторно прямо за ним), і цикл перезапускається. В іншому випадку, нащадок вставляється в чергу (у місці, визначеному його евристичної вартістю). Потім проводиться оцінка інших спадкоємців (якщо такі є) у батька.
Інші алгоритми пошуку
Посилання
- Wikibooks: Artificial Intelligence: Best-First Search
Ця стаття не містить . (червень 2016) |
Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Po shuk Najkra shij pe rshij ce algoritm poshuku yakij doslidzhuye graf shlyahom rozshirennya najperspektivnishih vuzliv yaki obirayutsya vidpovidno do viznachenogo pravila Zagalni vidomosti angl Judea Pearl opisav poshuk Najkrashij pershij vzyavshi yak ocinku vuzla n znachennya deyakoyi ocinki f n yaka vzagali kazhuchi mozhe zalezhati vid opisu vuzla n opisu meti informaciyi yaka zibrana poshukom na danij moment i golovne vid bud yakih dodatkovih znan pro predmetnu galuz Deyaki avtori vikoristovuvali poshuk Najkrashij pershij specialno dlya opisu poshuku z evristikoyu shob sprobuvati peredbachiti naskilki blizko znahodimosya do finalnogo stanu tak sho shlyahi yaki mayut najkrashu evristichnu ocinku rozglyadayutsya pershimi Cej specifichnij tip poshuku nazivayetsya zhadibnim poshukom Najkrashij pershij Efektivnij vibir potochnogo najkrashogo kandidata dlya rozshirennya poshuku yak pravilo realizuyetsya za dopomogoyu Algoritm poshuku A A star ye prikladom optimalnogo poshuku Najkrashij pershij Algoritm Najkrashij pershij chasto vikoristovuyutsya dlya poshuku shlyahu u kombinatornomu poshuku Algoritm1 OPEN Pochatkovij stan 2 poki OPEN ne ye porozhnim povtoryuvati 2 1 Vidaliti najkrashij vuzol z OPEN nazvemo jogo N 2 2 Yaksho N cilovij stan robimo trasuvannya shlyahu nazad do pochatkovogo vuzla cherez zapisi do batkiv vid N i povertayemo shlyah 2 3 Stvoriti spisok nashadkiv vuzla N 2 4 Ocinyuyemo kozhnogo nashadka dodayemo jogo v OPEN i zapisuyemo N yak jogo batka 3 zakinchiti Zvernit uvagu sho cya versiya algoritmu ne ye povnoyu tobto v nomu ne zavzhdi mozhlivo znajti shlyah mizh dvoma vuzlami navit yaksho vin ye Napriklad algoritm zastryaye v cikli yaksho vin zahodit v gluhij kut tobto vuzol z nashadkom yakij ye jogo batkom Algoritm povernetsya do svogo batka dodast tupikovij vuzol nashadka v spisok OPEN i perejde na nogo she raz i tak dali Nastupna versiya rozshiryuye algoritm vikoristovuyuchi dodatkovi spisok CLOSE sho mistit vsi vuzli yaki buli ocineni i ne budut pereglyanuti znovu Ce dozvolyaye uniknuti povtornoyi ocinki bud yakogo vuzla i ne porodzhuvati neskinchenni cikli 1 OPEN pochatkovij stan 2 CLOSE 3 poki OPEN ne ye porozhnim povtoryuvati 3 1 Vidaliti najkrashij vuzol z OPEN nazvemo jogo N dodati jogo v CLOSE 3 2 Yaksho N cilovij stan robimo trasuvannya shlyahu nazad do pochatkovogo vuzla cherez zapisi do batkiv vid N i povertayemo shlyah 3 3 Stvoriti spisok nashadkiv vuzla N 3 4 Dlya kozhnogo nashadka povtoryuvati 3 4 1 Yaksho nashadka nemaye v spisku CLOSE Ocinyuyemo jogo dodayemo jogo v OPEN i zapisuyemo N yak jogo batka 3 4 2 Inakshe yaksho ce novij shlyah krashij nizh poperednij zminyuyemo zapis na batka 4 zakinchiti Takozh zvernit uvagu sho danij psevdokod oboh versij prosto pripinyayetsya koli shlyah ne znajdenij Faktichni realizaciyi zvichajno vimagayut specialnoyi obrobki ciyeyi situaciyi Zhadibnij poshuk Najkrashij pershij Vikoristannya zhadibnogo algoritmu rozshiryuye pershogo nashadka batkiv Pislya generaciyi nashadkiv Yaksho evristichna ocinka nashadka krasha nizh u jogo batka nashadok vstavlyayetsya vpered chergi z batkami povtorno pryamo za nim i cikl perezapuskayetsya V inshomu vipadku nashadok vstavlyayetsya v chergu u misci viznachenomu jogo evristichnoyi vartistyu Potim provoditsya ocinka inshih spadkoyemciv yaksho taki ye u batka Inshi algoritmi poshukuAlgoritm poshuku A Algoritm Dejkstri Poshuk u glibinu Poshuk u shirinu Poshuk z vertannyam Algoritm imitaciyi vidpaluPosilannyaWikibooks Artificial Intelligence Best First Search Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno cherven 2016 Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi