Int negcyc(int);

int negcyc(); public:

MINCOST(const Graph & G, int s, int t): G(G), s(s), t(t), st(G.V()), wt(G.V())

{ MAXFLOW< Graph, Edge> (G, s, t); for (int x = negcyc (); x! = -1; x = negcyc ()) { augment(x, x); }

} };

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

Часть 5. Алгоритмы на графах

РИСУНОК 22.41. ОСТАТОЧНЫЕ СЕТИ (ВЫЧЕРКИВАНИЕ ЦИКЛОВ)

Каждый из потоков, показанных на этом рисунке, представляет собой максимальный поток в транспортной сети в верхней части рисунка, но только поток, изображенный в нижней части является максимальным потоком минимальной стоимости. Чтобы найти его, мы начинаем вычисления, имея произвольный максимальный поток, и наращиваем поток, используя отрицательные циклы. Стоимость начального максимально­го потока (второй вверху) равна 22 единицам, но он не является максималь­ным потоком минималь­ной стоимости, посколь­ку остаточная сеть (показана справа) содержит три отрица­тельных цикла. В этом примере мы производим наращивание потока вдоль пути 4-1-0-2-4, чтобы получит макси­мальный поток со стоимостью 21 (третий сверху), который все еще сохраняет один отрица­тельный цикл. Наращи­вание вдоль этого цикла дает поток минимальной стоимости (внизу). Обратите внимание на тот факт, что наращи­вание вдоль пути 3-2-4-1-3 дало бы нам максимальный поток минимальной стоимости всего за один шаг.

Глава 22. Потоки в сетях

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

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

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

Свойство 22.24. Число аугментальных циклов, необходимых для выполнения обобщенного алгоритма вычеркивания циклов, не превосходит ЕСМ.

Доказательство: В худшем случае каждое ребро в начальном потоке имеет пропуск­ную способность М, стоимость С и заполнено. Каждый цикл уменьшает эту стоимость, по меньшей мере, на 1. ■

Следствие. Время, необходимое для решения задачи о максимальном потоке минимальной стоимости в разреженной сети, есть O(V³CM).

Доказательство: Непосредственно следует из умножения числа аугментальных циклов в худшем случае на затраты на их поиск, которые определяет для худшего случая ал­горитм Беллмана-Форда (см. свойство 21.20). ■

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

Часть 5. Алгоритмы на графах

РИС. 22.42. АЛГОРИТМ ВЫЧЕРКИ­ВАНИЯ ЦИКЛОВ БЕЗ НАЧАЛЬНОГО МАКСИМАЛЬНОГО ПОТОКА

Данная последовательность диаграмм служит иллюстрацией вычисления максимального потока минимальной стоимости, начинающегося с первоначально нулевого потока, с применением алгоритма вычеркивания циклов, который использует фиктивное ребро из истока в сток в оста­точной сети с неограниченной пропускной способностью и неограниченными отрицательны­ми стоимостями. Фиктивное ребро превращает любой аугмен­тальный путь из 0 в 5 отрица­тельным циклом (однако, мы его игнорируем при наращивании потока и вычислении его стоимо­сти). Наращивание вдоль этого пути ведет к увеличению потока, как это имеет место в рамках алгоритмов построения аугмен­тальных путей (три верхних ряда). Когда нет циклов, в состав которых входит фиктивное ребро, то в остаточной сети отсут­ствуют пути из истока в сток, следовательно, мы имеем максимальный поток (третий ряд сверху). В этой точке наращивание потока вдоль отрицательного цикла уменьша­ет стоимость потока без изменения его величины (нижний ряд). В этом примере мы вычисля­ем максимальный поток, затем уменьшаем его стоимость; однако, не это главное. Напри­мер, алгоритм может увеличи­вать поток в отрицательном цикле 1-4-5-3-1 вместо цикла 0-1-4-5-0 на втором шаге. Поскольку каждое наращивание либо увеличивает поток, либо уменьшает стоимость, мы всегда в итоге получаем максимальный поток минимальной стоимости.

⇐ Предыдущая205206207208209210211212213214Следующая ⇒