Обзор алгоритмов поиска кратчайшего пути в графе

Аннотация

В статье рассматривается задача анализа различных алгоритмов, связанных с графами, и нахождения решения поиска оптимального пути, с учетом особенностей процесса распределения ресурсов сети связи. Рассматриваются алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла, Ли, алгоритм А*.

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

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

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

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

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

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

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

• алгоритм Дейкстры;
• алгоритм Беллмана-Форда;
• алгоритм поиска А*;
• алгоритм Флойда-Уоршелла;
• алгоритм Ли (волновой алгоритм).

Алгоритм Дейкстры. Самый известный и широко распространенный алгоритм. Был разработан голландским ученым Эдсгером Дейкстрой в 1959 году и используется для нахождения пути в графе из одной вершины до всех остальных. Алгоритм работает исключительно для графов с ребрами положительного веса. Вычислительная сложность алгоритма — O(n²+m) [Алексеев, 2005; Кормен, 2006].

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

Алгоритм Беллмана-Форда. Это алгоритм поиска кратчайшего пути во взвешенном графе, который находит путь от одной вершины до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает наличие в графе ребер с отрицательным весом. Был предложен независимо американцами Ричардом Беллманом и Лестором Фордом. Вычислительная сложность алгоритма — O(n²×m) [Кормен, 2006; Левитин, 2005].

Данный алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. Условие нашей задачи — нахождение рационального пути между двумя точками сети связи. Избыточная информация о дополнительных маршрутах будет использовать дополнительные ресурсы вычислительной машины Алгоритм использует полный перебор всех вершин графа, что приведет к большой потери времени и займет больший объем памяти вычислительной машины.

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

Алгоритм А* является алгоритмом поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной). Порядок обхода вершин определяется эвристической функцией расстояние + стоимость (обычно обозначаемой как f(x)) Эта функция — сумма двух других: функций стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)). Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Вычислительная сложность — O(log(h(x)) [Кормен, 2006].

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

Алгоритм Флойда-Уоршелла. Этот алгоритм был разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Является динамическим алгоритмом для поиска кратчайших расстояний между всеми вершинами взвешенного ориентированного графа.

Данный алгоритм имеет вычислительную сложность — O(n³) [Левитин, 2006]. При применении его к решению задач на значительно разветвленном графе, он потребует значительных затрат со стороны ресурсов вычислительной машины. К тому же, алгоритм Флойда-Уоршела применяется для нахождения путей из одной вершины во все остальные, что противоречит условиям нашей задачи.

Алгоритм Ли (волновой). Ли разработал этот алгоритм в 1961 году при формализации алгоритмов трассировки печатных плат. В основном используется при компьютерной разводке печатных плат, соединительных проводников на поверхности микросхем. Другое применение волнового алгоритма — поиск кратчайшего расстояния на карте в компьютерных стратегических играх.

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

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

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

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

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

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

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

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

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

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

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

Левитин А.В. Алгоритмы: введение в разработку и анализ. Москва: Вильямс, 2006.