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

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

Так как для любой дуги {Xi, Xj) из G, для которой существует некоторый ненулевой поток, в инкрементальном графе G () существует дуга (xf, xf), то все вершины xf из G> (), соответствующие вершинам Xi из G, лежащим на цепях потока от s к t, могут быть достигнуты из f с использованием обратных цепей, образованных дугами (xf, xf). Таким же способом может быть достигнут источник S. Итак, каждая вершина Xi из G может быть достигнута из s (в противном случае Xi может быть удалена из G, и это не повлияет на поток). Следовательно, так как дуги (Xj, xj), не несущие никакого потока в G, появляются в G> () в качестве дуг {xf, xf), вершины xf из (), соответствующие вершинам Xi из G, не лежащим на цепях потока, могут быть достигнуты из t через S. Иными словами, сначала просто достигаем s, как бы.то сказано выше, а затем следуем по пути яз s ъ xf.

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

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

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

t = -2,3 + 0,0113ге + 0,00166те (время в секундах

на машине ИБМ 360/75).

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

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

До сих пор предполагалось, что стоимость единицы потока по дуге {Xi, Xj) есть Cjj - постоянная величина. Однако это не является необходимым предположением и, как показали Ху [17]

J \ \ L

0 1 2 3 4 5

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

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

Если допустить, что стоимость потока по дуге (ж,-, Xj) задается выпуклой функцией Wij (Itj), изображенной на рисунке 11.15, то для любого потока мы можем определить инкрементальный граф G (I) = {X, (J Af) точно так же, как это делалось в разд. 2.3, за исключением того, что теперь никогда не нужно вычислять пропускные способности дуг qfj и qi, а стоимости дуг таковы:

для дуги {х^, х^) А^ положим

для дуги (х , xf) 6 Af положим

считая, что Wij (0) = 0.

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

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

5.2. Алгоритм, основанный на цепи наименьшей стоимости

Алгоритм из разд. 5.1 начинает работу с произвольного потока со значением и, после чего происходит постепенное улучшение потока до тех пор, пока не будет получен поток * минимальной стоимости. В терминологии математического программирования такой алгоритм следовало бы назвать основным алгоритмом, так как его первая цель состоит в получении допустимого потока, а затем поток улучшается с сохранением допустимости. Альтернативным подходом является двойственный метод, в котором для решения этой задачи начинают с построения потока * с минимальной стоимостью, имеющего некоторое значение Vq <i v, а затем добавляют в граф некоторый дополнительный поток, чтобы получить новый поток с минимальной стоимостью, имеющий значение 1 > Vq, и т. д. пока не будет построен поток с минимальной стоимостью со значением v. В отношении этого метода следует