Загальна схема алгоритму Харта, Нільсона і Рафаеля

 

Узагальненням для значної кількості алгоритмів, заснованих на графах, описаних у цьому розділі, служить алгоритм Харта, Нільсона і Рафаеля, призначений для пошуку найкоротшого шляху між двома вершинами графа. Розглянемо основні ідеї цього алгоритму. Уведемо такі позначення:

s – початкова вершина;

q – цільова вершина;

с (i, j) – довжина ребра, яке з'єднує i -ту та j -ту вершини;

d (і, j) – довжина найкоротшого шляху між і -ю та j -ю вершинами; зокрема, g (n) – довжина найкоротшого шляху від початкової вершини до n -ї; h (n) – довжина найкоротшого шляху від n -ї вершини до цільової; f (n) – довжина найкоротшого шляху від початкової вершини до цільової серед усіх шляхів, які проходять через n -ну вершину; при цьому f (n) = g (n) + h (n);

g′ (n) – оцінка довжини найкоротшого шляху від початкової вершини до n -ї; ця оцінка змінюється, якщо знайдено деякий новий (не обов'язково оптимальний) шлях до n -ї вершини; для оптимального шляху g′ (n) = g (n);

h′ (n) – евристична функція, яка задає оцінку довжини найкоротшого шляху від n -ї вершини до цільової; у здебільшого ми не можемо знати точне значення h (n), але можемо оцінити його виходячи зі специфіки конкретної задачі; приклади таких оцінок будуть наведені далі;

f′ (n) = g′ (n)+ h ′(n) – оцінка для f (n);

L (n) – множина всіх вершин, наступних за вершиною n. Говоритимемо, що алго­ритм розкриває вершину n, якщо він знаходить множину вершин, наступних за нею.

Далі нам будуть потрібні дві робочі множини: OPEN і CLOSE. Загальну схему пошуку найкоротшого шляху на графі від початкової вершини до цільової можна описати так:

1. Сформувати граф пошуку G, який на початку роботи алгоритму складається з однієї початкової вершини s. Занести s до OPEN. Узяти g′ (s) = = g (s) = 0.

2. Сформувати множину CLOSE, яка на початку роботи алгоритму порожня.

3. Якщо множина OPEN порожня, то перейти на вихід: потрібного шляху не існує.

4. Узяти з множини OPEN перший елемент t (відповідно до порядку, встановленого кроком 9). Вилучити t з OPEN та занести до CLOSE.

5. Якщо t – цільова вершина, то досягнуто успіху. Відновити шлях від s до t на основі відновлювальних покажчиків, установлених на кроці 6 – 8, і завершити виконання алгоритму.

6. Розкрити вершину t: отримати множину вершин, наступних за L (t). Додати до графа G всі вершини, які належать L (t), але не належать G, разом із відповідними дугами. Додати ці вершини до OPEN. Для кожної вершини k Î L (m)/ G обчислити оцінки f ′(k) = g′ (k) + h ′(k), узявши g ′(k) = g ′(m) + c (m,k); установити з k до t відновлювальний покажчик.

7. Для кожної вершини n із тих, які потрапили до L (t), але вже належали до OPEN або до CLOSE, переобчислити оцінки g ′(n) = min((g ′(m) + c (m,n)), g ′(n)). Якщо для деякої вершини попередня оцінка, обчислена раніше, зменшилася, перевстановити з неї відновлювальний покажчик до t (у напрямку найкоротшого шляху).

8. Для всіх вершин з L (t), які до цього знаходилися в множині CLOSE, перевстановити відновлювальні покажчики для кожної з вершин, наступних за цими вершинами, у напрямку найкоротшого шляху, а також переобчислити покажчики.

9. Переупорядкувати множину OPEN за зростанням значень f ′.

10. Повернутися на крок 3.

Евристичну функцію h ′ в алгоритмі Харта, Нільсона і Рафаеля можна обирати довільно, і залежно від вибору цієї функції надійність і якість алгоритму можуть істотно змінюватися. Сформульовано три важливі теореми, що встановлюють умови, за яких алгоритм гарантовано матиме ті чи інші бажані властивості.

Алгоритм Харта, Нільсона і Рафаеля називають допустимим, якщо він гарантовано знаходить оптимальний шлях до цільової вершини.

Теорема 1. Алгоритм Харта, Нільсона і Рафаеля допустимий, якщо виконуються такі умови:

· будь-яка вершина або взагалі не має наступників, або має скінченну їх кількість;

· довжина будь-якої дуги перевищує деяку величину e > 0;

· для будь-якої вершини п виконується нерівність h ′(n) £ h (n), тобто евристична функція є оцінкою знизу і не перевищує справжньої відстані до цільової вершини.

Нехай два допустимі алгоритми Харта, Нільсона і Рафаеля А і В відріз­няються лише своїми евристичними функціями h′A та h′B. Говорять, що алгоритм А є більш інформований, ніж алгоритм В, якщо для будь-якої нецільової вершини h′A (n) > h′B (n).

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

Інакше кажучи, теорема стверджує, що більш інформований алгоритм розкриває не більше вершин, ніж менш інформований, і тому він є більш оптимальний за швидкодією.

Інша важлива вимога до евристичної функції полягає в її консистентності (від англ. consistency). Евристичну функцію h ′(n) називають консистентною, якщо для будь-яких двох вершин t i п, таких що t є безпосередньо наступна за n, виконується нерівність h ′(n)– h ′(m)£ c (n,m).

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

Теорема 3. Якщо евристична функція, застосована в алгоритмі Харта, Нільсона і Рафаеля, є консистентна, то алгоритм розкриє будь-яку вершину не раніше, ніж знайде оптимальний шлях до неї.

Інакше кажучи, якщо виконується умова консистентності, то в момент, коли алгоритм розкриває вершину n, для неї виконується рівність g ′(n)= g (n).

Консистентність евристичної функції має дуже велике значення. Вона дозволяє не повертатися до тих вершин, які вже були проаналізовані й потрапили до множини CLOSE.

Якщо евристична функція не застосовується, тобто якщо h ′(n) º 0 і відповідно f ′(n)= g ′(n), маємо алгоритм Дейкстри. Теорема 2 стверджує, що введення належної евристичної функції дозволяє здебільшого прискорити роботу алгоритму.

Якщо взяти g ′(n)º 0, утвориться алгоритм Дорана і Мічі. Цей алгоритм у деяких випадках дозволяє швидко знайти шлях до цільової вершини. Але гарантії того, що цей шлях буде оптимальним, немає. Більше того, не гарантується навіть знаходження хоч якого-небудь шляху до цільової вершини.

Проілюструємо методику застосування алгоритму Харта, Нільсона і Рафаеля до розв’язання головоломки „гра у 8”. Цю головоломку можна розглядати як спрощений варіант відомої головоломки С. Ллойда „гра у 15”. У коробці розміром 3x3 лежить 8 фішок, пронумерованих цифрами від „1” до „8”; одне місце є пусте (рис. 1).

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

 

 

 

Рис. 2. Цільова позиція

Рис. 1. Головоломка „гра у 8”

 

 

Не будь-яку початкову позицію можна з додержанням правил гри перевести до цільової. Можна показати, що це здійсненне тільки для тих позицій, які переходять до цільової за парну кількість перестановок. Перестановкою називають таку операцію: дві фішки виймають із коробки та міняють місцями. Утім, якщо для певної початкової позиції задача не має розв'язку, це буде з'ясовано в ході роботи алгоритму.

Розв'язання задачі можна автоматизувати на основі планування в просторі станів. Побудова графа станів є очевидна. Кожна вершина графа відповідає певній позиції; якщо існує хід, який дозволяє перейти від позиції А до позиції В, то з А до В йде орієнтована дуга.

Так, у позиції, показаній на рис. 3, можна зробити два ходи:

– пересунути фішку „8” вправо;

– пересунути фішку „3” вгору.

Тому відповідний фрагмент графа станів має такий вигляд, як на рис. 3.

Тепер, коли граф станів побудовано, для розв'язання задачі можна застосувати будь-який алгоритм пошуку найкоротшого шляху. Для алгоритму Харта, Нільсона та Рафаеля необхідно задати конкретні евристичні функції, наприклад:

· h ′₁ – кількість фішок, які стоять не на своїх місцях;

· h ′₂ – сума відстаней усіх фішок до свого місця, тобто сума ходів, які потрібно зробити, щоб перевести кожну фішку на своє місце за умови, що інших фішок на дошці немає.

Можна побачити, що обидві евристичні функції допустимі, тобто є оцінками знизу. Обидві функції також є консистентні. Також очевидно, що алгоритм, який застосовує функцію h ′₂, є більш інформований, ніж той, який застосовує функцію h ′₁.

Рис. 3. Фрагмент графа станів