Анализ производительности алгоритмов поиска пути для графа навигации

Аннотация

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

Введение

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

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

Постановка задачи

Для поиска пути по графу существует множество алгоритмов, как универсальных, так и специализированных под конкретные ситуации. Многие алгоритмы, работающие с графами, требуют определенной систематической обработки вершин или ребер графа [1]. Среди них можно выделить: поиск в ширину, алгоритм Дейкстры и алгоритм А*. Именно эти алгоритмы будут рассмотрены в данной статье. Поиск в ширину имеет ту же эффективность, что и поиск в глубину, но имеются ситуации, где можно использовать поиск в ширину, но не в глубину – в рассматриваемой нами задаче поиска пути между вершинами [1].

Описание алгоритмов

Поиск в ширину (обход в ширину, breadth-first search) — это один из основных алгоритмов на графах. В результате поиска в ширину находится путь кратчайшей длины в невзвешенном графе, т.е. путь, содержащий наименьшее число рёбер. Алгоритм был разработан независимо Муром и Ли для разных приложений (поиск пути в лабиринте и разводка проводников соответственно) в 1959 и 1961 годах. Этот алгоритм можно сравнить с поджиганием соседних вершин графа: сначала мы зажигаем одну вершину (ту, из которой начинаем путь), а затем огонь за один элементарный промежуток времени перекидывается на все соседние с ней не горящие вершины. В последствие то же происходит со всеми подожженными вершинами. Таким образом, огонь распространяется «в ширину». В результате его работы будет найден кратчайший путь до нужной клетки [1].

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

Алгоритм А* – алгоритм поиска, который находит маршрут от стартовой вершины к финальной с наименьшей стоимостью. Был разработан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Данный алгоритм по сути является расширением алгоритма Дейкстры, но достигает более высокой производительности за счет введения в работу алгоритма эвристической функции [4].

Описание графа навигации

В качестве объекта навигации в данной статье выступает учебный корпус. Это четырехэтажное здание с одним входом и двумя лестницами. Граф навигации для здания приведен на рисунке 1.

Граф описывает четыре этажа – четыре длинных коридора с аудиториями, связанные между собой лестничными пролетами. Как показано на рисунке 1, вершины графа описывают перекрестки, лестничные площадки и конечные точки – учебные аудитории и служебные помещения, например, столовая или деканат. А связи между вершинами – ребра графа – описывают отрезки путей между ними, вес этих ребер содержит длину такого отрезка в реальном здании.

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

Моделирование

Моделирование производится на языке Java, так как алгоритмы тестируются на базе разработанного приложения для операционной системы Android. Алгоритмы поиска пути являются главной составляющей системы навигации [3].

Моделирование показывает распространение алгоритмов в результате поиска пути, что позволяет оценить эффективность работы алгоритма. На рисунке 2 приведен граф навигации, на котором отражены списки просмотренных вершин и вершины маршрута в результате работы алгоритма поиска в ширину.

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

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

На рисунке 4 приведен граф навигации, на котором отражены списки просмотренных вершин и вершины маршрута в результате работы алгоритма А*. Так как алгоритм А* для своей работы кроме стоимости пути использует еще и эвристическую информацию о расположении вершин в пространстве. С учетом эвристической информации алгоритм распространяется точно в сторону конечной вершины с минимальными отклонениями. Это позволяет находить короткий путь обрабатывая небольшое количество вершин.

Анализ работы алгоритмов

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

Как видно из диаграммы, алгоритмы практически одинаково находят путь между вершинами в графе навигации. Причем можно заметить, что поиск в ширину работает так же эффективно, как и эвристический алгоритм А*. Однако, это только те вершины, которые отсеялись в конце работы алгоритма. На рисунке 3 приведена диаграмма сравнения количества вершин маршрута и количества просмотренных алгоритмом вершин графа для самого длинного маршрута.

Из данных диаграмм можно сделать следующие выводы:

• Для слаборазветвлённых зданий может подойти алгоритм поиска в ширину, так как его распространение будет в большинстве случаев совпадать с распространением точных эвристических алгоритмов.
• Если есть необходимость в экономии памяти для списков просмотренных вершин и достаточно высокая скорость поиска, то с такой задачей хорошо справится эвристический алгоритм А*.
• Графы для систем навигации имеют специфическую форму и эффективность одного алгоритма поиска для разных зданий может значительно отличаться.

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

Список использованной литературы

1. Левитин А. В. Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы. Введение в разработку и анализ – М.: Вильямс, 2006. – 576 с.
2. Изотова, Т. Ю. Обзор алгоритмов поиска кратчайшего пути в графе / Т. Ю. Изотова // Новые информационные технологии в автоматизированных системах. – 2016. – № 19. – С. 341-344.
3. Кривошеев, С. В. Система поиска и построения маршрутов внутри помещения с помощью путевых карточек / С. В. Кривошеев, Е. А. Алутин // Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС-2020) : сборник научных трудов III Международной научно-практической конференции (студенческая секция), Донецк, 25–26 ноября 2020 года. – Донецк: Донецкий национальный технический университет, 2020. – С. 155-161.
5. Кравченко, М. К. Реализация алгоритма поиска пути для транспортного средства / М. К. Кравченко, С. В. Кривошеев, Р. В. Мальчева // Современные тенденции развития и перспективы внедрения инновационных технологий в машиностроении, образовании и экономике. – 2018. – Т. 4. – № 1(3). – С. 105-110.