АЛГОРИТМЫ НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ МАРШРУТОВ | Нищеменко Лолита Андреевна. Работа №215427

АЛГОРИТМЫ НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ МАРШРУТОВ

Нищеменко Л.А. 1

1Нищеменко Лолита Андреевна - студентка 4 курса факультета математики и информационных технологий АГУ, кафедра информационных технологий.

Астраханский государственный университет, г. Астрахань

Аннотация: в статье проведён анализ алгоритмов, вычисляющих оптимальные маршруты в графах, проведен сравнительный анализ различных алгоритмов.

Ключевые слова: алгоритм, путь, маршрут

OPTIMAL ROUTES ALGORITHMS

Nischemenko L.A. 1

1Nischemenko Lolita Andreevna, student of the Faculty of Mathematics and Information Technologies, Department of Information Technologies.

ASTRAKHAN STATE UNIVERSITY, ASTRAKHAN.

Abstract: the article analyzes the algorithms that calculate the optimal routes in graphs, a comparative analysis of various algorithms.

Keywords: algorithm, path, route

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

Маршрут можно представить графовой моделью. В качестве вершин выступает множество точек- множество мест доставки и дуг – множество путей. Структура графа может быть изменяемой. Ниже представлен пример графа на рис.1.

Рис. 1. Графовая модель

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

Рассмотрим наиболее популярные алгоритмов поиска кратчайшего пути в графе:

алгоритм Беллмана-Форда;

алгоритм Дейкстры;

алгоритм поиска А*;

алгоритм Ли (волновой алгоритм);

Алгоритм Беллмана-Форда. Это алгоритм поиска кратчайшего пути во взвешенном графе. Взвешенным графом называется граф, вершинам и (или) рёбрам которого присвоены "весы" - обычно это некоторые числа. Этот алгоритм находит путь от одной вершины графа до всех остальных. В этом алгоритме существуют ребра с отрицательным весом. Условием нашей задачи является нахождение рационального пути между несколькими точками. Алгоритм использует полный перебор всех вершин графа, что обычно занимает большой объем времени и больший объем памяти вычислительной машины, особенно если существует дополнительная информация о маршрутах.

Рис. 2. Графовая модель алгоритма Беллмана-Форда

Алгоритм Дейкстры. Самый известный и широко распространенный алгоритм. Он используется для нахождения пути в графе из одной вершины до всех остальных. Алгоритм работает исключительно для графов с ребрами положительного веса, в отличии от алгоритма Беллмана-Форда. Алгоритм Дейкстры считается одним из самых простых. Он хорошо выполняется в графах с небольшим количеством вершин. Но если количество вершин будет доходить до нескольких тысяч, использование такого алгоритма будет не лучшим решением. Еще одним минусом алгоритма Дейкстры в нашем случае является то, что он ищет кратчайшие пути от одной вершины графа до всех остальных.

Рис. 3. Графовая модель алгоритма Дейкстры

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

Рис. 4. Графовая модель алгоритма поиска А*

Алгоритм Ли (волновой). Применение волнового алгоритма – поиск кратчайшего расстояния на карте в компьютерных стратегических иг- рах.

Алгоритм работает на дискретном рабочем поле (ДРП), представляющем собой ограниченную замкнутой линией фигуру, не обязательно прямоугольную, разбитую на прямоугольные ячейки, в частном случае – квадратные. Множество всех ячеек ДРП разбивается на подмножества: «проходимые» (свободные), т. е при поиске пути их можно проходить, «непроходимые» (препятствия), путь через эту ячейку запрещён, стартовая ячейка (источник) и финишная (приемник). Назначение стартовой и финишной ячеек условно, достаточно – указание пары ячеек, между которыми нужно найти кратчайший путь.

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

Рис. 5. Графовая модель алгоритма Ли(волнового алгоритма)

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

Рассмотренные алгоритмы работают на взвешенных графах. Невзвешеные графы являются частным случаем взвешенных, имеющих равные веса. При этом, длина маршрута определяется количеством вершин, через которые он проходит.

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

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

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

Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных. – Нижний Новгород: Издательство Нижегородского государственного университета, 2005

Кормен

Т.Х.,

Лейзерсон

Ч.И.,

Ривест

Р.Л., Штайн К. Алгоритмы: построение и анализ. Москва: Вильямс, 2006.

Левитин А.В. Алгоритмы: введение в

разработ

- ку

и анализ. Москва

:

Вильямс

, 2006.

Базовые алгоритмы нахождения кратчайших путей во взвешенных графах

https://habr.com/ru/post/119158/

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе

https://habr.com/ru/post/111361/