Ця симуляція показує, як п’ять алгоритмів пошуку на графі знаходять маршрут через сітку клітинок. Кожна вільна клітинка стає вузлом, з’єднаним із чотирма ортогональними сусідами, а стіни блокують рух. A* ранжує клітинки за f(n) = g(n) + h(n), де g — реальна вартість від старту, а h — евристична оцінка відстані до цілі. Dijkstra визначає h як нуль, Greedy Best-First використовує лише h, а BFS розгортає звичайну чергу шар за шаром.
Селектор алгоритмів перемикає між A* (Манхеттен), A* (Євклід), Dijkstra, Greedy Best-First та BFS. Режими малювання дають змогу розміщувати стіни, початок і кінець або стирати, а повзунок швидкості задає, скільки кроків пошуку виконується за один кадр анімації. Ви також можете крокувати вручну, очищати пошук, скидати сітку або згенерувати лабіринт методом рекурсивного відкоту. Пошук шляху лежить в основі GPS-навігації, руху у відеоіграх і маршрутизації складських роботів.
Що саме показує ця симуляція пошуку шляху?
Вона розглядає сітку як граф і анімує, як обраний алгоритм веде пошук від стартової клітинки до кінцевої, забарвлюючи відкритий набір, відвідані (закриті) клітинки та остаточний найкоротший шлях. Живі лічильники показують кількість відвіданих клітинок і довжину шляху, щоб ви могли порівняти ефективність із оптимальністю.
Як тут працює алгоритм A*?
A* тримає чергу з пріоритетом, впорядковану за f(n) = g(n) + h(n). Значення g — це кількість кроків від старту, а h оцінює залишок відстані до цілі. На кожному кроці він розгортає клітинку з найменшим f, що спрямовує пошук до цілі й водночас гарантує найкоротший шлях, коли евристика ніколи не переоцінює відстань.
Яка різниця між Манхеттенською та Євклідовою версією A*?
Обидві використовують ту саму формулу f = g + h, але різну евристику. Манхеттенська відстань сумує горизонтальний і вертикальний розриви (|dr| + |dc|), що точно відповідає сітці з чотирма напрямками. Євклідова відстань використовує пряму лінію (гіпотенузу), яка на сітці без діагонального руху занижує відстань більше, тому може дослідити трохи більше клітинок.
Dijkstra — це A* із h, рівним нулю, тому він досліджує лише за накопиченою вартістю і розгортається рівномірно в усі боки. Greedy Best-First використовує f = h, прямуючи до цілі лише за оцінкою, що швидко, але стіни можуть обманути його й призвести до довшого маршруту. BFS використовує просту чергу «першим увійшов — першим вийшов», а не чергу з пріоритетом.
A* (з допустимою евристикою), Dijkstra та BFS усі повертають гарантовано найкоротший шлях на цій сітці з однаковою вартістю, бо кожен крок коштує одиницю. Greedy Best-First не гарантує оптимальності; він часто швидко знаходить маршрут, але може зробити довший гак навколо перешкод, бо ігнорує вже сплачену вартість.
Чіпи Wall, Start, End і Erase задають, що робить клік або перетягування по сітці. Wall блокує клітинки, Start і End переміщують зелену та червону кінцеві точки, а Erase очищає стіни. Повзунок швидкості обирає, скільки кроків пошуку виконується за кадр анімації — від одного кроку до ста, дозволяючи спостерігати повільно або розв’язати миттєво.
Сині напівпрозорі клітинки — це відкритий набір, ще в черзі на дослідження, темно-сині клітинки — закритий набір вже відвіданих, а жовтим позначено відновлений найкоротший шлях. Порівняння розміру закритої області між алгоритмами робить їхню ефективність наочною: A* зазвичай відвідує набагато менше клітинок, ніж Dijkstra, щоб досягти тієї самої цілі.
Кнопка «Згенерувати лабіринт» заповнює сітку стінами, а потім запускає рекурсивний відкат. Починаючи з кутової клітинки, він прокладає проходи по дві клітинки за раз у випадково перетасованому порядку, руйнуючи стіну між клітинками, які з’єднує. Результат — ідеальний лабіринт із рівно одним шляхом між будь-якими двома вільними клітинками.
Так. Щоразу, коли клітинка досягається вперше, алгоритм записує, від якого сусіда він прийшов, у мапі попередників. Коли кінцеву клітинку вийнято з черги, маршрут відбудовується, рухаючись цими батьківськими посиланнями назад від цілі до старту, а потім розвертається, щоб дати прямий шлях, підсвічений жовтим.
A* та Dijkstra лежать в основі планувальників маршрутів GPS і карт, руху неігрових персонажів у відеоіграх та навігації складських і кур’єрських роботів. Ті самі ідеї пошуку на графах поширюються на маршрутизацію мереж, розв’язання головоломок і логістику. A* уперше розробили у 1968 році в Стенфордському дослідному інституті для робота Shakey.
Алгоритми пошуку шляху знаходять найкоротший маршрут між двома точками на сітці клітинок, оминаючи перешкоди дорогою. Вони — рушій покрокової навігації GPS, руху персонажів у відеоіграх та планування маршрутів складських роботів. Найцікавіше — спостерігати, як різні стратегії балансують між швидкістю та оптимальністю: одні досліджують широко й гарантують найкращий шлях, інші мчать до цілі, але можуть потрапити в глухий кут.
f(n) = g(n) + h(n) — A* оцінює кожну клітинку за f, де g(n) — фактична вартість від старту, а h(n) — евристична оцінка відстані до цілі. Дейкстра використовує h = 0 (лише вартість), а Greedy Best-First — f = h (лише оцінку).
A* винайшли 1968 року Пітер Гарт, Нільс Нільссон і Бертрам Рафаель у Стенфордському дослідницькому інституті під час роботи над Shakey — одним із перших мобільних роботів, здатних осмислювати власні дії.
Порівняйте алгоритми пошуку шляху у реальному часі: A* з евристикою, Дейкстру для гарантовано найкоротшого шляху та BFS для незваженого графу. Малюйте перешкоди і дивіться, як вони справляються.
A* поєднує реальну вартість g(n) з евристичною оцінкою h(n) майбутньої вартості: f(n) = g(n) + h(n). З допустимою евристикою A* гарантовано оптимальний. Дейкстра — особливий випадок A* без евристики.
Розставляйте перешкоди, початкову та кінцеву точки. Виберіть алгоритм і дивіться, як поширюється пошук. Порівняйте кількість відвіданих вузлів для кожного алгоритму.
A* використовується в мільйонах відеоігор і Google Maps. Сучасний навігаційний алгоритм Google обробляє мільйони вузлів — але суть та сама: f(n) = g(n) + h(n), придумана у 1968 р.