Алгоритм Дейкстри

End

Begin

 

s.parent := nil; // s is a node for the start push s on Open

 

whileOpen is not emptydo beginpop node n from Open

 

ifn is a goal nodethen begin(9.1)construct path

 

 

result := true; // success exit;

 

end;

 

foreach successor n' of ndo begin ifn' has been visited already,

 

then continue;n'.parent := n; push n' on Open

 

end;end;

 

result := false; // no path found

 

На рис. 9.4 показано результат роботи алгоритму (9.1).

 


Бачимо, що алгоритм дійсно знаходить шлях обходу перешкод і цей шлях гарантовано оптимальний (найкоротший) за умови, що рух усіма дозволеними елементами карти має однакову «вартість». Проте є декілька проблем, пов’язаних з алгоритмом «пошуку в ширину». По-перше, пошук здійснюється в усіх напрямках, замість того, щоб проводити його за напрямком до цілі. По-друге, не всі кроки мають однакову довжину. Перехід на сусідній елемент по діагоналі довший, ніж перехід під прямим кутом.

 

Рис. 9.4. Робота алгоритму«пошуку в ширину»

 

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

 

Рис. 9.5. Двонапрямлений пошук у ширину

 

 


Подібні методи поліпшення можуть використовуватись і для інших алгоритмів пошуку.

 

9.4. Метод «пошуку в глибину»

 

Логічною альтернативою методу «пошуку в ширину» став метод «пошуку в глубину» (depth-first search), за якого пошук ведеться переважно в бік віддалення від розглядуваного вузла, а не в бік пошуку в сусідніх до нього вузлах. Очевидно, що в цьому випадку потрібні додаткові умови припинення такого процесу, наприклад, за досягнення заданої глибини пошуку.

 

З погляду реалізації цей алгоритм відрізняється від методу «пошуку в ширину» (9.1) лише тим, що замість черги FIFO використовують чергу типу «останній зайшов, перший вийшов» (LIFO, last-in-first-out).

 

 

Дейкстра (Edsger Wybe Dijkstra, 1930–2002) розробив класичний алгоритм обходу графів із зв’язками, що мають різні вагові коефіцієнти. На кожному кроці алгоритм шукає не оброблений раніше вузол, найближчий до початкового, обробляє його «сусудів» і встановлює їх відстані від початкового. Такий підхід має деякі переваги перед методом «пошуку в ширину». По-перше, враховується відстань від одного вузла до іншого, а по-друге, поновлюється інформація про відстань до розглядуваного вузла, якщо кращу траєкторію було знайдено. Реалізація алгоритму Дейкстри відрізняється від методу «пошуку в ширину» тільки тим, що замість черги FIFO використовують пріоритетну чергу, в якій спершу обробляється вузол, який має найкращу «вартість» у розумінні відстані від початкового вузла. Результат роботи алгоритму подано на рис. 9.6.

 


 

 

Рис. 9.6. Алгоритм Дейкстри

 

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

 

9.6. «Зірка пошукових алгоритмів» – А*

 

Найбільш успішним із усіх алгоритмів пошуку оптимальних шляхів обходу перешкод є алгоритм A* (вимовляється як «ей-стар»). Евристичний пошук оцінює кожен вузол пропорційно до ефективності траєкторії, що проходить через нього. Типова формула для оцінювання рейтингу вузла має такий вигляд:

 

f (n)= g (n)+ h(n),

 

де f(n) – рейтинг ефективності, що присвоюється вузлу n; g(n) – найбільш ефективна «вартість» шляху з початкового вузла в даний; h(n) – евристична оцінка «вартості» прямування з даного вузла в цільовий.

 

Наведемо реалізацію алгоритму A*. functionAStarSearch : Boolean;var

 

n, n’, s : node;

 

Open : priorityqueue; Closed : list;