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

Abstract

Розглянуто алгоритми, що дозволяють ландшафту надавати один з можливих варіантів шляху з однієї точки в іншу на географічній карті з урахуванням особливостей прохідності місцевості. Описано методи, які умовно можна розділити на наступні класи: алгоритми пошуку найкоротшого шляху (Дейкстри); алгоритми пошуку субоптимального шляху (A * і його модифікації, зокрема Theta *).

The algorithms that allow the landscape to provide one of the possible variants of the way from one point to another on a geographical map, taking into account the peculiarities of the pertinence of the terrain, are considered. Described methods that can be conventionally divided into the following classes: algorithms for finding the shortest path (Deikstri); algorithms for finding the sub-optimal path (A * and its modifications, in particular Theta *).