Алгоритм Дейкстри. Дейкстра (Edsger Wybe Dijkstra, 1930–2002) розробив класичний алгоритм обходу графів із зв’язками, що мають різні вагові коефіцієнти

Дейкстра (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;

Begin

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

s.g := 0; // s is the start node

s.h := GoalDistEstimate( s ); s.f = s.g + s.h;

push s on Open

whileOpen is not emptydo begin

pop node n from Open

ifn is a goal nodethen begin

construct path

result := true; // success

exit;

End;

foreach successor n’ of ndo begin

newg := n.g + cost(n,n’);

if(n’ is in Open or Closed)andn’.g <= newg

then continue;

n’.parent := n; n’.g := newg;

n’.h := GoadDistEstimate( n’ ); n’.f := n’.g + n’.h;

ifn’ is in Closedthenremove n’ from Closed;if

n’ is not in Openthenpush n' on Open;

end;

push n on Closed

end;

result := false; // no path found

End

Алгоритм A* має декілька цікавих властивостей:

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

– кількість обчислень евристичної функції мінімальна. Це означає, що ніякий інший алгоритм, що використовує ту ж саму функцію h(n),не обробить менше вузлів,ніж алгоритмA*.

Приклад роботи алгоритму A* для розглянутої задачі подано на рис. 9.7.

Рис. 9.7. Результат роботи алгоритмуA*

9.7. Різні форми задання простору пошуку

Було показано роботу алгоритмів з дискретними картами, зображуваних у вигляді двовимірного прямокутного масиву даних. Але у реальних застосуваннях таке подання не завжди відповідає дійсності. Однак є декілька способів перетворення простору пошуку до вигляду, придатного для пошукових алгоритмів.

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