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

Abstract

Метою роботи є розробка системи побудови оптимального шляху з обмеженням максимальної протяжності, через точки різної вартості. Необхідно набрати якомога більше балів проходячи через різні точки лише по одному разу. Інформація про положення та вартість точок отримується за допомогою розпізнавання зображення карти для змагань. Об’єктом дослідження є карти для змагань з рогейну. Використано методи розпізнавання градієнтним перетворенням Хафа та розпізнавання чисел за допомогою OCR. Проведено дослідження з методами обходу на графах, пошуком оптимального шляху з додатковими параметрами. У результаті роботи здійснена програмна реалізація розпізнавання карти, для визначення координат КП та їх вартості, на підставі яких побудовано граф. Розроблено алгоритм видалення надлишкових ребер із графа. Також реалізовано алгоритм пошуку оптимального шляху по отриманим даним.