Поток максимальной мощности минимальной стоимости

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

Рассмотрим ориентированный граф \(G = (V, E)\) с истоком \(s\) и стоком \(t\) , в котором у каждого ребра \((u, v)\) задана целая стоимость \(w_\) и целая положительная пропускная способность \(c_\) . Требуется найти максимальный поток, стоимость которого минимальна:

Заметим, что рёбра отрицательной стоимости по условию возможны. Мы дополнительно предполагаем, что циклов отрицательного веса нет.

Модифицируем сеть, добавив стандартным образом обратные рёбра, позволяющие «отменять» операции: для каждого ребра \((u, v)\) добавим \((v, u)\) , для которого \(c_ = 0\) и \(w_ = -w_\) . Напомним, что остаточной сетью называется граф из рёбер, остаточная пропускная способность которых ненулевая ( \(c_-f_ > 0\) ).

Критерий оптимальности

Если в остаточной сети нет циклов отрицательного веса, то поток оптимален (и наоборот).

Доказательство:

\(\rightarrow\) Рассмотрим произвольный неоптимальный поток \(f\) и оптимальный поток \(f^*\) . Рассмотрим разность \(f^*-f\) . Она является циркуляцией, а любая циркуляция может быть разложена на сумму простых циклов. Хотя бы один из этих циклов будет иметь отрицательную стоимость, так как стоимость \(f^*\) меньше стоимости \(f\) , что противоречит предположению.

\(\leftarrow\) Пусть цикл существует, тогда мы можем пропустить поток по этому циклу и получить поток меньшей стоимости.

Отмена циклов

Этот критерий сразу даёт нам относительно простой алгоритм: найдем какой-нибудь максимальный поток и будем «отменять» циклы отрицательного веса в остаточной цепи, пока такие циклы существуют. Искать цикл нам придётся не более \(mUC\) раз где \(U\) — величина потока, \(C\) — максимальная пропускная способность ребра. Этой величиной ограничен модуль минимальной стоимости ответа, а каждый отмененный цикл уменьшает ответ хотя бы на единицу.

Если искать цикл алгоритмом Форда-Беллмана, то асимптотика алгоритма составит \(O(m^2nUC)\) (предполагая, что какой-нибудь максимальный поток мы уже нашли).

Дополняющие пути

Вспомним общий алгоритм поиска максимального потока, основанный на теореме Форда-Фалкерсона: найти какой-нибудь дополняющий путь, пропустить по нему поток и модифицировать сеть, снова найти дополняющий путь и так далее, пока путь из истока в сток существует. Что будет, если мы каждый раз будем искать не произвольный путь, а путь минимальной стоимости? Утверждается, что такой алгоритм найдет максимальный поток минимальной стоимости.

Утверждение. Алгоритм не создает в остаточной сети циклов отрицательного веса.

Изначально в остаточной сети нет циклов отрицательного веса. Мы нашли минимальный путь из \(s\) в \(t\) и модифицировали сеть, возможно добавив какие-то обратные рёбра. Могли ли из-за этих рёбер появиться циклы отрицательного веса? Пусть какое-нибудь обратное ребро \((v, u)\) находится в цикле отрицательного веса. Тогда есть путь Из \(u\) в \(v\) стоимости меньше, чем \(w_\) . Но такое не могло произойти: если бы такой путь существовал, то на этапе поиска дополняющего пути мы выбрали бы его вместо ребра \((u, v)\) .

Для поиска дополняющего пути можно использовать алгоритм Форда-Беллмана. Асимптотика в данном случае составит \(O(nmU)\) — искать каждый дополняющий путь мы будем не более \(U\) раз.

Почему мы не использовали алгоритм Дейкстры? Проблема в рёбрах отрицательного веса. Даже если в исходном графе их нет, они могут в процессе алгоритма появиться как обратные. Покажем, как изменить веса рёбер так, чтобы они стали неотрицательными, но информация о кратчайших путях не утратилась: это можно сделать, если дать каждой вершине так называемый «потенциал», который будет учитываться при пересчете стоимостей ребер.

Потенциалы Джонсона

Потенциалом вершины \(v\) будем называть расстояние \(d_v\) от вершины \(s\) . Рассмотрим граф из всех достижимых вершин и тех же рёбер, только с изменёнными весами:

Утверждение 1. Веса всех рёбер графа неотрицательные.

Доказательство. Пусть вес какого-то ребра \((u, v)\) отрицателен, то есть \(w_‘ = w_ + d_u — d_v . Тогда \(d_u + w_ , и нарушилось неравенство треугольника: почему мы тогда не использовали ребро \((u, v)\) , когда искали кратчайший путь до \(v\) ?

Аналогично можно показать, что рёбра на кратчайших путях из \(s\) имеют нулевую стоимость. Заметим, что стоимость обратных рёбер на кратчайших путях тоже будет нулевой: \[ w_‘ = w_ + d_v — d_u = -w_ — d_u + d_v = -(w_) = 0 \]

Утверждение 2. Кратчайшие пути между любыми вершинами остались кратчайшими.

Доказательство. Распишем новую стоимость пути из \(a\) в \(z\) .

\[ \begin w_‘ + \ldots + w_‘ &= (w_ + \ldots + w_) + (d_a + \ldots + d_y) — (d_b + \ldots + d_z) \\&= (w_ + \ldots + w_) + d_a — d_z \end \]

Получаем, что стоимость всех путей из \(a\) в \(z\) лишь изменилась на константу.

Более того, если мы добавим или удалим некоторые рёбра из графа, потенциалы тоже никак не повлияют на кратчайшие пути.

Заметьте, что в доказательстве мы не использовали то, что \(d_v\) — кратчайшие расстояния. Это вообще могут быть произвольные числа.

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

Доказательство. Все добавленные обратные рёбра на кратчайшем пути будут иметь нулевую стомость (утверждение 1), а добавления или удаления рёбер на кратчайшие пути не повлияли (утверждение 2).

Итоговый алгоритм

• Модифицируем сеть, добавив обратные рёбра.
• Если в исходном графе есть рёбра отрицательного веса (но нет циклов отрицательного веса), то посчитать изначальные потенциалы (расстояния) алгоритмом Форда-Беллмана. Иначе достаточно положить потенциалы изначально равными нулю.
• Пока максимальный поток не найден:
• • Посчитать алгоритмом Дейкстры кратчайшие расстояния от \(s\) , используя для веса формулу с потенциалами, записать их в \(d\) .
• • Протолкнуть максимально возможный поток вдоль кратчайшего пути \(s \leadsto t\) , обновить остаточную сеть.

Реализация

Ниже приведено решение задачи о назначениях (паросочетание минимального веса). Для нахождения дополняющего пути используется алгоритм Дейкстры для плотных графов (без приоритетной очереди — каждую итерацию ищется минимум за \(O(n)\) ).

• cost , cap — параметры сети
• pot — потенциалы
• par — предок вершины в алгоритме Дейкстры (нужен для проталкивания потока)
• d — временный массив для алгоритма Дейкстры, куда будут записаны новые расстояния

Асимптотика

В общем случае, алгоритм работает за \(O(U m \log n)\) или \(O(U n^2)\) в случае плотных графов.

В наиболее популярных задачах рёбра обычно с единичной пропускной способностью, и \(U \leq n\) или \(U \leq m\) . Например, в задаче о назначениях \(U = n\) , и алгоритм работает за \(O(n^3)\) , что совпадает с асимптотикой венгерского алгоритма.

Источник

Поток минимальной стоимости (min-cost-flow). Алгоритм увеличивающих путей

Дана сеть G, состоящая из N вершин и M рёбер. У каждого ребра (вообще говоря, ориентированному, но по этому поводу см. ниже) указана пропускная способность (целое неотрицательное число) и стоимость единицы потока вдоль этого ребра (некоторое целое число). В графе указан исток S и сток T. Даётся некоторая величина K потока, требуется найти поток этой величины, причём среди всех потоков этой величины выбрать поток с наименьшей стоимостью («задача min-cost-flow»).

Иногда задачу ставят немного по-другому: требуется найти максимальный поток наименьшей стоимости («задача min-cost-max-flow»).

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

Описание

Простейший случай

Рассмотрим для начала простейший случай, когда граф — ориентированный, и между любой парой вершин не более одного ребра (если есть ребро (i,j), то ребра (j,i) быть не должно).

Пусть U_ij — пропускная способность ребра (i,j), если это ребро существует. Пусть C_ij — стоимость единицы потока вдоль ребра (i,j). Пусть F_ij — величина потока вдоль ребра (i,j), изначально все величины потоков равны нулю.

Модифицируем сеть следующим образом: для каждого ребра (i,j) добавим в сеть так называемое обратное ребро (j,i) с пропускной способностью U_ji = 0 и стоимостью C_ji = — C_ij. Поскольку, по нашему предположению, ребра (j,i) до этого в сети не было, то модифицированная таким образом сеть по-прежнему не будет мультиграфом. Кроме того, на всём протяжении работы алгоритма будем поддерживать верным условие: F_ji = — F_ij.

Определим остаточную сеть для некоторого зафиксированного потока F следующим образом (собственно, так же, как и в алгоритме Форда-Фалкерсона): остаточной сети принадлежат только ненасыщенные рёбра (т.е. у которых F_ij 3 M), правда, алгоритм Дейкстры придётся модифицировать, чтобы он работал на графах с отрицательными весами (это называется алгоритм Дейкстры с потенциалами).

Вместо этого можно использовать алгоритм Левита, который, хотя и асимптотически намного хуже, но на практике работает очень быстро (примерно за то же время, что и алгоритм Дейкстры).

Реализация

Здесь приведена реализация алгоритма min-cost-flow, базирующаяся на алгоритме Левита.

На вход алгоритма подаётся сеть (неориентированный мультиграф) с N вершинами и M рёбрами, и K — величина потока, который нужно найти. Алгоритм находит поток величины K минимальной стоимости, если такой существует. Иначе он находит поток максимальной величины минимальной стоимости.

В программе есть специальная функция для добавления ориентированного ребра. Если нужно добавить неориентированное ребро, то эту функцию нужно вызывать для каждого ребра (i,j) дважды: от (i,j) и от (j,i).

Источник

Задача минимальной стоимости потока — Minimum-cost flow problem

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

Содержание

• 1 Определение
• 2 Отношение к другим проблемам
• 3 Решения
• 4 Применение
  • 4.1 Двудольное сопоставление с минимальным весом
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

Определение

Потоковая сеть — это ориентированный граф с исходной вершиной и вершиной- приемником , где каждое ребро имеет пропускную способность , поток и стоимость , при этом большинство алгоритмов потока с минимальной стоимостью поддерживают ребра с отрицательной стоимостью. Стоимость отправки этого потока по ребру составляет . Проблема требует, чтобы поток был отправлен от источника к приемнику . г знак равно ( V , E ) <\ Displaystyle G = (V, E)> s ∈ V <\ displaystyle s \ in V> т ∈ V <\ displaystyle t \ in V> ( ты , v ) ∈ E <\ displaystyle (u, v) \ in E> 0>»> c ( ты , v ) > 0 <\ Displaystyle с (и, v)>0> 0″> ж ( ты , v ) ≥ 0 <\ Displaystyle е (и, v) \ geq 0> а ( ты , v ) <\ Displaystyle а (и, v)> ( ты , v ) <\ Displaystyle (и, v)> ж ( ты , v ) ⋅ а ( ты , v ) <\ Displaystyle е (и, v) \ cdot а (и, v)> d <\ displaystyle d> s <\ displaystyle s> т <\ displaystyle t>

Определение проблемы — минимизировать общую стоимость потока по всем ребрам:

∑ ( ты , v ) ∈ E а ( ты , v ) ⋅ ж ( ты , v ) <\ Displaystyle \ сумма _ <(и, v) \ в Е>а (и, v) \ CDOT F (и, v)>

Отношение к другим проблемам

Вариант этой проблемы — найти максимальный поток, но с наименьшими затратами среди решений с максимальным потоком. Это можно назвать проблемой минимальной стоимости и максимального потока, и она полезна для поиска сопоставлений минимальной стоимости и максимальной .

В некоторых решениях найти максимальный поток с минимальной стоимостью очень просто. Если нет, то можно найти поток максимального посредством выполнения двоичного поиска на . d <\ displaystyle d>

Связанная с этим проблема — проблема обращения с минимальными затратами , которую можно использовать для решения потока минимальных затрат. Это достигается путем установления нижней границы по всем краям до нуля, а затем сделать дополнительный край от раковины к источнику , с мощностью и нижней границы , заставляя общий поток от до также быть . т <\ displaystyle t> s <\ displaystyle s> c ( т , s ) знак равно d <\ displaystyle c (t, s) = d> л ( т , s ) знак равно d <\ displaystyle l (t, s) = d> s <\ displaystyle s> т <\ displaystyle t> d <\ displaystyle d>

Следующие задачи являются частными случаями задачи о потоках с минимальными затратами (мы по очереди даем краткие наброски каждого применимого сокращения):

• Проблема кратчайшего пути (из одного источника). Требовать, чтобы возможное решение проблемы потока с минимальной стоимостью отправляло одну единицу потока от назначенного источника к назначенному приемнику . Дайте всем ребрам бесконечную емкость. s <\ displaystyle s>т <\ displaystyle t>
• Задача максимального расхода . Пусть все узлы имеют нулевой спрос, и пусть стоимость, связанная с прохождением любого ребра, равна нулю. Теперь представьте новый край от текущего стока к текущему источнику . Предположите, что удельная стоимость отправки потока через границу равна , и разрешить бесконечную пропускную способность. (Это сокращение также упоминается в проблеме обращения ). ( т , s ) <\ Displaystyle (т, с)>т <\ displaystyle t>s <\ displaystyle s>( т , s ) <\ Displaystyle (т, с)>— 1 <\ displaystyle -1>( т , s ) <\ Displaystyle (т, с)>
• Проблема с присвоением . Предположим, что каждое частичное множество в двудольном множестве имеет вершины, и обозначим двудольность через . Дайте каждое предложение и дайте каждое требование . Каждое ребро должно иметь единицу мощности. п <\ displaystyle n>( Икс , Y ) <\ displaystyle (X, Y)>Икс ∈ Икс <\ displaystyle x \ in X>1 / п <\ displaystyle 1 / n>у ∈ Y <\ displaystyle y \ in Y>1 / п <\ displaystyle 1 / n>

Решения

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

Кроме того, существует множество комбинаторных алгоритмов, подробный обзор см. Некоторые из них являются обобщениями алгоритмов максимального потока , другие используют совершенно другие подходы.

Известные фундаментальные алгоритмы (их много вариаций):

• Отмена цикла : общий основной метод.
• Отмена минимального среднего цикла : простой сильно полиномиальный алгоритм.
• Последовательный кратчайший путь и масштабирование емкости : двойные методы, которые можно рассматривать как обобщение алгоритма Форда – Фулкерсона .
• Масштабирование затрат : первично-двойной подход, который можно рассматривать как обобщение алгоритма push-relabel .
• Сетевой симплексный алгоритм : специализированная версия симплексного методалинейного программирования .
• Необычный алгоритмД. Р. Фулкерсона

заявка

Двудольное соответствие минимального веса

Для двудольного графа G = ( A ∪ B , E ) цель состоит в том, чтобы найти максимальное соответствие мощности в G, которое имеет минимальную стоимость. Пусть ш : Е → R является функцией веса по краям Е . Задача двустороннего согласования с минимальным весом или задача назначения состоит в том, чтобы найти идеальное согласование M ⊆ E , общий вес которого минимизирован. Идея состоит в том, чтобы свести эту проблему к проблеме сетевого потока.

Пусть G ′ = ( V ′ = A ∪ B , E ′ = E ). Присвойте емкость всех ребер в E ′ равной 1. Добавьте исходную вершину s и соедините ее со всеми вершинами в A ′, добавьте вершину приемника t и соедините все вершины внутри группы B ′ с этой вершиной. Вместимость всех новых ребер равна 1, а их стоимость равна 0. Доказано, что существует совершенное двудольное паросочетание с минимальным весом в G тогда и только тогда, когда существует поток с минимальной стоимостью в G ‘ .

Источник