Пошук за першим найкращим збігом

По́шук «Найкра́щий — пе́рший» — це алгоритм пошуку, який досліджує граф шляхом розширення найперспективніших вузлів, які обираються відповідно до визначеного правила.

Загальні відомості

Джудеа Перл (англ. 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. закінчити

Також зверніть увагу, що даний псевдокод, обох версій, просто припиняється, коли шлях не знайдений. Фактичні реалізації, звичайно, вимагають спеціальної обробки цієї ситуації.

Жадібний пошук «Найкращий — перший»

Використання жадібного алгоритму розширює першого нащадка батьків. Після генерації нащадків: Якщо евристична оцінка нащадка краща, ніж у його батька, нащадок вставляється вперед черги (з батьками повторно прямо за ним), і цикл перезапускається. В іншому випадку, нащадок вставляється в чергу (у місці, визначеному його евристичної вартістю). Потім проводиться оцінка інших спадкоємців (якщо такі є) у батька.

Інші алгоритми пошуку

Посилання

Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.