5. Поток минимальной стоимости от s к t

В разделе 2 мы рассмотрели задачу максимизации потока от безотносительно к какой-либо стоимости. Теперь мы рассмотрим задачу нахождения такого потока заданной величины от стоимость которого минимальна. В этой задаче каждая дуга имеет два связанных с ней числа — пропускную способность и стоимость единицы потока по этой дуге.

Очевидно, что если больше, чем значение максимального потока от к то не существует никакого решения. Если же не превышает этого значения, то, вообще говоря, может существовать несколько различных потоков и требуется найти поток величины обеспечивающий минимальную стоимость. Наиболее известной процедурой решения задачи о потоке с минимальной стоимостью является так называемый алгоритм «беспорядка» Форда и Фалкерсона, и интересующийся читатель может найти описание этого эффективного алгоритма в [12], [4] и [7]. Алгоритмы, которые мы здесь опишем, принадлежат Клейну [20] и Басакеру и Гауэну [6]. Эти алгоритмы концептуально проще, чем метод беспорядка, и используют уже введенную технику. С вычислительной точки зрения эти методы сравнимы [2].

5.1. Алгоритм, основанный на выявлении отрицательных циклов

Предположим, что в графе существует допустимый поток со значением и что этот поток известен. Такой поток может быть получен с помощью алгоритма максимального потока (от s к t) из разд. 2 и добавления потока общей величины на всех аугментальных цепях (шаги с 4 по 6 алгоритма) до тех пор, пока поток не достигнет значения которое по условию меньше значения максимального потока.

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

Для каждой дуги положим

Для каждой дуги положим

Новый граф дает теперь инкрементальные пропускные способности и стоимости (относительно начального потока любого дополнительного потока, введенного в Алгоритм основан на следующей теореме.

Теорема 5. Поток будет потоком минимальной стоимости со значением тогда и только тогда, когда в (|) не существует никакого цикла сумма стоимости дуг которого отрицательна.

Доказательство. Пусть с стоимость потока в графе сумма стоимости в цикле по отношению к графу

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

Достаточность. Допустим, что в графе для каждого цикла и что поток минимальной стоимости со значением Обозначим теперь через поток, значение которого на дуге равно

Так как и можно разложить в сумму потоков (от по цепям в то построение унитарного графа (см. разд. 2.4) для потока дает следующие полустепени вершин:

Так как в соответствии с разд. состоит из наборов конформальных единичных потоков по циклам (например), то мы можем написать

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

Рассмотрим теперь инкрементальный граф Единственными дугами этого графа, стоимости которых уменьшились по сравнению с соответствующими стоимостями в графе являются те, которые будут «обращениями» дуг в Но, так как потоки конформальны, такие дуги не могут быть использованы ни одним из оставшихся циклов следовательно, не влияют на последующие рассуждения.

Теперь мы имеем

для любого

Стоимость потока равна тогда С

Продолжая рассуждения аналогичным образом, мы получим окончательно с а это противоречит предположению о том, что поток минимальной стоимости со значением Теорема доказана.

Таким образом, в соответствии с теоремой 5, все, что требуется для нахождения потока минимальной стоимости со значением это начать с допустимого потока со значением построить граф (|) и проверить, нет ли в нем циклов с отрицательной стоимостью, используя любой из алгоритмов нахождения кратчайшей цепи, данных в разд. 3 и 4 гл. 9. Если не существует никакого цикла с отрицательной стоимостью, то поток будет потоком минимальной стоимости. Если цикл с отрицательной стоимостью существует, то надо «пустить» по нему поток с максимально возможным значением 6. Суммарный поток от не изменит своего значения у, а его стоимость уменьшится на где с величина стоимости отрицательного цикла. Очевидно, должно быть выбрано так, чтобы пропускные способности дуг в не превышались, т. е.

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

5.1.1. Описание алгоритма

Шаг 1. Использовать алгоритм максимального потока (от из разд. 2 для нахождения в графе допустимого потока со значением

Шаг 2. Построить для этого потока граф пользуясь цанными ранее правилами.

Шаг 3. Отправляясь от матрицы стоимостей графа и используя алгоритм кратчайшей цепи (см. разд. 3.1 и 4 гл. 8), определить, существует ли в графе цикл с отрицательной стоимостью. Если такой цикл существует, то найти его (цикл )

Рис. 11.13. Граф из примера 5.1.2. Первая пометка является пропускной способностью дуги, вторая — стоимостью дуги.

и перейти к шагу 5. Если такого цикла нет, то остановиться. Поток будет потоком минимальной стоимости.

Шаг 4. По (11.11) вычислить

(I) Для всех изменить поток в соответствующей дуге из на

(II) Для всех изменить поток в соответствующей дуге из на

Шаг 5. Повторить шаг 2, начиная с нового потока

5.1.2. Пример.

Рассмотрим граф изображенный на рис. 11.13, где первое число пометки у каждой дуги равно ее пропускной способности, а второе — стоимости. Мы хотим найтв поток от минимальной стоимости со значением 20.

Для выявления циклов с отрицательной стоимостью на шаге с вышеописанного метода используем алгоритм кратчайшей Флойда (разд. 3.1 гл. 8).

Шаг 1. Алгоритм максимального потока дает первый допустимый поток, изображенный на рис. 11.14а. Стоимость этого потокг

Рис. 11.14а. Начальный поток

равна

Шаг 2. Исходя из этого потока, построим граф как доказано на рис. 11.146, где цикл отрицательной стоимости изображен пунктиром.

Шаг 3. Начиная с матрицы стоимостей

(где на пустых местах должны стоять элементы и применяя алгоритм Флойда, получаем следующие матрицы наименьших стоимостей вместе с соответствующими им матрицами цепей:

В последней итерации элемент получается отрицательным, со значением —15, которое показывает существование цикла отрицательной стоимости, содержащего вершину Этот цикл, найденный по матрице цепей, имеет вид

Шаг 4. Из (11.11) находим значение 6:

(см. скан)

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

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

Шаг 3. Обнаружен отрицательный цикл со стоимостью —10.

Шаг 4.

Новый поток со стоимостью 512 изображен на рис. 11.14д.

Шаг 2. Граф соответствующий новому потоку, изображен на рис.

Шаг 3. Обнаружен отрицательный цикл со стоимостью —8.

Шаг 4.

Новый поток со стоимостью 480 изображен на рис. 11.14ж.

Шаг 2. Получившийся граф показан на рис. 11.14з.

Шаг 3. Обнаружен отрицательный цикл со стоимостью —4.

Шаг 4.

Новый поток со стоимостью 476 изображен на рис. 11.14 и.

Шаг 2. Граф изображен на рис.

Шаг 3. Обнаружен отрицательный цикл со стоимостью —2.

Шаг 4.

Рис. 11.14л. Поток минимальной стоимости.

Новый поток со стоимостью 474 изображен на рис.

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

5.1.3. Шаг 3 из алгоритма 5.1.1.

В вышеприведенном примере был использован метод Флойда для нахождения циклов отрицательной стоимости в инкрементальном графе на шаге 3 алгоритма определения потока минимальной стоимости, данного в разд. 5.1.1. Но, как уже отмечалось в разд. 4 гл. 8, это не лучший метод выявления циклов отрицательной стоимости для графа в котором существует вершина достижимая из всех других вершин Лучший способ состоит в использовании алгоритма, который находит кратчайшую цепь от ко всем другим вершинам, а не в применении алгоритма Флойда, находящего кратчайшие цепи между каждой парой вершин [2]. В этом отношении более успешно, как это объясняется в разд. 4 настоящей главы, может быть использован алгоритм кратчайшей цепи из разд. 2.2.1 главы 8.

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

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

Поэтому в инкрементальном графе (|) все вершины могут быть достигнуты из и если эта вершина используется в качестве источника при нахождении кратчайшей цепи от ко всем другим вершинам из (например, с использованием алгоритма из 2.2.1 гл. 8), то все циклы отрицательной стоимости в могут быть обнаружены.

Используя такой подход при организации шага 3 основного алгоритма потока минимальной стоимости из разд. 5.1, Беннингтон [2] опубликовал вычислительные результаты, показывающие, что этот алгоритм не хуже алгоритма «беспорядка» [12, 4, 7]. Применение метода наименьших квадратов к оценке требуемого времени вычисления по тестам, использующим случайно

порожденные графы с вершинами и дугами, дало такой результат:

Граф с 200 вершинами и 5000 дугами требует приблизительно 8 с машинного времени.

5.1.4. Потоки минимальной стоимости в графах с выпуклыми функциями стоимости

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

Рис. 11.15. Выпуклая функция стоимости дуг.

Однако это не является необходимым предположением и, как показали Ху [17] и Клейн [20], алгоритм, описанный в 5.1.1, можно легко применить и для нахождения потоков минимальной стоимости в графах, стоимости дуг которых являются выпуклыми кусочно-линейными функциями потока.

Если допустить, что стоимость потока по дуге задается выпуклой функцией изображенной на рисунке 11.15, то для любого потока мы можем определить инкрементальный граф точно так же, как это делалось в разд. 2.3, за исключением того, что теперь никогда не нужно вычислять пропускные способности дуг а стоимости дуг таковы:

для дуги положим

для дуги положим

считая, что

Теперь мы можем непосредственно использовать алгоритм из разд. 5.1.1, за исключением того, что поток, посылаемый по любому циклу отрицательной стоимости, который можно найти в всегда берется равным 1. Заметим, что все инкрементальные стоимости были определены так, чтобы они приводили к увеличению или уменьшению значения потока на одну единицу. Заметим также, что при использовании только «единичных» преобразований потоков (т. е. при уменьшении или увеличении значения потока только на единицу) нет необходимости вычислять инкрементальные пропускные способности дуг в так как эти величины нужны лишь для вычисления

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