ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РАЗЛИЧНЫХ АЛГОРИТМОВ ПОИСКА ПУТЕЙ НА ГРАФАХ

АННОТАЦИЯ

В статье рассматривается сравнительная эффективность трех алгоритмов поиска кратчайшего пути в графах: A*, Dijkstra и BFS (c добавленной эвристикой). Для оценки производительности были сгенерированы тестовые графы различного размера (от 10^3 до 10^6 вершин). Проведены эксперименты на локальном компьютере с процессором Intel Core i7‑10750H и 24 ГБ оперативной памяти под управлением Windows 10×64. Замерялись время выполнения поиска и используемая память, а также оценивалось отклонение полученного пути от оптимального. Результаты показывают, что A* при правильно выбранной эвристике показывает хорошую производительность на плотных графах, в то время как Dijkstra оказывается эффективнее при отсутствии надежной эвристики, а BFS с эвристикой (GBFS) может опережать A* на малых графах, но иногда выдавать неоптимальные решения. Предложены рекомендации по выбору алгоритма поиска в зависимости от размера графа и структуры связности.

ABSTRACT

This paper presents a comparative study of three pathfinding algorithms in graphs: A*, Dijkstra, and BFS with heuristics. Various test graphs with up to 10^6 vertices were generated to evaluate performance on a local computer (Intel Core i7‑10750H, 24 GB RAM, Windows 10×64). We measured execution time, memory usage, and the deviation of the found path from the optimal solution. The results indicate that A* with a proper heuristic achieves high efficiency in dense graphs, while Dijkstra is more suitable when a good heuristic is unavailable. BFS with a heuristic (GBFS) can outperform A* in small graphs but sometimes yields suboptimal paths. We provide recommendations for selecting an algorithm depending on graph size and connectivity structure.

Ключевые слова: алгоритмы поиска пути, A*, Dijkstra, BFS, граф, производительность, эвристика.

Keywords: pathfinding algorithms, A*, Dijkstra, BFS, graph, performance, heuristic.

ВВЕДЕНИЕ

Задача поиска кратчайшего пути в графах является одной из фундаментальных основ в области теоретической информатики и находит широкое практическое применение в транспорте, робототехнике, геоинформационных системах и многих других производственных сферах [3]. В частности, в робототехнике алгоритмы поиска кратчайших путей [3] используются при планировании маршрутов мобильных роботов и беспилотных транспортных средств, чтобы оперативно и надежно прокладывать путь в условиях динамических или малоизвестных окружений. В геоинформационных системах подобные исследовательские методы применяются при определении оптимальных маршрутов на картах, учитывая дорожные ограничения и трафик, а также при аналитике сетевых инфраструктур. Среди наиболее известных подходов к решению задачи поиска кратчайшего пути выделяют классический алгоритм Дейкстры (Dijkstra) [4], алгоритм A* [5], [8], использующий эвристическую функцию для более целенаправленного поиска, а также поиск в ширину (BFS) [1], который нередко модифицируется под эвристический вариант (GBFS), что делает его более быстрым в определенных условиях [1], [7]. Существуют и дополнительные расширения, например D* [6] или методы «онлайн-поиска» в реальном времени [7], однако в рамках данной работы акцент сделан на классических алгоритмах (A*, Dijkstra, BFS), которые остаются наиболее распространенными в учебной и прикладной литературе [1], [9]. На практике выбор алгоритма зависит от структуры графа (плотность и тип ребер, равномерность весов), наличия эвристики, доступных ресурсов по памяти и времени, а также требований к оптимальности результата.

В данной статье автор проводит комплексный анализ трех алгоритмов (A*, Dijkstra и BFS с эвристикой) на наборе тестовых графов с размерностью от 10^3 до 10^6 вершин. При этом учитываются временная и пространственная эффективность, а также отклонение найденных решений от реального оптимума. Проведенные эксперименты позволяют не только выявить сильные и слабые стороны рассмотренных методов, но и дать конкретные рекомендации по выбору алгоритма в зависимости от размера и структуры графа, а также наличия подходящей эвристики.

Цель исследования

Основная цель настоящей работы – провести комплексное экспериментальное сравнение трех алгоритмов поиска кратчайшего пути: A* [5], [8], Dijkstra [4] и BFS с эвристикой [1]. Для этого планируется оценить, в каких условиях каждый из алгоритмов показывает наилучшие результаты с точки зрения времени выполнения и потребления оперативной памяти. Исследование охватывает широкий диапазон размеров графов – от 10^3 до 10^6 вершин, что позволяет проследить, как меняется эффективность алгоритмов от относительно небольших сетей до весьма крупных структур.

Важным аспектом анализа является оценка точности найденных путей. Особенно актуально это при использовании BFS с эвристикой (GBFS) [1], где алгоритм может предоставлять субоптимальное решение. Поэтому в работе планируется замерять отклонение найденной длины пути от реального оптимума, выявляя, насколько существенно использование эвристики влияет на конечный результат и в каких ситуациях это отклонение может оказаться критическим.

Завершающим этапом исследования является формулирование рекомендаций по выбору конкретного алгоритма, исходя из размера графа, структуры его связности (плотный или разреженный) и наличия надежной эвристики. Ожидается, что данные рекомендации позволят применять наиболее подходящий метод в зависимости от доступных ресурсов и требований к качеству (оптимальности) решения.

МАТЕРИАЛЫ И МЕТОДЫ ИССЛЕДОВАНИЯ

Используемое оборудование

Все эксперименты проводились на локальном компьютере со следующими характеристиками:

• Операционная система: Windows 10 ×64
• Процессор: Intel Core i7‑10750H @ 2.60 ГГц (6 ядер / 12 потоков)
• Оперативная память: 24 ГБ
• Накопитель: SSD 512 ГБ

Выбор данного оборудования позволяет исключить факторы сетевой задержки и других внешних условий. Запуск алгоритмов осуществлялся в автономном режиме.

Программная реализация

В рамках настоящего научного исследования алгоритмы были реализованы на языке программирования Python версии 3.10, поскольку он обеспечивает удобный и наглядный способ быстрой разработки и проведения экспериментов. В качестве структуры данных для алгоритма Dijkstra использовалась приоритетная очередь (бинарная куча), реализованная с помощью стандартного модуля heapq. Такой подход позволил эффективно обрабатывать вершины в порядке возрастания текущих затрат.

Для алгоритма A* была необходима эвристическая функция, которая определяет, насколько далеко текущая вершина может находиться от целевой. В данной работе использовались евклидова и манхэттенская метрики. Евклидова дистанция хорошо подходит для графов, представимых в виде геометрической модели, а манхэттенская полезна при работе с решетчатыми структурами, где перемещение обычно происходит по осям сетки. Благодаря корректно выбранной эвристике алгоритм A* способен заметно уменьшить пространство поиска и повысить производительность.

Третий алгоритм, BFS с эвристикой (GBFS), формирует очередь вершин с приоритетом по оценке расстояния до цели, однако при этом не учитывает уже пройденный путь. Подобная стратегия в ряде случаев обеспечивает быстрое нахождение решения, хотя может приводить к субоптимальным путям и, как следствие, к большему отклонению от реального оптимального маршрута.

Генерация тестовых графов

Чтобы охватить различные условия, была использована двухтипная генерация:

1. Случайные графы, где вероятность ребра между двумя вершинами задается как p (0,01 ≤ p ≤ 0,1), что дает нам разреженный или умеренно плотный граф.
2. Графы на основе решетки, где вершины расположены в узлах двумерной сетки, а ребра соединяют соседние клетки. Для такой структуры удобно использовать манхэттенскую метрику.

В экспериментах размер графов изменялся в диапазоне от 10^3 до 10^6 вершин, что позволило охватить широкий спектр структур и масштабов. При этом вес ребер в случае случайных графов задавался случайным образом в пределах от 1 до 10, а в решетках все ребра принимались равными единице.

Метрики оценки

• Время выполнения: среднее из 5 повторных запусков для каждой конфигурации размера графа.
• Использование памяти: максимум потребляемой памяти (в МБ), определяемый с помощью библиотеки psutil или встроенного профилировщика Python.
• Отклонение пути от оптимального (%):

где  – длина пути, найденного алгоритмом, а  – реальная кратчайшая длина, установленная по результатам алгоритма Дейкстры либо по предварительному вычислению на небольших графах.

План экспериментов

Малый масштаб охватывал графы размером от 1000 до 5000 вершин (как случайные графы, так и небольшие решетки 70×70), средний масштаб составлял от 10^4 до 10^5 вершин, а крупный охватывал диапазон от 5×10^5 до 10^6 вершин и включал только случайные графы, поскольку решетки 1000×1000 дают 10^6 вершин и легко поддаются проверке. Для каждой конфигурации соответствующий алгоритм (Dijkstra, A*, BFS с эвристикой) запускался по 5 раз, после чего вычислялись средние показатели. С целью повышения точности на больших графах вводилось ограничение глубины поиска для BFS-эвристики, чтобы избежать чрезмерного расхода памяти.

РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ

В данном разделе приводятся итоги сравнительного анализа четырех алгоритмов (Dijkstra, A*, BFS, GBFS) на двух типах тестовых графов: решетках и случайных. Для каждого типа варьировалось число вершин, а при случайной генерации использовалось p=0.02. Основными метриками выступают время выполнения, потребление памяти и длина пути. Полученные результаты, усредненные по нескольким повторным запускам, сведены в Таблицах 1–5. На Рисунках 1–3 показаны зависимости времени, памяти и длины пути от числа вершин для тех же конфигураций графов.

Результаты на решетчатых графах

В решетчатых структурах (клетки 50×50 и 100×100) все ребра имеют единичный вес. Из‑за этого BFS и GBFS (при манхэттенской/евклидовой эвристике) находят путь той же длины, что и Dijkstra или A*, но зачастую выполняют задачи быстрее. GBFS работает значительно оперативнее, когда эвристика точно указывает направление к цели. При этом у GBFS могут наблюдаться скачки потребления памяти (см. Dijkstra и GBFS в Таблице 1 для 50×50), однако в целом при таких размерах ресурсы остаются невелики.

Таблица 1.

Средние результаты для решеток. Граф 50×50

Таблица 2.

Средние результаты для решеток. Граф 100×100

Как видно, итоговое расстояние (98 или 198) не зависит от алгоритма, тогда как время у BFS и GBFS нередко оказывается минимальным, особенно при «правильной» эвристике.

Рисунок 1. Зависимость времени выполнения от числа вершин

Рисунок 1 иллюстрирует, как изменяется время выполнения на разных размерах решеток и случайных графов. Замечено, что на малых сетках BFS и GBFS работают быстрее всего, а Dijkstra и A* дают небольшие дополнительные затраты (приоритетные структуры данных, вычисление эвристики).

Результаты на случайных графах

В случайных графах ребра могут иметь вес 1…10. В таких условиях BFS стремится минимизировать количество ребер, не учитывая их суммарную стоимость. Напротив, Dijkstra и A* (при неотрицательных весах) находят реальный кратчайший путь по сумме весов. GBFS может выдавать очень длинные маршруты (см. Расстояние = 202, 687, 1027 в Таблицах 3–5), если эвристика слабо отражает реальную конфигурацию графа, и при этом тратит больше памяти и времени.

Таблица 3.

Средние результаты для случайных графов. Граф на 1000 вершин

Таблица 4.

Средние результаты для случайных графов. Граф на 5000 вершин

Таблица 5.

Средние результаты для случайных графов. Граф на 10 000 вершин

Как показывают Таблицы 3–5, Dijkstra и A* везде обеспечивают оптимальную цену (3, 5 или 7 ребер по весу), в то время как BFS стремится к минимальному количеству ребер (2–3), но игнорирует суммарные затраты. GBFS, если эвристика не отражает реальные расстояния, может находить крайне длинный путь (до 1027 ребер), сопровождаясь существенным ростом времени и памяти.

Рисунок 2. Зависимость потребления памяти от числа вершин

Рисунок 2 иллюстрирует распределение потребляемой памяти в зависимости от числа вершин. При малых сетках BFS и GBFS сохраняют скромные требования по памяти, но при росте размера случайного графа GBFS способно «раздуваться» на десятки мегабайт – резко больше, чем Dijkstra и A*.

Рисунок 3. Зависимость длины пути от числа вершин

Рисунок 3 показывает, как меняется длина пути. Для единичных ребер на решетках все алгоритмы выдают одинаковую минимальную дистанцию, а в случайных графах A* и Dijkstra гарантированно достигают лучшей стоимости, тогда как BFS сокращает число ребер, но не всегда обеспечивает оптимальность, а GBFS может сильно отклоняться от оптимального маршрута.

Как видно из Рисунков 1–3, эти данные подтверждают выводы, основанные на данных из Таблиц 1–5: BFS и GBFS особенно эффективны для невзвешенных или равномерно взвешенных сеток, тогда как Dijkstra и A* предпочтительны при различных весах ребер, гарантируя стабильное время выполнения и оптимальный путь.

ОБСУЖДЕНИЕ РЕЗУЛЬТАТОВ

Результаты экспериментов указывают на существенные различия в поведении алгоритмов Dijkstra, A*, BFS и GBFS при различных структурах графа и характере весов ребер. В решетчатых структурах с единичными весами все эти методы дают одинаковую длину пути, однако BFS и GBFS зачастую достигают цели быстрее, поскольку не тратят время на дополнительную обработку (приоритетные очереди и вычисление эвристики). Особенно высокую эффективность на сетках показывает GBFS, когда эвристика (манхэттенская либо евклидова) точно отражает расстояние до цели, позволяя практически сразу направляться в правильном направлении и сводить к минимуму перебор вершин.

В случайных графах поведение алгоритмов оказывается более вариативным. BFS остается быстрым, но не учитывает разные веса ребер (1–10), из-за чего не всегда ведет к глобально оптимальному решению. A* и Dijkstra, напротив, гарантированно находят кратчайший путь по сумме весов, хотя у A* возникают реальные преимущества перед классическим Дейкстрой лишь тогда, когда эвристика хорошо коррелирует с реальной структурой графа. Если вершины заданы просто целыми индексами и геометрическая эвристика слабо информативна, A* мало чем отличается от Дейкстры по времени и памяти.

Наибольшие сложности отмечаются у GBFS, когда эвристика оказывается неточной: алгоритм может теряться, формируя крайне длинные пути и резко увеличивая потребление ресурсов. Это совпадает с результатами, известными по исследованиям в области real-time heuristic search [7]: при неточной оценке расстояния к цели жадный поиск (GBFS) существенно теряет эффективность. При динамических изменениях в структуре графа могли бы применяться расширения вроде D*, описанные в [6], но в данной статье рассматривается статическая постановка задачи.

Собранные экспериментальные данные подтверждают, что BFS и GBFS эффективны в условиях невзвешенных или однородных по весам графов (особенно решеток), тогда как Dijkstra и A* являются универсальным решением при необходимости учета различных весов и обеспечения оптимального пути. Влияние эвристики для A* и GBFS критически важно: при ее корректном выборе время поиска заметно сокращается, при слабом – алгоритм может расходовать чрезмерное количество ресурсов.

ВЫВОДЫ

Анализ четырех алгоритмов (Dijkstra, A*, BFS, GBFS), примененных на двух типах графов – решетках с единичными ребрами и случайных структурах с весами в диапазоне 1–10, продемонстрировал их сильные и слабые стороны. На сетках BFS и GBFS зачастую оказываются быстрее Dijkstra и A*, поскольку не требуют затрат на приоритетные структуры, а при наличии информативной эвристики (манхэттенской или евклидовой) быстро находят кратчайший путь. Напротив, в случайных графах BFS, игнорируя реальные веса, нередко дает решение с минимальным количеством ребер, но может быть субоптимален по сумме весов. В то же время Dijkstra и A* гарантированно находят путь с минимальной совокупной стоимостью, тогда как GBFS при неточной эвристике застревает и показывает ухудшенные результаты.

Особенно важным фактором оказывается качество эвристики: A* действительно превосходит Dijkstra лишь при достаточной точности оценки расстояния, а GBFS сохраняет быстроту только тогда, когда эвристика точно ведет к цели. Практическое применение экспериментов подтверждает, что для невзвешенных решеток разумнее всего применять BFS или GBFS (при хорошей эвристике), позволяя добиться высокой скорости и низких затрат памяти. Однако если требуется учитывать неоднородные веса и обеспечивать истинный оптимум, предпочтительными оказываются Dijkstra или A*. Если при этом в графе возможны динамические изменения (перестройка весов, появление/исчезновение препятствий), имеет смысл рассматривать алгоритмы семейства D*, упомянутые в [6].

Полученные результаты соответствуют традиционным представлениям о применимости этих алгоритмов и подчеркивают решающую роль надежной эвристики (для A* и GBFS), а также необходимость внимательного выбора метода с учетом размера и структуры исследуемого графа.

Исходные коды, включая реализации алгоритмов, генерацию тестовых графов и скрипты для воспроизведения экспериментов, находятся в открытом репозитории: https://github.com/anchmelev/graph-pathfinding-experiments [2].

Список литературы:

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. – М.: Вильямс, 2017. – 1296 с.
2. Открытый репозиторий [Электронный ресурс]. – Режим доступа:  https://github.com/anchmelev/graph-pathfinding-experiments (дата обращения: 09.05.2025.).
3. Станкевич О.О. Алгоритмы поиска путей на графах в системах робототехники // Известия вузов. Приборостроение. – 2019. – Т. 62. – № 4. – С. 54–61.
4. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. – 1959. – Vol. 1. – No. 1. – P. 269–271.
5. Hart P.E., Nilsson N.J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics. – 1968. – Vol. 4. – No. 2. – P. 100–107.
6. Koenig S., Likhachev M.D. Lite // Proceedings of AAAI. – 2002. – P. 476–483.
7. Korf R.E. Real-time heuristic search // Artificial Intelligence. – 1990. – Vol. 42, No. 2–3. – P. 189–211.
8. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. – Addison-Wesley, 1984. – 382 p.
9. Russell S., Norvig P. Artificial Intelligence: A Modern Approach (3rd ed.). – Upper Saddle River (NJ): Prentice Hall, 2010. – 1152 p.