Page 110 - 6109

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

€
Вкажемо властивості А-алгоритма. Якщо для всіх вершин ( ) 0h n  , то А-
алгоритм відповідатиме алгоритму рівних цін. В цьому випадку гарантується
знаходження оптимального шляху, але ефективність пошуку буде низькою, і
якщо простір пошуку буде нескінченний, то пошук просто не здійснимо.
А-алгоритм не дає гарантії, що знайдений шлях буде оптимальним. Шлях
може бути не оптимальним у випадку, якщо оцінка витрат на шляху з вершини
€
і в цільову вершину буде перебільшена (переоцінена), тобто якщо ( )h n  h ( )n .
А-алгорітм забезпечить пошук оптимального шляху, якщо виконується
умова
€
h ( )n  h ( )n (11.1)
Алгоритм, що враховує умову (2.1), називають А*-алгоритмом або
гарантуючим алгоритмом. А*-алгоритм недооцінює витрати на шляху з
проміжної вершини в цільову вершину або оцінює їх правильно, але ніколи не
переоцінює.
Нехай А1* і A2* – довільні гарантуючі алгоритми і на всіх вершинах
€
€
h ( )n  h ( )n . Тоді інформованість А1* вище, ніж А2*. Говорять, що в цьому
1 2
випадку А1* має більшу евристичну силу, ніж А2*. Евристично більш сильний
алгоритм А1* більшою мірою скорочує простір пошуку.
Ефективність пошуку за допомогою А*-алгоритма може знижуватися
через те, що вершина, що знаходиться в списку Closed, може потрапляти назад
в список Open і потім повторно розкриватися. Наступний приклад демонструє
випадок багатократного розкриття вершин (рис.11.1).

110