A* (читається «А-зірка») — алгоритм пошуку в графі, що знаходить найкоротший шлях між двома вузлами, поєднуючи точну вартість пройденого шляху g (як у Дейкстри) з евристичною оцінкою відстані h, що залишилась. Кожному вузлу присвоюється пріоритет f = g + h. Розроблений у 1968 році Хартом, Нільссоном та Рафаелем, A* лежить в основі навігації персонажів у відеоіграх, планування маршрутів роботів і пошуку оптимальних маршрутів у картографічних сервісах. При допустимій евристиці — тобто такій, що ніколи не переоцінює реальну вартість, — алгоритм гарантовано повертає оптимальний шлях.
Ця симуляція дає змогу порівнювати A*, Дейкстру (h = 0) та жадібний пошук за найкращим першим (g = 0) на сітці зі стінами і ділянками з підвищеною вартістю (×5). Вибирайте евристику (Манхеттенська, Евклідова або Чебишевська), вмикайте діагональні переміщення і спостерігайте за розширенням фронту крок за кроком у режимі реального часу.
Що означає f = g + h?
В A* кожен вузол у відкритому наборі отримує оцінку f(n) = g(n) + h(n), де g(n) — точна вартість найдешевшого знайденого шляху від старту до вузла n, а h(n) — евристична оцінка вартості від n до цілі. Алгоритм завжди розширює вузол із найменшим f, тому якщо h є допустимою, перше розширення цільового вузла гарантує оптимальний шлях.
Що таке допустима евристика?
Евристика h є допустимою, якщо вона ніколи не переоцінює справжню вартість досягнення цілі — формально h(n) ≤ h*(n) для всіх n. Манхеттенська відстань є допустимою для 4-зв'язної сітки; Евклідова — для будь-якої. Недопустима евристика може пришвидшити A*, але ризикує повернути неоптимальний шлях.
Чим A* відрізняється від алгоритму Дейкстри?
Алгоритм Дейкстри встановлює h = 0 і розширює вузли в порядку їхньої точної вартості від початку, рівномірно поширюючись у всіх напрямках. A* додає евристику, щоб спрямовувати пошук до цілі, розширюючи значно менше вузлів. На відкритій сітці без перешкод A* з Манхеттенською відстанню може скоротити кількість розширень на 50–90% порівняно з Дейкстрою.
Жадібний пошук встановлює g = 0 і спрямовується до вузла, що виглядає найближчим, без урахування реальної вартості шляху. Це дуже швидко у відкритому просторі, але алгоритм може потрапити в пастку дорогого рельєфу або знайти шлях, значно довший за оптимальний. У найгіршому випадку знайдений шлях може бути довільно гіршим.
Манхеттенська відстань підходить для 4-напрямкового руху — вона точно підраховує мінімальну кількість кроків. Евклідова відстань доречна при дозволених діагональних переміщеннях із вартістю √2. Відстань Чебишева (max(|Δx|, |Δy|)) є правильним вибором, коли всі 8 напрямків коштують однаково, як у багатьох стратегічних іграх.
Зважені клітинки позначають важкопрохідний рельєф: входження в таку клітинку коштує 5 замість 1. A* і Дейкстра коректно враховують ваги й часто обходять кілька зважених клітинок замість прямого проходу. Жадібний пошук ігнорує вартості й може пройти прямо через дорогий рельєф.
У найгіршому випадку A* має складність O(b^d) за часом і пам'яттю, де b — коефіцієнт розгалуження, а d — глибина оптимального рішення. При узгодженій евристиці кожен вузол розширюється не більше одного разу, що дає O(V log V) на скінченному графі з V вершинами — ту саму асимптотику, що й Дейкстра з бінарною купою.
Генератор лабіринту створює досконалий лабіринт із рівно одним шляхом між будь-якими двома клітинками. Вузькі коридори зводять нанівець перевагу евристики A* — при єдиному валідному маршруті всі алгоритми розширюють приблизно однакову кількість вузлів.
Зелений — початковий вузол, червоний — ціль. Сині клітинки утворюють поточний фронт (відкритий набір), темно-сині — відвідані (закритий набір), жовтий підсвічує вузол, що розширюється. Зважені клітинки коричневі. Знайдений шлях трасується лаймовим зеленим, а точна вартість відображається на панелі статистики.
Так — A* працює на будь-якому графі з невід'ємними вагами ребер, якщо існує допустима евристика. Реальні застосування: планування руху роботизованих маніпуляторів у просторі конфігурацій, маршрутизація в мережах і синтаксичний аналіз природної мови. Сітка тут — лише найнаочніший спосіб представлення загального алгоритму.
Лічильник показує, скільки разів алгоритм вилучав вузол із фронту й обробляв його сусідів — це основна міра ефективності A*. Менший показник означає, що евристика добре спрямовує пошук. На сітці 30×30 хороша евристика часто знаходить оптимальний шлях, розширивши менше 100 вузлів, тоді як Дейкстра може обробити всі досяжні клітинки.
Ця симуляція показує, як алгоритм A* шукає найкоротший шлях на сітці. Кожному вузлу присвоюється оцінка f(n) = g(n) + h(n), де g — це вже пройдена відстань від старту, а h — евристична оцінка відстані до цілі; першим завжди розширюється вузол із найменшим f. Перемкнувши алгоритм на Дейкстру, ви обнуляєте h, а режим «Жадібний» повністю ігнорує g — можна порівняти три способи розв'язати той самий лабіринт крок за кроком.
Кольорова сітка показує пошук у реальному часі: сині клітинки — це відкритий фронт, темно-сині — вже розглянуті (закриті) вузли, а жовта клітинка — та, що обробляється саме зараз. Коли ціль досягнута, знайдений маршрут трасується лаймовим кольором, а панель статистики показує кількість розгорнутих вузлів і повну вартість шляху.
Оберіть алгоритм і евристику у випадаючих списках, малюйте стіни або «важку» місцевість (×5) інструментами малювання, або перетягуйте позначки старту й цілі прямо на сітці. Прапорець «Дозволити діагональні ходи» перемикає між 4- і 8-напрямковим рухом, «Показувати значення g/h/f» показує числа прямо на клітинках, а кнопки автозапуску, кроку, генерації лабіринту та скидання керують відтворенням.
Алгоритм A* опублікували ще 1968 року Піт Гарт, Нільс Нільссон і Бертрам Рафаель, і попри свій вік він досі є стандартним вибором для пошуку шляху у відеоіграх, робототехніці та навігаційних сервісах — з допустимою евристикою він гарантовано не розглядає жодного зайвого вузла.
Кожна евристика по-своєму оцінює h(n) — відстань до цілі, — і це змінює форму фронту пошуку. Манхеттенська відстань точна для руху лише вгору/вниз/вліво/вправо; Евклідова (пряма лінія) підходить для діагональних переміщень; Чебишевська (максимум різниць по осях) підходить, коли всі 8 напрямків коштують однаково. Заниження оцінки зберігає оптимальність шляху, але змушує розглядати більше вузлів; завищення пришвидшує пошук ціною можливо не найкоротшого маршруту.
Вхід у зважену клітинку коштує 5 замість 1, тож вона піднімає g(n) для будь-якого шляху, що через неї проходить. Оскільки A* і Дейкстра завжди мінімізують сумарну вартість, вони охоче обійдуть скупчення важких клітинок, якщо це дешевше загалом — лише жадібний пошук, який ігнорує g, може пройти прямо крізь дорогу територію.
Сині клітинки перебувають у відкритій множині — вже знайдені, але ще не розглянуті — і зберігаються в бінарній купі за ключем f, з розв'язанням нічиїх за меншим h. Темно-сині клітинки закриті: їхні сусіди вже перевірені, а значення g остаточне. Жовтим підсвічується єдиний вузол, вилучений із купи на поточному кроці.
Генератор лабіринту прокладає «ідеальний» лабіринт із рівно одним шляхом між будь-якими двома клітинками за допомогою рандомізованого рекурсивного backtracker-алгоритму, тож для евристики немає жодних коротких шляхів. Жадібний пошук завжди мчить до клітинки, що виглядає найближчою по прямій, і часто заходить у глухі кути, тоді як A* і Дейкстра методично повертаються й пробують інший варіант.
Так — коли увімкнено «Дозволити діагональні ходи», діагональний крок коштує квадратний корінь із двох замість 1, що відповідає його реальній евклідовій довжині, а симуляція забороняє «зрізати кут» між двома сусідніми стінами. У цьому режимі евристика також переходить на октильну формулу відстані, щоб лишатися допустимою для 8-напрямкового руху.