Page 107 - 6109

While ОРЕN < >'порожній список' Dо
n:=First(Open);
If n='цільова вершина' Тhen Вихід(УСПІХ);
Перемістити вершину n із списку Open в Сlosed;
Розкрити вершину n, для кожної дочірньої вершини n i
обчислити вартість g^(n, n i);
Помістити дочірні вершини, яких немає в списках Open і
Сlosed, в список Open, пов'язавши з кожною вершиною покажчик на
вершину n і покласти g^(n i)= g^(n, n i);
Для кожної з дочірніх вершин, які вже містяться в списку
Open, порівняти поточну вартість g^(n, n i) з раніше обчисленим
значенням вартості g^(n i), що зберігається в списку Open, якщо
g^(n,n i)<g^(n i), то встановити g^(n i) = g^(n, n i). Забезпечити
вказані дочірні вершини покажчиками на вершину n;
Упорядкувати список Open за збільшенням вартості;
Епd;
Вихід(НЕВДАЧА);
Еnd.
В той момент, коли розкривається деяка вершина n, оптимальний шлях до

цієї вершини вже знайдений, тобто €( )g n  g ( )n . Іншими словами, якщо
вершина вже знаходиться на початку списку Open, то для неї неможливо знайти
більш дешевший шлях. Отже, переклад вершини в список Сlosed є остаточним.
Розглянута процедура пошуку гарантує знаходження шляху мінімальної
вартості, якщо граф кінцевий і існує шлях з початкової вершини в цільову
вершину. Проте сам процес пошуку не є оптимальним, оскільки пошук
виконується без урахування положення цільових вершин.

11.4 Евристичний пошук

Основна ідея евристичного пошуку полягає у використовуванні
додаткової інформації для управління процесом пошуку. Ця додаткова
інформація формується на основі емпіричного досвіду, припущень і інтуїції
дослідника, тобто евристик. Використовування евристик дозволяє скоротити
кількість варіантів, що проглядаються, при пошуку рішення задачі, що веде до
більш швидкого досягнення мети.
В алгоритмах евристичного пошуку список відкритих вершин
упорядковується за збільшенням деякій оцінній функції, формованій на основі
евристичних правил. Оцінна функція може включати дві складові, одна з яких
називається евристичною і характеризує близькість поточної і цільової вершин.
Чим менше значення евристичної оцінної функції, тим ближче дана вершина до
цільової вершини. Залежно від способу формування оцінної функції виділяють
наступні алгоритми евристичного пошуку: алгоритм «підйому на гору»,
алгоритм глобального обліку відповідності мети, А-алгоритм.

11.4.1 Алгоритм "підйому на гору"

Алгоритм здійснюється цілеспрямований пошук у напрямі найбільшого
€
убування оцінної функції ( )h n . Дана функція забезпечує оцінку (прогноз)
вартості найкоротшого шляху від поточної вершини п до найближчої цільової

107