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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Зміст

Загальні відомості [ред.]

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

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

Жадібний пошук «Кращий — перший» [ред.]

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

Інші алгоритми пошуку [ред.]

Посилання [ред.]


Алгоритми Це незавершена стаття про алгоритми.
Ви можете допомогти проекту, виправивши або дописавши її.
Отримано з http://uk.wikipedia.org/w/index.php?title=Пошук_за_першим_кращим_збігом&oldid=12343101