Дізнайтесь більше про нові кар'єрні можливості в 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?
