Алгоритми пошуку шляху в графі


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Для новачків Граф – це (спрощено) множина крапок, що називаються “вершинами”, сполучених якимись лініями, що називаються “ребрами” (необов’язково всі вершини сполучені). Можна уявляти собі як міста, сполучені дорогами.

Будь-яке картате поле можна представити у вигляді графа. Вершинами будуть клітини, а ребрами – суміжні сторони клітин.

Наочне уявлення про роботу наведених нижче алгоритмів можна отримати завдяки візуалізації PathFinding.js.

Пошук завширшки

Алгоритм був розроблений незалежно Муром і Лі для різних додатків (пошук шляху в лабіринті та розводка провідників відповідно) в 1959 і 1961 роках. Цей алгоритм можна порівняти з підпалом сусідніх вершин графа: спочатку ми запалюємо одну вершину (ту, з якої починаємо шлях), а потім вогонь за один елементарний проміжок часу перекидається на всі сусідні з нею вершини, що не горять. Те саме відбувається з усіма підпаленими вершинами. Таким чином, вогонь поширюється “завширшки”. В результаті його роботи буде знайдений найкоротший шлях до потрібної клітини.

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

Цей алгоритм названий за іменем творця і був розроблений 1959 р. У процесі виконання алгоритм перевірить кожну з вершин графа, і знайде найкоротший шлях до початкової вершини. Стандартна реалізація працює на зваженому графові – графові, у якого кожен шлях має вагу, тобто “вартість”, яку потрібно буде “заплатити”, щоб перейти по цьому ребру. У стандартній реалізації ваги ненегативні. На картатому полі вага кожного ребра графа приймається однаковою (наприклад, одиницею).

А* (А “із зірочкою”)

Уперше описаний 1968 р. Пітером Хартом, Нільсом Нільсоном і Бертрамом Рафаелем. Даний алгоритм є розширенням алгоритму Дейкстри, прискорення роботи досягається за рахунок евристики – при розгляді кожної окремої вершини перехід робиться в ту сусідню вершину, передбачуваний шлях з якої до шуканої вершини найкоротший. При цьому є безліч різних методів підрахунку довжини передбачуваного шляху з вершини. Результатом роботи також буде найкоротший шлях. Про реалізацію алгоритму читайте в тут.

Пошук за першим найкращим збігом (Best-First Search)

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

IDA* (A* з ітеративним поглибленням)

Розшифровується як Iterative Deeping A*. Є зміненою версією A*, використовує менше пам’яті за рахунок меншої кількості розгорнених вузлів. Працює швидше A* у разі вдалого вибору евристики. Результат роботи – найкоротший шлях.

Jump Point Search

Наймолодший з названих алгоритмів був представлений 2011 р. Є вдосконаленим A*. JPS прискорює пошук шляху, “перестрибуючи” багато місць, які мають бути переглянуті. На відміну від подібних алгоритмів JPS не вимагає попередньої обробки і додаткових витрат пам’яті.


Матеріали про найцікавіші алгоритми ми оглядали в підбірці матеріалів за просунутими алгоритмами і структурами даних.

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *