ПРОМЕНЕВИЙ АЛГОРИТМ ПОШУКУ ШЛЯХУ НА ГЕКСАГОНАЛЬНОМУ РАСТРІ

Анотація

В статті розглянуто променевий алгоритм пошуку шляху, який в теорії графів застосовується для пошуку шляху між вершинами зв’язного графу. На практиці він використовується для вирішення цілого ряду прикладних задач. Застосовуючи променевий алгоритм пошуку шляху знаходять та будують маршрути від початкової точки до місця призначення у картах та навігаторах на місцевості, при проєктуванні електронних плат мікроконтролерів, в логістиці, картографії, комп’ютерних іграх. Використання штучного інтелекту у безпілотних транспортних засобах актуалізувало застосування променевого алгоритму пошуку шляху, як швидкий і маловитратний спосіб побудови маршрутів в режимі реального часу і в ситуації динамічних змін поточних сценаріїв руху. Особливостями променевого алгоритму пошуку шляху є направлений пошук вздовж вибраних променів, рух променів з обох вершин у напрямку один до одного, побудова шляху від вершини перетину взаємонаправлених променів. Запропоновано застосувати променевий алгоритм пошуку шляху для гексагональних комірок. Характерною особливістю гексагональних комірок є їх шестизв’язна симетрія та найнижче співвідношення периметра до площі серед інших багатокутників (і квадрата в тому числі). Застосовуючи променевий алгоритм пошуку шляху на гексагональних комірках буде збільшено можливі напрямки поширення променю з 4-х до 6-ти. Дослідження поля гексагональних комірок здійснюється у напрямку руху променю, залежно від початкових передумов, що визначаються різницею координат початкової комірки і комірки призначення, до якою моє бути прокладено шлях. Оскільки під час аналізу координат комірок вибираються і аналізуються координати не всіх комірок, а тільки ті, що розміщені на шляху променю, променевий алгоритм пошуку шляху матиме кращу швидкодію під час реалізації, ніж хвильовий алгоритм. Недоліком променевого алгоритму пошуку шляху є те, що не завжди можна знайти шлях між визначеними комірками, хоча варіанти шляху можуть існувати. Також запропоновано представлення поля гексагональних комірок у виді зв’язного графу та перетворення у двовимірну матрицю, для кращої обробки програмними засобами, та для виявлення непрохідних комірок, якщо такі присутні.