Экстремальные пути и контуры на графах - В.Н. Бурков, Д.А. Новиков ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

2. Экстремальные пути и контуры на графах

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

Задача о кратчайшем пути. Пусть задана сеть из n + 1 вер­ шины, то есть ориентированный граф, в котором выделены две вершины - вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Дли­ ной пути {контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети 1 .

Известно [7, 15], что для существования кратчайшего пути не­обходимо и достаточно отсутствия в сети контуров отрицательной длины.

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

; В дальнейшем будем предполагать, что в любую вершину сети можно попасть из входа, и из любой вершины можно попасть в выход (вершины, не удовлетво­ ряющие этому требованию, можно удалить).

Обозначим Ц - длину дуги ( i ; j ). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

Шаг 0: Помечаем нулевую вершину индексом Хо = 0;

Шаг k : помечаем вершину k индексом

Индекс выхода Я„ будет равен длине кратчайшего пути 1 . На рисунке 2 приведен пример применения алгоритма 1 для опреде­ ления кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен двойными линиями).

Когда индексы (называемые в некоторых задачах потенциа­ лами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь

Рис. 2. Поиск кратчайшего пути

Следующий алгоритм дает возможность определять кратчай­ ший путь в общем случае (то есть при произвольной нумерации вершин).

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом все ос-

тальные вершины индексами

Шаг к Рассматриваем все дуги. Если для дуги ( i ; j ), го вычисляем новое значение

Индексы устанавливаются за конечное число шагов. Обозна­ чим {Я г } - установившиеся значения индексов, которые обладают

следующим свойством: величина Я г равна длине кратчайшего

пути из нулевой вершины в вершину i . Кратчайший путь из вер­шины 0 в вершину i определяется методом обратного хода.

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

Алгоритм 3.

Шаг 0: Помечаем нулевую вершину индексом Хо = 0;

Шаг k : Пусть уже помечено некоторое множество вершин. Обозначим Q - множество непомеченных вершин, смежных с помеченными. Для каждой вершины k е Q вычисляем величину где минимум берется по всем помеченным вер­ шинам i , смежным с вершиной к Помечаем вершину k, для кото­рой величина § t минимальна, индексом

Подобную процедуру повторяем до тех пор, пока не будет по­мечена вершина n. Длина кратчайшего пути равна Я„, а сам крат­чайший путь определяется так, как это было описано выше.

Запишем задачу о кратчайшем пути как задачу линейного про­граммирования (ЛП). Пусть ху = 1, если дуга ( i ; j ) входит в путь 1 ц,

Ху = 0, если дуга ( i ; j ) не входит в путь

Задачу о минимальном пути можно записать в виде 2 :

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

2 Ограничение (2) отражает требование того, что в искомом пути из входа выходит одна дуга и в выход заходит одна дуга. Ограничение (3) обеспечивает равенство числа заходящих и выходящих в любую промежуточную вершину дуг.

Любое решение системы неравенств (2)-(3) определяет путь в сети без контуров (но не в сети с контурами).

Пусть все контуры имеют строго положительную длину, то есть нет контуров отрицательной и нулевой длины. Тогда решение задачи (1)-(3) определяет путь кратчайшей длины.

Сформулируем задачу ЛП, двойственную задаче (1)-(3), по­ставив в соответствие ограничениям (2) двойственные переменные Хо и Я„, а ограничениям (3) - двойственные переменные {Я,},

По теореме двойственности линейного программирования [7], для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых функций совпадают.

Задача (4)-(5) называется задачей о потенциалах вершин гра­ фа. Общая ее формулировка такова: найти потенциалы вершин удовлетворяющие системе неравенств (5) и максимизирую­ щие некоторую функцию Ф(Х), где Примером является задача о ближайших потенциалах, в которой

могут интерпретироваться как

желательные потенциалы.

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

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

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

Гораздо более сложными ( NP -полными 1 ) являются задачи по­ иска элементарных путей кратчайшей (максимальной) длины в случае, когда в сети имеются контуры отрицательной (соответст­венно, положительной) длины 2 . Эффективных (не сводящихся к полному перебору) точных алгоритмов для них не существует.

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

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

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

; Качественно, если n - число вершин графа, то, если сложность (количество вычислений, операций, шагов и т.д.) алгоритма поиска точного решения пропор­циональна п а , где а - некоторое положительное число, то говорят, что алго­ ритм имеет полиномиальную сложность. Если сложность пропорциональна а", то имеет место экспоненциальная сложность ( NP -полнота). 2 Существуют несколько алгоритмов проверки отсутствия контуров отрица­ тельной (или положительной) длины: изменять индексы, пока число шагов алгоритма не превысит максимально необходимое (равное т-п) число; ограни­ чить потенциалы вершин заданными числами d i и при Я, < d t (Я, > d ,) проверять действительно ли полученное значение потенциала соответствует длине неко­ торого пути, или имеется контур отрицательной (положительной) длины; и др.

числом а,, вес предмета (или его объем) - &,-. Суммарный вес, который может нести турист (объем рюкзака), ограничен величи­ ной R . Требуется найти набор предметов, обладающий максималь­ной суммарной полезностью и удовлетворяющий ограничению.

Обозначим jc , - переменную, принимающую значение ноль (если 1-ый предмет не кладется в ранец) или единица (если г-ый предмет кладется в ранец). Тогда задача о ранце имеет вид:

Верхняя оценка числа возможных комбинаций - 2". Однако для решения задачи о ранце существует эффективный алгоритм - метод динамического программирования. При его использовании строится сеть (см. примеры в [7, 8, 12]) по следующим правилам. По оси абсцисс будем последовательно откладывать номера пред­метов, по оси ординат - их вес. Из каждой точки (начиная с точки (0; 0)) выходят две дуги - горизонтальная (соответствующая аль­ тернативе «не брать предмет») и наклонная (соответствующая альтернативе «взять предмет»), вертикальная проекция которой равна весу предмета. Длины наклонных дуг положим равными ценности предметов, длины горизонтальных дуг - нулю. Получен­ная сеть (конечная вершина является фиктивной и вес любой дуги, соединяющей ее с другими вершинами, равен нулю) обладает следующими свойствами: любому решению задачи (6)-(7) соответ­ствует некоторый путь в этой сети; любому пути соответствует некоторое решение задачи. Таким образом, задача свелась к нахо­ ждению пути максимальной длины.

Задача поиска контура минимальной длины решается сле­ дующим образом. Если известно, что искомый контур содержит некоторую вершину, то нужно определить кратчайшей путь от этой вершины до нее же, применяя описанные выше алгоритмы. Так как в общем случае контур минимальной длины может прохо­ дить через любую вершину графа, то находятся контуры мини­мальной длины, проходящие через каждую вершину, и среди них выбирается кратчайший. Более простым является следующий алгоритм 4 : берется первая вершина (в произвольном их упорядо­ чении) графа и рассматривается сеть, в которой эта вершина явля-

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

длина которого равна

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

1. Определяем произвольный контур. Пусть L - длина этого контура, k-число его дуг. Вычисляем 1 ср = Ь/ки добавляем (-1 ср ) к длинам Ц всех дуг.

Затем определяем контур отрицательной длины, повторяем шаг 1, и т.д. до тех пор, пока на очередном шаге таких контуров не найдется.

Так как на каждом шаге длины всех дуг изменялись на одно и то же число, то на последнем шаге длина дуги равна -

суммарное изменение длины каждой дуги на всех шагах.

Значение равно минимальной средней длине дуг контуров графа. При этом контуром минимальной средней длины является контур, определенный на предпоследнем шаге.

Путь максимальной эффективности. Пусть задана сеть, в которой для каждой дуги ( i ; j ) определены два числа ин-

терпретируемые как эффект при осуществлении соответствующей операции - и затраты на эту операцию - Эффективность пути определяется как отношение его эффекта к

затратам Задача заключа-

ется в поиске пути максимальной эффективности:

Если решение этой задачи известно, то по опреде-

лению К выполнено:

(8)

Следовательно, задача свелась к поиску минимального значе­ния К , для которого имеет место (8). Другими словами, необходи­мо найти минимальное К , такое, что все пути (длина которых определяется как в сети имеют неположитель-

ную длину (неравенство (8) должно выполняться, в том числе, и для пути максимальной длины).

Алгоритм 6. 1) Положим К = 0. Находим путь щ максималь­ ной длины. Положим (заметим, что при К = К] длина пути jj { Ki ) равна нулю).

2) Находим максимальный путь ц 2 при K = K1. Если длина пу­ти fj . 2 , которую мы обозначим L ( K 1), равна нулю, то задача решена. Если то вычисляем и находим макси-

мальный путь fj . 2 при K = К 2 и т.д.

Путь максимальной эффективности с учетом штрафов. Пусть для каждой дуги (n + 7)-вершинной сети заданы два числа: эффект Эу и время tij. Каждый путь \ i из начальной вершины в конечную вершину характеризует некоторый процесс (например, проект). Под продолжительностью пути будем понимать сумму времен его дуг. Если продолжительность процесса отличается от заданного времени T, то налагаются штрафы %{р), пропорциональ­ные отклонению, то есть: = где коэф­фициенты а и /3 могут быть как положительными, так и отрица­ тельными.

Задача заключается в том, чтобы найти путь /л , максимизи­рующий разность между эффектом и штрафами, то есть

Обозначим

продолжительность оптимального пути при параметре то есть пути, имеющего максимальную длину, измеряемую в Легко показать, что с ростом величина не возрастает.

Обозначим - продолжительности оптимального пу-

ти при равном а и, соответственно, - эти пути (для

их нахождения необходимо решить две задачи на поиск пути максимальной длины). Рассмотрим шесть случаев (исходную