Алгоритм отмены цикла минимального среднего веса

В статье описывается один из сильно полиномиальных алгоритмов решения задачи о поиске потока минимальной стоимости.

Алгоритм

Приведенный алгоритм основан на идее алгоритма Клейна отмены цикла отрицательного веса. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.

Определение:

Сильно полиномиальными (англ. strongly polynomial) в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от $V$ и $E$.

Описание

Обозначим как $c_{f}(C)$ остаточную пропускную способность цикла $C$ при протекании в сети потока $f$. Cтоимость цикла $C$ обозначим за $p(C)$, а длину (число входящих в него ребер) — за $\texttt{len}(C)$.

Определение:

Средним весом (англ. mean weight) цикла будем называть отношение его стоимости к его длине $\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}$

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

Более формально:

• Шаг $1$. Рассмотрим некоторый поток $f$.
• Шаг $2$. Найдем цикл $C$, обладающий наименьшим средним весом. Если $\mu (C) \geqslant 0$, то $f$ — поток минимальной стоимости и алгоритм завершается.
• Шаг $3$. Отменим цикл $C$, пустив по нему максимально возможный поток: $f = f + c_{f}(C)\cdot f_{C}$. Перейдем к шагу $1$.

Сложность

Для сетей с целочисленными стоимостями на ребрах $O(VE\cdot VE\log{CV})$, с вещественными — $O(VE\cdot VE^{2}\log{V})$. В обоих случаях $O(VE)$ времени тратится на поиск цикла минимального среднего веса.

Псевдокод

 func findMin
 while f
   C = c : M(c) = $\min\limits_c$ M(c)               // M(C) — вес минимального цикла
   if M(C) $\geqslant$ 0
     return f                             // тогда мы нашли f — поток минимальной стоимости, алгоритм завершается
   else
     f += c_f * f(C)                      // иначе отменим цикл

Корректность

Пусть $f$ — поток минимальной стоимости. Введём на нашей сети функцию потенциалов $\varphi$.

Определение:

Приведённой стоимостью (англ. reduced cost) ребра назовем следующую величину: $p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)$.

Иными словами, приведённая стоимость — это сколько нужно потратить денег, чтобы перевезти единицу жидкости из $u$ в $v$ (её нужно купить в $u$, перевезти из $u$ в $v$ и продать в $v$).

Лемма ($1$):

Если $f$ — поток минимальной стоимости, то $\exists \varphi$ такое, что $\forall uv: \; c_{f}(uv) \gt 0 \implies p_{\varphi}(uv) \geqslant 0$.

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

$\triangleright$

Рассмотрим остаточную сеть — граф $G_{f}$. В нем нет отрицательных циклов, так как $f$ — поток минимальной стоимости. Добавим вершину $a$ и проведем из нее ребро стоимости $0$ во все вершины графа $G_{f}$. В качестве $\varphi(u)$ выберем стоимость минимального пути из $a$ в $u$. Рассмотрим теперь некоторое ребро $uv$. Понятно, что $\varphi(v) \leqslant \varphi(u) + p(uv)$. (Здесь сравниваются минимальный путь $a \rightsquigarrow v$ и путь $a \rightsquigarrow u \rightarrow v$). Перенеся $\varphi(v)$ в другую часть неравенства, получаем $0 \leqslant \varphi(u) + p(uv) - \varphi(v)$ или $0 \leqslant p_{\varphi}(uv)$.

$\triangleleft$

Определение:

Будем говорить, что поток $f$ — $\varepsilon$-оптимальный (англ. $\varepsilon$-optimal), если $\exists \varphi$ такая, что $\forall uv: c_{f}(uv) \gt 0 \implies p_{\varphi}(uv) \geqslant -\varepsilon$.

Лемма ($2$):

Если стоимости целочисленны и поток $f$ — $\varepsilon$-оптимальный, где $\varepsilon \lt \dfrac{1}{V}$, то $f$ — поток минимальной стоимости.

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

$\triangleright$

Рассмотрим цикл в остаточной сети $C$. Заметим, что $p(C)=p_{\varphi}(C)$ (для доказательства этого факта достаточно расписать $p_{\varphi}(C)$ по определению). Возьмем $\varphi$ такое, что стоимости всех ребер в $C$ не меньше $-\varepsilon$. Тогда стоимость всего цикла $p_{\varphi}(C)\geqslant -V\cdot \varepsilon$ (в цикле не больше $V$ ребер). Таким образом, $p_{\varphi}(C) \gt -1$, то есть $p(C) \gt -1$. Но исходные пропускные способности были целочисленными, поэтому $p(C) \geqslant 0$, а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, $f$ — поток минимальной стоимости.

$\triangleleft$

Обозначим за $\mu^{*}$ минимальную величину среди средних весов циклов для потока $f$, а за $\varepsilon^{*}$ минимальное $\varepsilon$ такое, что поток $f$ — $\varepsilon$-оптимальный.

Лемма ($3$):

Если $f$ — поток не минимальной стоимости, то $\varepsilon^{*}=-\mu^{*}$.

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

$\triangleright$

Пусть $C$ — цикл минимального среднего веса в остаточной сети. Покажем, что $\mu^{*} \geqslant -\varepsilon^{*}$. Поскольку поток $f$ является $\varepsilon^{*}$-оптимальным, верно следующее: $p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon^{*}$ или $\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon^{*}$, то есть $\mu(C)=\mu^{*} \geqslant -\varepsilon^{*}$. Теперь покажем, что $\mu^{*} \leqslant -\varepsilon^{*}$. Пусть $p'(uv)=p(uv)-\mu^{*}$ для любого $uv \in E_{f}$. Логичным будет также обозначить для некоторого цикла $C$ за $\mu'(C)$ величину $\dfrac{p'(C)}{\texttt{len}(C)}$. Таким образом, для любого цикла $C$, $\mu'(C)=\mu(C)-\mu^{*}\geqslant 0$. Далее проведем рассуждения, аналогичные доказательству леммы $1$. Добавим вершину $a$ и проведем из нее ребро стоимости $0$ во все вершины графа $G_{f}$. В качестве $\varphi(u)$ выберем стоимость (считая стоимостью функцию $p'$) минимального пути из $a$ в $u$. Таким образом, $\varphi(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv) - \mu^{*}$. Отсюда получаем, что $p_{\varphi}(uv) \geqslant \mu^{*}$ для любого ребра $uv$ из остаточной сети $E_{f}$, что означает, что $f$ — $(-\mu^{*})$-оптимальный, и, по определению $\varepsilon^{*}$, $\varepsilon^{*} \leqslant -\mu^{*}$.

$\triangleleft$

Лемма ($4$):

Отмена цикла минимального среднего веса не увеличивает $\varepsilon^{*}$.

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

$\triangleright$

Пусть $C$ — цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл $C$ ребро $uv$ удовлетворяет свойству $\varepsilon^{*}$-оптимальности: $p_{\varphi}(uv) \geqslant -\varepsilon^{*}$. По лемме $3$, $\varepsilon^{*}=-\mu^{*}$, то есть $p_{\varphi}(uv) \geqslant \mu^{*}$. Но поскольку $\mu^{*}$ — средний вес цикла, то $p_{\varphi}(uv) = \mu^{*} = -\varepsilon^{*}$. По свойству антисимметричности потока, после отмены цикла $C$, в остаточной сети появятся ребра стоимости $\varepsilon$. Таким образом, свойство $p_{\varphi}(uv) \geqslant -\varepsilon$ все еще выполняется.

$\triangleleft$

Определение:

Допустимым графом (англ. admissible graph) будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. $H=\{uv \in E_{f}\;|\; p_{\varphi}(uv) \lt 0\}$

Лемма ($5$):

Пусть $f$ — некоторый поток, а $f'$ — поток после $E$ отмен циклов минимального среднего веса. Тогда $\varepsilon'^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}$, где $\varepsilon'^{*}$ — минимальное $\varepsilon$ такое, что поток $f'$ $\varepsilon$-оптимальный.

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

$\triangleright$

Изначально любое ребро $uv$ удовлетворяет свойству $p_{\varphi}(uv) \geqslant -\varepsilon^{*}$. Отмена цикла добавляет в остаточную сеть $G_{f}$ только ребра положительной приведенной стоимости (см. лемму $4$) и удаляет из сети $G$ как минимум одно ребро. Рассмотрим два случая: Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа $H$ и после $E$ отмен граф $H$ пуст, что означает, что $f'$ — оптимальный поток, то есть $\varepsilon'^{*}=0$. Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на $i$-ой итерации, и, соответственно, $C_{i}$ — первый из таких циклов. Для $C_{i}$ имеем, что каждое его ребро обладает приведенной стоимостью как минимум $-\varepsilon_{i}^{*}$ (при этом $\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}$ по лемме $4$), хотя бы одно из ребер $C_{i}$ обладает неотрицательной приведенной стоимостью и количество ребер в $C_{i}$ не превышает $V$. Тогда средний вес этого цикла $\mu(C_{i}) = \mu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant - \left(1-\dfrac{1}{V}\right)\varepsilon^{*}$, и $\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} = -\mu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}$.

$\triangleleft$

Определение:

$\varepsilon$-фиксированным (англ. $\varepsilon$-fixed) будем называть ребро, поток через которое неизменен для любых $\varepsilon$-оптимальных потоков в сети.

Теорема:

Пусть поток $f$ является $\varepsilon$-оптимальным с функцией потенциалов $\varphi$. Также пусть для некоторого ребра $uv \; \left|p_{\varphi}(uv)\right| \geqslant 2V\varepsilon$. Тогда ребро $uv$ $\varepsilon$-фиксировано.

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

$\triangleright$

По свойству антисимметричности, достаточно будет доказать теорему для случая $p_{\varphi}(uv) \geqslant 2V\varepsilon$. Рассмотрим такой поток $f'$, что $f'(uv) \neq f(uv)$. Поскольку $p_{\varphi}(uv) \geqslant 2V\varepsilon \gt \varepsilon$, поток по ребру $uv$ должен быть как можно меньше, то есть $f(uv) = -c(uv)$, и тогда раз $f'(uv) \neq f(uv)$, то $f'(uv) \gt f(uv)$. Покажем теперь, что $f'$ не $\varepsilon$-оптимальный. Обозначим за $G_{\gt }$ подграф $G$ такой, что $G_{\gt }=(V, \{uv \in E \;|\; f'(uv) \gt f(uv) \})$. Рассмотрим некоторое ребро $uv$ в $G_{\gt }$. Поскольку $f$ и $f'$ являются циркуляциями, в $G_{\gt }$ должен содержаться простой цикл $C$, проходящий через $uv$. Поскольку все ребра в $C$ — остаточные, стоимость $C$ не меньше $p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon \gt V\varepsilon$. Теперь рассмотрим цикл $\overline{C}$, который получен из $C$ разворотом всех его ребер. Заметим, что $\overline{C}$ является циклом в $G_{\lt }=(V,\{uv \in E \;|\; f'(uv) \lt f(uv)\})$ и, соответственно, циклом в $G_{f}$. По свойству антисимметричности, стоимость $\overline{C}$ меньше, чем $-V\varepsilon$ и, таким образом, $\mu(\overline{C}) \lt -\varepsilon$. Откуда по лемме $3$ имеем, что $f'$ не $\varepsilon$-оптимален.

$\triangleleft$

Лемма (доказательство оценки времени работы алгоритма в случае вещественных стоимостей):

Пусть $k=VE(\lceil \log V + 1 \rceil)$. Разобьем работу алгоритма на группы по $k$ последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре $uv$, то есть итерации из другой группы не меняют величину $f(uv)$.

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

$\triangleright$

Оценка времени работы следует непосредственно из этого утверждения. Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть $f$ — поток до первой итерации, а $f'$ — после последней итерации этой группы. Обозначим за $\varepsilon'^{*}$ минимальное $\varepsilon$ такое, что поток $f'$ $\varepsilon$-оптимальный, а за $\varphi'$ — функцию потенциалов такую, что $f'$ удовлетворяет свойству $\varepsilon'^{*}$-оптимальности. Выбор $k$ и лемма $5$ дают нам следующее неравенство: $\varepsilon'^{*} \leqslant \varepsilon^{*} \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon^{*}}{2V}$. Рассмотрим цикл $C$, отмененный на первой итерации рассматриваемой группы. Поскольку средний вес цикла $C$ равен $-\varepsilon^{*}$ (см. лемму $3$), некоторое ребро $uv$ цикла $C$ должно иметь приведенную стоимость $p_{\varphi'}(uv) \leqslant -\varepsilon^{*} \leqslant -2V\varepsilon'^{*}$. Таким образом, поток на ребре $uv$ не изменится при итерациях, происходящих после этой группы. Таким образом, по теореме каждая группа фиксирует поток на независимом ребре.

$\triangleleft$

Алгоритм поиска цикла минимального среднего веса

Наивный способ

Устроим двоичный поиск. Установим нижнюю и верхнюю границы величины среднего веса цикла $l$ и $r$ соответственно, вычислим серединное значение $m$ и отнимем полученную величину $m$ от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи алгоритма Форда-Беллмана), значит существует цикл с меньшим средним весом, чем $m$. Тогда продолжим поиск среди значений в диапазоне от $l$ до $m$, иначе — от $m$ до $r$.

Тогда, если $C_{max}$ и $C_{min}$ — максимальная и минимальная возможные величины среднего веса цикла соответственно, такой алгоритм для вещественных значений весов ребер будет работать за $O\left(\log \dfrac{C_{max}-C_{min}}{\varepsilon} \cdot EV\right)$, где $\varepsilon$ — точность выбора среднего веса цикла. При этом для целочисленных значений на ребрах точность выбора величины среднего веса цикла не может превысить $\dfrac{1}{V}$, что дает нам оценку $O\left(\log (V(C_{max}-C_{min})) \cdot EV\right)$.

Псевдокод

   func findMinCycleBinarySearch (l, r)
     m = (l + r) / $2$
     for e in edges
       e.weight -= m
     if $\exists$ C : M(C) < 0 
       findMinCycleBinarySearch (l, m)
     else
       findMinCycleBinarySearch (m, r)

Продвинутый алгоритм

Добавим к нашему графу вершину $s$ и ребра из нее во все остальные вершины. Запустим алгоритм Форда-Беллмана и попросим его построить нам квадратную матрицу со следующим условием: $d[i][u]$ — длина минимального пути от $s$ до $u$ ровно из $i$ ребер. Тогда длина оптимального цикла $\mu^{*}$ минимального среднего веса вычисляется как $\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}$.

Достаточно будет доказать это правило для $\mu^{*}=0$, так как для других $\mu^{*}$ можно просто отнять эту величину от всех ребер и получить снова случай с $\mu^{*}=0$.

Чтобы найти цикл после построения матрицы $d[k][u]$, запомним, при каких $u$ и $k$ достигается оптимальное значение $\mu^{*}$, и, используя $d[n][u]$, поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину — мы нашли цикл минимального среднего веса.

Этот алгоритм работает за $O(VE)$ .

Псевдокод

 func findMinCycle()
   Node s
   Edge e
   insert(s)                                         // добавляем мнимую вершину $s$ и проводим рёбра нулевого веса в каждую вершину графа
   for u in G
     e.begin = s
     e.end = u
     e.weight = 0
   fordBellman(s)
   m = $\min\limits_{u} {\max\limits_{k} }$((d[n][u] - d[k][u]) / (n - k))

См. также

• Использование потенциалов Джонсона при поиске потока минимальной стоимости
• Сведение задачи о назначениях к задаче о потоке минимальной стоимости

Источники информации

• Лекция 14 | Дополнительные главы алгоритмов | Андрей Станкевич | CSC | Лекториум
• A.V.Goldberg and R.E.Tarjan — Finding Minimum-Cost Circulations by Cancelling Negative Cycles (Journal of the Association for Computing Machinery. Vol. 36, No. 4. October 1989. pp. 873-886.)
• Lecture by M.X.Goemans on Goldberg-Tarjan Min-Cost Circulation Algorithm