АНАЛИЗ АЛГОРИТМОВ «A*» и «ДЕЙКСТРЫ»

АННОТАЦИЯ

В статье проанализированы и реализованы два известных и интересных алгоритма «А*» и «Дейкстры». Данные алгоритмы широко используются для решения задач поиска кратчайшего пути в лабиринте. Так же в статье представлено авторское приложение, написанное на языке программирования С#, позволяющее пользователю создать собственный лабиринт, выбрать желаемый алгоритм для поиска пути и визуально рассмотреть и оценить его работу.

Ключевые слова: лабиринт, поиск пути, алгоритм; a*; алгоритм Дейкстры.

Алгоритм «Дейкстры» – является одним из классических алгоритмов на графах, используемый для нахождения кратчайших путей от начальной до всех остальных вершин в графе с неотрицательными весами рёбер [1].

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

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

Так как принцип работы алгоритма теперь понятен, перейдём непосредственно к его реализации на языке программирования C#. Основной функцией является «FindPathDijkstra», представленна на рисунке 1.

Рисунок 1. Реализация алгоритма «Дейкстры»

Результатом работы функции может быть «null», если до искомой вершины невозможно добраться, либо список ячеек, представляющий собой кратчайший путь от начальной до целевой вершины.

В процессе выполнения основной функции также используется вспомогательная функция «GetNeighbors», которая возвращает список соседних ячеек для текущей вершины, а также расстояния до них.

Далее рассмотрим принцип работы алгоритма «A*» [2]. Этот алгоритм, в отличие от алгоритма «Дейкстры», ориентирован на нахождение пути к целевой вершине более целенаправленно, опираясь на оценочную функцию (эвристику), которая помогает быстрее приближаться к цели.

Эвристическая функция – это функция, используемая в алгоритмах поиска для оценки того, насколько близко находится текущая вершина к достижению цели.

Первым этапом алгоритма «A*» является инициализация данных. Для каждой вершины создаются три структуры данных: первый список, обозначенный как «gCost», сохраняет фактическую стоимость пути от начальной вершины до текущей; второй список, обозначенный как «fCost», хранит сумму эвристической оценки и фактической стоимости пути; третий список содержит открытые вершины, которые предстоит исследовать. Изначально значения каждой вершины в списках «gCost» и «fCost» равны бесконечности, за исключением начальной вершины. Значение начальной вершины в «gCost» равно нулю, а в «fCost» оно равно эвристической оценке, так как фактическая стоимость равна нулю. Начальная вершина также добавляется в список открытых вершин.

На основном этапе работы алгоритма из списка открытых вершин извлекается вершина с наименьшим значением «fCost». Затем определяются её соседи (смежные вершины). Для каждого соседа вычисляются фактическая и суммарная стоимости пути. Если новая фактическая стоимость оказалась меньше предыдущей, значения обновляются в списках «fCost» и «gCost». Если соседнюю вершину ещё не посещали, она добавляется в список открытых вершин.

Как и в предыдущем алгоритме, работа алгоритма завершается, если была найдена целевая вершина или список открытых вершин пуст.

Реализация данного алгоритма на языке С# представлена на рисунке 2.

Рисунок 2. Реализация алгоритма «A*»

В отличие от реализации алгоритма «Дейкстры», в процессе выполнения данного алгоритма используется функция «GetFValueWithHeuristicDistance». Эта функция применяется для получения суммы эвристической оценки и фактической стоимости пути, вычисляя расстояние по гипотенузе от текущей вершины до целевой.

Так как все алгоритмы рассмотрены, перейдём к реализации приложения используя фреймворк Windows Presentation Foundation (WPF) [3].

На рисунке 3 представлены дополнительные функции, используемые для реализации приложения.

Рисунок 3. Дополнительные функции

Одной из значимых функций является «ChangeCell», которая используется для создания лабиринта, а также запуска процесса поиска кратчайшего пути.

Пример выполнения программы представлен на рисунке 4.

Рисунок 4. Пример выполнения программы

Далее проведём тестирование каждого алгоритма, чтобы определить, какой из них является наиболее эффективным и подходящим для использования в различных сценариях. Мы сравним их по таким критериям, как время выполнения и стоимость пути. Тестирование каждого из алгоритмов приведено в таблице 1.

Таблица 1.

Тестирование «A*» и «Дейкстры»

Исходя из полученных результатов тестирования алгоритмов «A*» и «Дейкстры», можно сделать следующие выводы: если важны как оптимальная стоимость пути, так и приемлемая скорость выполнения, то алгоритм «A*» является предпочтительным вариантом. Алгоритм «Дейкстры», несмотря на свою точность и гарантированно оптимальные пути, работает намного медленнее по сравнению с другими алгоритмами.

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

1. «Алгоритм Дейкстры». [электронный ресурс] – URL: https://algosolve.pythonanywhere.com/algorithms/grafovyie-algoritmyi-graph/algoritm-dejkstryi-dijkstras-algorithm/ (дата обращения 20.07.2024).
2. «A* Algorithm». [электронный ресурс] – URL: https://codeharborhub.github.io/dsa/Algorithms/Graph%20Algorithms/a-star-algorithm/ (дата обращения 20.07.2024).
3. «Руководство по WPF». [электронный ресурс] – URL: https://metanit.com/sharp/wpf/ (дата обращения 20.07.2024).