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

Abstract

The work is devoted to the comparative analysis of algorithmic approaches to solving the problem of finding the shortest route in weighted graphs. The evolution of methods from classical brute-force algorithms to modern heuristic strategies is investigated. The computational complexity and functional features of Dijkstra's algorithm and the A* (Astar) algorithm are analyzed. The influence of the choice of heuristic function on the algorithm convergence speed and the optimality of the found solution is considered. The areas of appropriate use of each method depending on the topology of the studied space and memory resource requirements are determined.

Роботу присвячено порівняльному аналізу алгоритмічних підходів до вирішення задачі пошуку найкоротшого маршруту в зважених графах. Досліджено еволюцію методів від класичних алгоритмів повного перебору до сучасних евристичних стратегій. Проаналізовано обчислювальну складність та особливості функціонування алгоритму Дейкстри та алгоритму А* (А-зірка). Розглянуто вплив вибору евристичної функції на швидкість збіжності алгоритму та оптимальність знайденого рішення. Визначено сфери доцільного використання кожного з методів залежно від топології досліджуваного простору та вимог до використання ресурсів пам'яті.