<< Предыдущая

стр. 2
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

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

Задачи поиска кратчайших и длиннейших путей на графах
возникают в различных областях управления. Сначала мы рас-
смотрим задачи о кратчайшем пути, затем задачи об экстремаль-
ных контурах.
Задача о кратчайшем пути. Пусть задана сеть из n + 1 вер-
шины, то есть ориентированный граф, в котором выделены две
вершины – вход (нулевая вершина) и выход (вершина с номером
n). Для каждой дуги заданы числа, называемые длинами дуг. Дли-
ной пути (контура) называется сумма длин входящих в него дуг
(если длины дуг не заданы, то длина пути (контура) определяется
как число входящих в него дуг). Задача заключается в поиске
кратчайшего пути (пути минимальной длины) от входа до выхода
сети1.
Известно [7, 15], что для существования кратчайшего пути не-
обходимо и достаточно отсутствия в сети контуров отрицательной
длины.
Предположим, что в сети нет контуров. Тогда всегда можно
пронумеровать вершины таким образом, что для любой дуги (i, j)
имеет место j > i. Такая нумерация называется правильной. Легко
показать, что в сети без контуров всегда существует правильная
нумерация.
1
В дальнейшем будем предполагать, что в любую вершину сети можно попасть
из входа, и из любой вершины можно попасть в выход (вершины, не удовлетво-
ряющие этому требованию, можно удалить).
7
Обозначим lij – длину дуги (i; j). Кратчайший путь в сети,
имеющей правильную нумерацию, определяется следующим
алгоритмом.
Алгоритм 1.
Шаг 0: Помечаем нулевую вершину индексом ?0 = 0;
Шаг k: помечаем вершину k индексом ?k = min (?i + lik).
i<k
Индекс выхода ?n будет равен длине кратчайшего пути1. На
рисунке 2 приведен пример применения алгоритма 1 для опреде-
ления кратчайшего пути (числа у дуг равны длинам дуг, индексы
вершин помещены в квадратные скобки, кратчайший путь выделен
двойными линиями).
Когда индексы (называемые в некоторых задачах потенциа-
лами вершин) установятся, кратчайший путь определяется методом
обратного хода от выхода к входу, то есть кратчайшим является
путь µ = (0; i1; i2; ...; in-1; n), такой, что lin ?1n = ?n – ?n-1 и т.д.

[8] [9]
1
2 4
6
9 [14]
2
[0] 5
5
0
3 4

8 3
1 [10]
[5]


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


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



1
Алгоритм 1 для задач динамического программирования отражает принцип
оптимальности Беллмана: если ищется кратчайший путь между двумя точка-
ми, то длина пути между любыми двумя точками кратчайшего пути также
должна быть минимальна.
8
Шаг 0: Помечаем нулевую вершину индексом ?0 = 0, все ос-
тальные вершины индексами ?i = +?, i = 1, n ;
Шаг k: Рассматриваем все дуги. Для дуги (i; j), если ?j – ?i >lij,
то вычисляем новое значение ?' j = ?i + lij.
Индексы устанавливаются за конечное число шагов. Обозна-
чим { ?* } – установившиеся значения индексов, которые обладают
i

следующим свойством: величина ?* равна длине кратчайшего
i
пути из нулевой вершины в вершину i. Кратчайший путь из вер-
шины 0 в вершину i определяется методом обратного хода.
Если длины всех дуг неотрицательны, то для поиска кратчай-
шего пути применим следующий алгоритм.
Алгоритм 3.
Шаг 0: Помечаем нулевую вершину индексом ?0 = 0;
Шаг k: Пусть уже помечено некоторое множество вершин.
Обозначим Q – множество непомеченных вершин, смежных с
помеченными. Для каждой вершины k ? Q вычисляем величину
?k = min (?k + lki), где минимум берется по всем помеченным вер-
шинам i, смежным с вершиной k. Помечаем вершину k, для кото-
рой величина ?k минимальна, индексом ?k = ?k.
Подобную процедуру повторяем до тех пор, пока не будет по-
мечена вершина n. Длина кратчайшего пути равна ?n, а сам крат-
чайший путь определяется так, как это было описано выше.
Запишем задачу о кратчайшем пути как задачу линейного про-
граммирования (ЛП). Пусть xij = 0, если дуга (i; j) входит в путь1 µ,
xij = 0, если дуга (i; j) не входит в путь µ, i, j = 0 , n .
Задачу о минимальном пути можно записать в виде2:
n

?l xij > min
(1) L(x) = ij
x
i, j =0




1
Будем считать, что имеются две дуги между каждой парой вершин, так как,
если их нет в исходном графе, то, положив их длину равной бесконечности, мы
заведомо исключим их из решения.
2
Ограничение (2) отражает требование того, что в искомом пути из входа
выходит одна дуга и в выход заходит одна дуга. Ограничение (3) обеспечивает
равенство числа заходящих и выходящих в любую промежуточную вершину дуг.
9
?x ?x
(2) = 1, = 1,
0j jn
j
j

?x ?x , k = 1, n ? 1 .
(3) =
ki jk
j
i
Любое решение системы неравенств (2)-(3) определяет путь в
сети без контуров (но не в сети с контурами).
Пусть все контуры имеют строго положительную длину, то
есть нет контуров отрицательной и нулевой длины. Тогда решение
задачи (1)-(3) определяет путь кратчайшей длины.
Сформулируем задачу ЛП, двойственную задаче (1)-(3), по-
ставив в соответствие ограничениям (2) двойственные переменные
?0 и ?n, а ограничениям (3) – двойственные переменные {?i},
i = 1, n ? 1 :
(4) ?n – ?0 > max
(5) ?j – ?i ? lij, i, j = 0 , n .
По теореме двойственности линейного программирования [7],
для оптимальных решений задач (1)-(3) и (4)-(5) значения целевых
функций совпадают.
Задача (4)-(5) называется задачей о потенциалах вершин гра-
фа. Общая ее формулировка такова: найти потенциалы вершин
{?i}, удовлетворяющие системе неравенств (5) и максимизирую-
щие некоторую функцию ?(?), где ? = (?0, ?1, ..., ?n). Примером
является задача о ближайших потенциалах, в которой
? |?j – ?0 |, где { ?0j } могут интерпретироваться как
?(?) = j
j
желательные потенциалы.
Аналогично задаче о кратчайшем пути формулируется и ре-
шается задача о максимальном (длиннейшем) пути – достаточно
изменить знаки дуг на противоположные и решить задачу о крат-
чайшем пути. Для существования решения задачи о максимальном
пути необходимо и достаточно отсутствия контуров положитель-
ной длины.
В задаче поиска пути максимальной надежности длины дуг
интерпретируются, например, как вероятности того, что существу-
ет связь между соответствующими двумя пунктами. Заменяя дли-
ны дуг их логарифмами, взятыми с обратными знаками, получаем,

10
что путь максимальной надежности в исходном графе будет соот-
ветствовать кратчайшему пути в новом графе.
Гораздо более сложными (NP-полными1) являются задачи по-
иска элементарных путей кратчайшей (максимальной) длины в
случае, когда в сети имеются контуры отрицательной (соответст-
венно, положительной) длины2. Эффективных (не сводящихся к
полному перебору) точных алгоритмов для них не существует.
К таким же сложным задачам относятся и задачи поиска крат-
чайших или длиннейших путей или контуров, проходящих через
все вершины графа (элементарный путь (контур), проходящий
через все вершины графа, называется гамильтоновым путем (кон-
туром)). Классическим примером задачи поиска гамильтонова
контура является задача коммивояжера, заключающаяся в сле-
дующем. Коммивояжер (бродячий торговец) должен посетить n
городов, побывав в каждом ровно один раз, и вернуться в исход-
ный пункт своего путешествия. Заданы неотрицательные длины
дуг, интерпретируемые как расстояние между городами или стои-
мости проезда. Требуется найти гамильтонов контур минимальной
длины (в графе из n вершин существует n! (число перестановок)
гамильтоновых контуров).
Алгоритмы решения задачи о кратчайшем пути позволяют
решать широкий класс задач дискретной оптимизации. В качестве
примера приведем задачу целочисленного линейного программи-
рования – задачу о ранце (о рюкзаке), к которой сводятся многие
практически важные задачи определения оптимальной комбинации
факторов при ограничениях на общий вес, площадь, объем, финан-
сирование и т.д.
Задача о ранце. Пусть имеется n предметов, которые могут
быть полезны в походе. Полезность i-го предмета оценивается

1
Качественно, если n – число вершин графа, то, если сложность (количество
вычислений, операций, шагов и т.д.) алгоритма поиска точного решения пропор-
циональна n?, где ? – некоторое положительное число, то говорят, что алго-
ритм имеет полиномиальную сложность. Если сложность пропорциональна ?n,
то имеет место экспоненциальная сложность (NP-полнота).
2
Существуют несколько алгоритмов проверки отсутствия контуров отрица-
тельной (или положительной) длины: изменять индексы, пока число шагов
алгоритма не превысит максимально необходимое (равное m n) число; ограни-
чить потенциалы вершин заданными числами di и при ?i ? di (?i ? di) проверять
действительно ли полученное значение потенциала соответствует длине неко-
торого пути, или имеется контур отрицательной (положительной) длины; и др.
11
числом ai, вес предмета (или его объем) – bi. Суммарный вес,
который может нести турист (объем рюкзака), ограничен величи-
ной R. Требуется найти набор предметов, обладающий максималь-
ной суммарной полезностью и удовлетворяющий ограничению.
Обозначим xi – переменную, принимающую значение ноль
(если i-ый предмет не кладется в ранец) или единица (если i-ый
предмет кладется в ранец). Тогда задача о ранце имеет вид:
n
? a i xi > max
(6)
x
i =1
n
? bi xi ? R.
(7)
i =1
Верхняя оценка числа возможных комбинаций – 2n. Однако
для решения задачи о ранце существует эффективный алгоритм –
метод динамического программирования. При его использовании
строится сеть (см. примеры в [7, 8, 12]) по следующим правилам.
По оси абсцисс будем последовательно откладывать номера пред-
метов, по оси ординат – их вес. Из каждой точки (начиная с точки
(0; 0)) выходят две дуги – горизонтальная (соответствующая аль-
тернативе «не брать предмет») и наклонная (соответствующая
альтернативе «взять предмет»), вертикальная проекция которой
равна весу предмета. Длины наклонных дуг положим равными
ценности предметов, длины горизонтальных дуг – нулю. Получен-
ная сеть (конечная вершина является фиктивной и вес любой дуги,
соединяющей ее с другими вершинами, равен нулю) обладает
следующими свойствами: любому решению задачи (6)-(7) соответ-
ствует некоторый путь в этой сети; любому пути соответствует
некоторое решение задачи. Таким образом, задача свелась к нахо-
ждению пути максимальной длины.
Задача поиска контура минимальной длины решается сле-
дующим образом. Если известно, что искомый контур содержит
некоторую вершину, то нужно определить кратчайшей путь от
этой вершины до нее же, применяя описанные выше алгоритмы.
Так как в общем случае контур минимальной длины может прохо-
дить через любую вершину графа, то находятся контуры мини-
мальной длины, проходящие через каждую вершину, и среди них
выбирается кратчайший. Более простым является следующий
алгоритм 4: берется первая вершина (в произвольном их упорядо-
чении) графа и рассматривается сеть, в которой эта вершина явля-
12
ется одновременно конечной и начальной вершиной. Для этой сети
(применением описанного выше алгоритма) ищется путь µ1 мини-
мальной длины L(µ1). Затем первая вершина отбрасывается, и
минимальный путь µ2 ищется для сети, в которой начальной и
конечной вершиной является вторая вершина. Затем отбрасывается
вторая вершина и т.д. для всех вершин исходного графа, для кото-
рых существует контур, проходящий через них и через вершины с
большими номерами. Контуром минимальной длины будет контур
µmin, длина которого равна L(µmin) = min {L(µ1), L(µ2), ,..., L(µn)}.
Задача поиска контура минимальной средней длины за-
ключается в поиске контура, для которого минимально отношение

<< Предыдущая

стр. 2
(из 5 стр.)

ОГЛАВЛЕНИЕ

Следующая >>