![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Int costRto(int v)
{ return from(v)? -pcost: pcost; } Обход обратных ребер соответствует удалению потока из соответствующего ребра исходной сети, так что стоимость изменяется на соответствующую величину. В связи с наличием стоимостей ребер, эти сети могут иметь циклы с отрицательной стоимостью. Понятие отрицательных циклов, которое показалось нам несколько искусственным при первой встрече с ним, когда мы рассматривали его в контексте алгоритмов построения кратчайшего пути, играет фундаментальную роль в алгоритмах, как сейчас можно будет в этом убедиться. Мы рассмотрим два алгоритма, оба они основаны на следующем условии оптимальности. Свойство 22.23. Максимальный поток является максимальным потоком минимальной стоимости (mincost maxflow) тогда и только тогда, если его остаточная сеть не содержит (ориентированного) цикла с отрицательной стоимостью. Доказательство: Предположим, что задан максимальный поток минимальной стоимости, остаточная сеть которого содержит цикл с отрицательной стоимостью. Пусть х есть пропускная способность ребра с минимально пропускной способностью в цикле. Увеличим поток, добавляя х в ребра в потоке, соответствующем ребрам с положительной стоимостью в остаточной сети (прямые ребра) и вычитая х из ребер, соответствующих ребрам с отрицательной стоимостью в остаточной сети (обратные ребра). Эти изменения не оказывают влияния на разность между притоком и истечением любой вершины, однако они меняют стоимость сети на стоимость цикла, умноженную на х, которая принимает отрицательное значение, что противоречит условию, согласно которому стоимость исходного потока минимальна. Чтобы доказать обратное, предположим, что существует максимальный поток F без циклов отрицательной стоимости, стоимость которых не является минимальной, и рассмотрим любой максимальный поток М с минимальной стоимостью. В силу рассуждений, аналогичных использованным при доказательстве теоремы о разложении потоков (свойство 22.2), мы можем найти самое большее Е ориентированных циклов таких, что добавление этих циклов к потоку F дает поток М. Тем не менее, поскольку F не имеет отрицательных циклов, эта операция не может понизить стоимости потока F, т.е. получаем противоречие. Другими словами, мы должны быть способными преобразовать F в М за счет наращивания циклов, однако мы не можем это сделать, поскольку нет циклов отрицательной стоимости, которые можно было бы использовать для понижения стоимости потока. ■ Это свойство немедленно приводит к простому обобщенному алгоритму решения задачи о потоке минимальной стоимости, получившего название алгоритма вычеркивания циклов (cycle-canceling algorithm): Найти максимальный поток. Увеличить поток в произвольном цикле с отрицательной стоимости в остаточной сети, продолжая эту процедуру до тех пор, пока не останется ни одного такого цикла. Глава 22, Потоки в сетях Этот метод объединяет механизмы, которые были разработаны на протяжении всей этой и предыдущих глав, обеспечивающие построение эффективных алгоритмов решения широкого класса задач, подпадающих под модель потока минимальной стоимости. Подобно нескольким другим обобщенным методам, с которыми нам приходилось сталкиваться, он допускает несколько различных реализаций, поскольку методы отыскания начального максимального потока и отыскания циклов с отрицательной стоимости не описаны. На рис. 22.41 показан пример вычисления максимального потока, который использует алгоритм вычеркивания циклов. Поскольку мы уже разработали алгоритмы вычисления максимального потока и поиска отрицательных циклов, мы сразу же получаем реализацию алгоритма вычеркивания циклов, представленную программой 22.9. Мы используем любую реализацию максимального потока для вычисления начального максимального потока и алгоритм Беллмана-Форда поиска отрицательных циклов (см. упражнение 22.108). К двум этим реализациям в такую реализацию остается только добавить цикл, обеспечивающий наращивание потоков в циклах на графах.
|