Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
3.2. Алгоритмы нахождения кратчайшего пути (цепи) между вершинами графа
Алгоритм нахождения кратчайшего пути (кратчайшей цепи) входит в качестве отдельного этапа подзадачи во многие вычислительные схемы оптимизации для экстремальных задач на графах. Поэтому в литературе по этому вопросу можно найти описания алгоритмов, принадлежащих различным авторам: Беллман, Дийкста, Форд и Фалкерсон, Данциг, Ен и др. Мы приведем описание алгоритма «приписывания меток», который состоит из двух этапов. На первом этапе последовательно приписываются метки вершинам исходного графа до тех пор, пока не будет помечена искомая вершина. На втором этапе по приписанным меткам восстанавливается искомый путь.
Пусть задан граф, у которого дуги (рёбра) не взвешены и вершины пронумерованы индексом 
. Требуется найти кратчайший путь из вершины 
в вершину 
, т.е. путь 
, состоящий из наименьшего числа дуг. Через 
обозначим множество всех вершин, в которые исходят дуги из вершины 
.
Этап 1. На нулевом шаге вершине приписываем метку 
. На первом шаге всем вершинам 
приписываем метки 
. На каждом последующем шаге 
действуем следующим образом: если вершина помечена меткой 
, то всем еще непомеченным вершинам 
приписываем метку 
. Этап 1 заканчивается на некотором шаге 
, как только вершина окажется отмеченной меткой 
.
Этап 2. Коль вершина 
помечена меткой , то кратчайший путь состоит из дуг, причем, у каждой из этих дуг 
метка начала на единицу меньше метки конца 
: 
. Тогда для нахождения достаточно проследовать от вершины к вершине с меткой 
, от вершины к вершине с меткой 
и т.д., пока не дойдем до вершины 
. Если вершин с одинаковой меткой несколько, то выбирается любая.
Опишем метод решения задачи о кратчайшем пути на взвешенном графе. Пусть задан неориентированный граф 
, вершины которого перенумерованы индексом 
.
Требуется в графе 
выделить кратчайшую цепь , соединяющую вершину с вершиной 
. Одним из наиболее экономных алгоритмов решения этой задачи принадлежит Дийкстра. Приведем описание этого алгоритма, работа которого состоит из действий двух видов. Сначала всем вершинам графа приписываются пробные метки 
. Затем пробные метки заменяются на постоянные метки 
, где 
– длина кратчайшей цепи от к . Преобразование пробных меток в постоянные заканчивается, как только пробная метка 
у вершины 
будет заменена на постоянную 
. После этого искомый путь выделяется обратным ходом от к .
Начало работы алгоритма: вершине приписывается метка 
, а всем остальным вершинам графа приписывается пробная метка 
, 
. При этом для каждой пары вершин , определяется величина 
следующим образом: 
, если ребро 
, и значение 
в противном случае.
Дальнейшая работа алгоритма осуществляется по шагам 
. На каждом шаге осуществляется преобразование некоторых пробных меток в постоянные.
Шаг 1. Всем смежным с вершинам приписываем новую пробную метку 
и среди всех новых меток 
выбираем минимальную. Пусть это будет 
. Тогда минимальная пробная метка 
объявляется постоянной, т.е. 
и следует перейти к следующему шагу 2.
В дальнейшем через 
будем обозначать множество вершин 
, 
, каждая из которых после реализации шага 
уже имеет постоянную метку 
.
Шаг , 
. Всем вершинам 
с пробными метками 
приписываем новые пробные метки
и выбираем среди них минимальную. Пусть это будет 
. Тогда пробную метку оставляем постоянной, т.е. 
, и переходим к шагу 
.
На некотором шаге 
вершина получит постоянную метку 
. Это означает, что длина кратчайшей цепи в данном графе от вершины к вершине равна 
. Искомая кратчайшая цепь находится движением от к по таким ребрам 
, что 
. Эти ребра и составляют искомую кратчайшую цепь .
Трудоемкость, т.е. вычислительная сложность алгоритма Дийкстра составляет 
элементарных операций.
На конкретном примере алгоритма Дийкстры покажем, что этот инструмент классической дискретной оптимизации (задачи с данными в виде действительных чисел) в определенной степени применим к задаче с интервальными весами [7]. Пусть ребра 
данного графа взвешены интервалами, т.е. отрезками 
, 
. В этом случае на множестве допустимых решений 
целевая функция (3.1) принимает также интервальные значения, то есть, если 
, 
, 
, то
,(3.2)
где
, 
, 
.(3.3)
В главе 5 мы покажем, что в этом случае для экстремальных задач на графах «оптимальные» допустимые решения, вообще говоря, отсутствуют, т.к. всякая экстремальная задача на графе с интервальными весами эквивалентна (т.е. взаимосводима) к определенной 2-критериальной задаче [7]. В многокритериальных задачах множество допустимых решений делится на две части: паретовское множество (ПМ) 
[74] и множество доминируемых решений (
), т.е. решений, качество которых можно улучшить хотя бы по одному критерию, в силу чего множество (
) не содержит оптимумов.
Парето-оптимальные решения являются векторно-несравнимыми в том смысле, что в общем случае среди них отсутствуют элементы, удовлетворяющие понятию «оптимум». Вместе с тем, в смысле теории выбора и принятия решений [49], [92] «наилучшее» решение выбирается из . Поэтому, в общем случае, термин «решение экстремальной задачи с интервальными данными» подразумевает нахождение ПМ 
. Нахождение ПМ иногда обусловлено непреодолимыми вычислительными трудностями [30]. Отсюда возникает важный вопрос о практически реализуемых (т.е. малотрудоёмких) методах вычисления априорных оценок значений интервальной целевой функции (3.2)-(3.3) на неизвестном «наилучшем» решении 
. Позитивный конструктивный ответ на этот вопрос можно получить с помощью алгоритма Дийкстры следующим образом.
Для заданного графа с интервальными весами рассмотрим два случая нового взвешивания: если ребро 
имеет интервальный вес 
, то в первом (втором) случае интервал 
заменяем на нижнее (верхнее) значение 
(
). С помощью алгоритма Дийкстры для первого (второго) случая находим кратчайший путь 
длины 
(
длины 
). Тогда в обозначениях (3.2)-(3.3) для всякого паретовского оптимума
, выбираемого в качестве «наилучшего» решения, являются справедливыми следующие оценки (значения) интервальной целевой функции 
:
.(3.4)
Нетривиальность оценок (3.4) состоит в том, что, вообще говоря, являются несовпадающими пути , 
и 
. Более того, если эти пути состоят из дуг, составляющих соответственно множества 
, 
и 
, то может быть пустым каждое их попарное пересечение: 
, 
, 
.
Наряду с оценками (3.4) с помощью алгоритма Дийкстры представляется возможным ценою полиномиальной вычислительной сложности находить подмножество 
представителей ПМ. Для этого достаточно использовать множество векторов 
,
(например 
, 
, 
) и применить алгоритм Дийкстры к исходному n-вершинному графу, ребра которого последовательно взвешиваются свёрткой вида
, 
.(3.5)
Согласно [74] соответствующее r-ому значению свёртки (3.5) решение 
является паретооптимальным, в силу чего множество 
, является подмножеством ПМ 
. Вычислительная сложность нахождения 
является полиномиальной, если 
, где 
– константа.
Примечание 3.1. На примере представленного выше применения алгоритма Дийкстры для получения оценок вида (3.4), а также нахождения «подмножеств представителей» вида паретовского множества продемонстрирован достаточно общий подход к использованию алгоритмов классической дискретной оптимизации для решения задач с интервальными исходными данными.