A* Алгоритм Пошуку Шляху: Дійсну Дирецію

Дікстра досліджує все. А* має інтуїцію.

Алгоритм Дікстри знаходить найкоротший шлях від стартової точки, розширюючи межу вперед у порядку відстані: він завжди розширює невідвіданий вузол з найменшою на той момент вартістю. Він правильний і повний, але сліпий – він розширює вузли позаду вас, поруч із вами та попереду з однаковою енергією, оскільки не має жодного уявлення, де знаходиться ціль. На відкритій сітці він досліджує диск.

А* (Харт, Нільссон і Рафаель, 1968) змінює лише одну річ. Кожен вузол оцінюється не за вартість досягнення його, а за оцінену вартість всього шляху через нього:

f(n) = g(n) + h(n) g(n) = точна вартість найкращого знайденого досі шляху від стартової точки до n h(n) = ГЕОМЕТРИЧНА оцінка залишкова вартість від n до мети Розширюйте вузол з найменшим f, а не з найменшим g. Це одне заміщення спрямовує пошук у бік цілі: на відкритій сітці диск Дікстри перетворюється на вузький еліпс, що вказує на ціль. Встановіть h = 0 і А* зводиться точно до Дікстри; зробіть h великим і це перетворюється на жадібний пошук найкращого першого, який швидко занурюється у ціль і знаходить погані шляхи.

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

g(n) = the exact cost of the best path found so far from start to n
h(n) = a HEURISTIC estimate of the remaining cost from n to the goal

Допустимість, узгодженість та те, що може вас обійти

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

Більша властивість – узгодженість (трикутник нерівність, також відома як монотонність):

h(n) ≤ cost(n, n') + h(n') для кожної ребра n → n'

h(ціль) = 0

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

h(n) ≤ cost(n, n') + h(n')     for every edge n → n'
h(goal) = 0

Вибір евристичної функції для вашої сітки

Евристична функція повинна точно відповідати правилам руху. Це найпоширеніша причина неточних шляхів і надзвичайно повільних пошуків:

Рух у 4 напрямки (ПЗХ): h = D * (|dx| + |dy|) // Манхеттен

Рух у 8 напрямків (діагоналі коштують D2 ≈ 1.414·D): h = D * (|dx| + |dy|) + (D2 - 2*D) * min(|dx|, |dy|) // октальний

Рух під будь-яким кутом: h = D * sqrt(dx*dx + dy*dy) // Евклідова Використання відстані Манхеттена на сітці з 8 напрямками переоцінює — діагональний крок покриває одиницю dx і одиницю dy за вартістю 1.414, а не 2 — тому евристика неприйнятна, і шлях може бути неправильним. Використання відстані Евкліда на сітці з 4 напрямками є допустимою, але слабкою: вона завжди недооцінює, тому A* досліджує значно більше вузлів, ніж потрібно. Правило таке: евристика повинна бути вартістю найдешевшого шляху, не вражаючи перешкоди, за правилами руху, які ви дозволяєте.

Ще одна неприємність – зв’язки. На безперешкодній сітці величезна кількість шляхів має однакове значення f, і A* досліджує всі вони, створюючи товстий діамант замість лінії. Стандартне рішення – розв'язувати зв’язки на користь прямої лінії — трохи збільшити h на коефіцієнт приблизно (1 + 1/очікувана довжина шляху) або додати невеликий вектор перерізу від початкової до кінцевої точки. Шлях залишається оптимальним у практиці, і досліджувана область драматично стискається.

4-way movement (N/E/S/W)
    h = D * (|dx| + |dy|)                       // Manhattan

8-way movement (diagonals cost D2 ≈ 1.414·D)
    h = D * (|dx| + |dy|) + (D2 - 2*D) * min(|dx|, |dy|)   // octile

any-angle movement
    h = D * sqrt(dx*dx + dy*dy)                 // Euclidean

Реалізація та де саме витрачається час

відкритий = черга за пріоритетом (бінарний куч), з ключовим значенням f початковий = 0; push(початковий, h(початковий)) while (відкритий не порожня): attuale = pop_min(відкритий) // O(log n) якщо attuale є ціллю: поверни reconstruct(cameFrom, attuale) закриті.додати(attuale) для кожного сусіда nb актуального: якщо nb у закритих: continue тимчасове = g[актуальний] + cost(актуальний, nb) якщо (тимчасове < g[nb]): // кращий шлях до nb cameFrom[nb] = актуальний g[nb] = тимчасове push_or_decrease_key(відкритий, nb, тимчасове + h(nb)) Відкрита множина повинна бути чергою за пріоритетом. Лінійний пошук мінімума при кожному вилученні перетворюється на O(n) і є причиною того, що багато реалізацій A*, написаних вручну, працюють дуже повільно. Бінарна куча забезпечує O(log n) вилучень та вставлень і достатня для будь-якої сітки, яку можна намалювати. Ще дві практичні точки: зберігайте g та батьківський узел у плоских масивах з індексами y*w + x замість у хеш-мапі, керованій об'єктами, і якщо ваша куча не має операції зменшення ключа, просто вставте вузол ще раз із кращим f та відкидайте застарілі записи при їх вилученні (перевірте, чи збігається вилучений f із поточним g + h). Це трохи витрачає пам'ять і швидше, ніж підтримувати індекс.

open = priority queue (binary heap), keyed by f
g[start] = 0; push(start, h(start))

while (open not empty):
  current = pop_min(open)                 // O(log n)
  if current is goal: return reconstruct(cameFrom, current)
  closed.add(current)
  for each neighbour nb of current:
    if nb in closed: continue
    tentative = g[current] + cost(current, nb)
    if (tentative < g[nb]):               // a better route to nb
      cameFrom[nb] = current
      g[nb] = tentative
      push_or_decrease_key(open, nb, tentative + h(nb))

Варіанти, які варто знати

Зважений A* f = g + w·h, де w > 1. Недопустимий, але гарантує шлях протягом фактора w від оптимального, а пошук значно швидший. Зазвичай w ≈ 1,2–2.

Jump Point Search (JPS) – на рівномірних сітках пропускає цілі коридори симетричних вузлів без розширення. Забезпечує той самий оптимальний шлях, часто з порядком величини меншою кількістю розширень.

Theta* – дозволяє будь-який кут шляху, дозволяючи будь-якому предкову вузла мати видимість, усуваючи незручну сходинку 45 градусів, яку генерує A* на сітці. Це також вирішує цю проблему безпосередньо в процесі пошуку.

D* Lite – відновлює попередній пошук при зміні карти замість перепланування з нуля — стандартний вибір для робота, який виявляє перешкоди під час руху.

HPA* – ієрархічний: планування на грубій графі кластерів, уточнення всередині кожного кластера. Масштабується до великих карт. Важливо пам’ятати, що шлях, який повертає A* на сітці, є оптимальним для заданої вами графа, що не обов’язково відповідає оптимальному шляху в площині. Шляхи на сітці – це сходи, і рух одиниці виглядає механічним, якщо не провести постобробку — ряд «тяг», який видаляє будь-яку точку шляху, де сусіди можуть бачити один одного.

Weighted A*    f = g + w·h, with w > 1. Inadmissible, but the
               path is guaranteed within a factor w of optimal and
               the search is dramatically faster. w ≈ 1.2–2 is common.

Jump Point     On uniform-cost grids, skips over whole corridors of
Search (JPS)   symmetric nodes without expanding them. Same optimal
               path, often an order of magnitude fewer expansions.

Theta*         Allows any-angle paths by letting a node's parent be
               any ancestor with line-of-sight, removing the ugly
               45° staircase that grid A* produces.

D* Lite        Repairs the previous search when the map changes
               instead of replanning from scratch — the standard
               choice for a robot discovering obstacles as it moves.

HPA*           Hierarchical: plan on a coarse graph of clusters,
               refine inside each cluster. Scales to huge maps.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте A* Pathfinding і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.