Материал из Викиконспекты
Алгоритм
Приведенный алгоритм основан на идее алгоритма Клейна отмены цикла отрицательного веса. Выбор цикла минимального среднего веса вместо случайного делает алгоритм сильно полиномиальным.
| Определение: |
| Сильно полиномиальными (англ. strongly polynomial) в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от [math]V[/math] и [math]E[/math]. |
Описание
Обозначим как [math]c_{f}(C)[/math] остаточную пропускную способность цикла [math]C[/math] при протекании в сети потока [math]f[/math].
Cтоимость цикла [math]C[/math] обозначим за [math]p(C)[/math], а длину (число входящих в него ребер) — за [math]\texttt{len}(C)[/math].
| Определение: |
| Средним весом (англ. mean weight) цикла будем называть отношение его стоимости к его длине [math]\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}[/math] |
- Шаг 1. Рассмотрим некоторый поток [math]f[/math].
- Шаг 2. Найдем цикл [math]C[/math], обладающий наименьшим средним весом. Если [math]\mu (C) \geqslant 0[/math], то [math]f[/math] — поток минимальной стоимости и алгоритм завершается.
- Шаг 3. Отменим цикл [math]C[/math], пустив по нему максимально возможный поток: [math]f = f + c_{f}(C)\cdot f_{C}[/math]. Перейдем к шагу 1.
Сложность
[math]O(VE\cdot VE^{2}\log{V})[/math], при этом
[math]O(VE)[/math] времени тратится на поиск цикла минимального среднего веса.
Корректность
Пусть [math]f[/math] — поток минимальной стоимости. Введем на нашей сети функцию потенциалов [math]\varphi[/math].
| Определение: |
| Приведенной стоимостью (англ. reduced cost) ребра назовем следующую величину: [math]p_{\varphi}(uv)=\varphi(u) + p(uv) - \varphi(v)[/math]. |
Иными словами, приведенная стоимость — это сколько нужно потратить денег, чтобы перевести единицу жидкости из [math]u[/math] в [math]v[/math]. (Ее нужно купить в [math]u[/math], перевезти из [math]u[/math] в [math]v[/math] и продать в [math]v[/math].)
| Лемма: |
Если [math]f[/math] — поток минимальной стоимости, то [math]\exists \varphi[/math] такое, что [math]\forall uv: \; c_{f}(uv) \gt 0 \qquad p_{\varphi}(uv) \geqslant 0[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- Рассмотрим остаточную сеть — граф [math]G_{f}[/math]. В нем нет отрицательных циклов, так как [math]f[/math] — поток минимальной стоимости[1].
- Добавим вершину [math]a[/math] и проведем из нее ребро стоимости [math]0[/math] во все вершины графа [math]G_{f}[/math]. В качестве [math]\varphi(u)[/math] выберем стоимость минимального пути из [math]a[/math] в [math]u[/math].
- Рассмотрим теперь некоторое ребро [math]uv[/math]. Понятно, что [math]\varphi(v) \leqslant \varphi(u) + p(uv)[/math]. (Здесь сравниваются минимальный путь [math]a \rightsquigarrow v[/math] и путь [math]a \rightsquigarrow u \rightarrow v[/math]). Перенеся [math]\varphi(v)[/math] в другую часть неравенства, получаем [math]0 \leqslant \varphi(u) + p(uv) - \varphi(v)[/math] или [math]0 \leqslant p_{\varphi}(uv)[/math], что и требовалось доказать.
|
| [math]\triangleleft[/math] |
| Определение: |
| Будем говорить, что поток [math]f[/math] — [math]\varepsilon[/math]-оптимальный (англ. [math]\varepsilon[/math]-optimal), если [math]\exists \varphi[/math] такая, что [math]\forall uv: c_{f}(uv) \gt 0 \qquad p_{\varphi}(uv) \geqslant -\varepsilon[/math]. |
| Лемма: |
Если стоимости целочисленны и поток [math]f[/math] — [math]\varepsilon[/math]-оптимальный, где [math]\varepsilon \lt \dfrac{1}{n}[/math], то [math]f[/math] — поток минимальной стоимости. |
| Доказательство: |
| [math]\triangleright[/math] |
- Рассмотрим цикл в остаточной сети [math]C[/math]. Заметим, что [math]p(C)=p_{\varphi}(C)[/math].
- Возьмем [math]\varphi[/math] такое, что стоимости всех ребер в [math]C[/math] не меньше [math]-\varepsilon[/math]. Тогда стоимость всего цикла [math]p_{\varphi}(C)\geqslant -n\cdot \varepsilon[/math] (в цикле не больше [math]n[/math] ребер). Таким образом, [math]p_{\varphi}(C) \gt -1[/math], то есть [math]p(C) \gt -1[/math]. Но исходные пропускные способности были целочисленными, поэтому [math]p(C) \geqslant 0[/math], а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, [math]f[/math] — поток минимальной стоимости.
|
| [math]\triangleleft[/math] |
Обозначим за [math]\mu(f)[/math] минимальную величину среди средних весов циклов для потока [math]f[/math], а за [math]\varepsilon(f)[/math] минимальное [math]\varepsilon[/math] такое, что поток [math]f[/math] — [math]\varepsilon[/math]-оптимальный.
| Лемма: |
Если [math]f[/math] — поток не минимальной стоимости, то [math]\varepsilon(f)=-\mu(f)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- Покажем, что [math]\mu(f) \geqslant -\varepsilon(f)[/math].
- Рассмотрим в остаточной сети некоторый цикл [math]C[/math].
- Поскольку поток [math]f[/math] является [math]\varepsilon(f)[/math]-оптимальным, верно следующее: [math]p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon(f)[/math] или [math]\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon(f) [/math], то есть [math]\mu(C) \geqslant -\varepsilon(f)[/math], а поскольку это верно для любого цикла, то и [math]\mu(f) \geqslant -\varepsilon(f)[/math].
- Теперь покажем, что [math]\mu(f) \leqslant -\varepsilon(f)[/math].
- Пусть [math]C[/math] — цикл минимального среднего веса в остаточной сети. Поскольку поток [math]f[/math] не минимален, в остаточной сети существует отрицательный цикл, и тогда [math]\mu(C)=\mu(f) \lt 0[/math].
- Предположим, что существуют [math]\varphi[/math] и [math]\varepsilon[/math] такие, что [math]\varepsilon \gt -\mu(f)[/math] или [math]-\varepsilon \lt \mu(f)[/math].
- Рассмотрим такое ребро [math]uv[/math], входящее в цикл, что величина [math]p_{\varphi}(uv)[/math] минимальна. Тогда верно следующее: [math]p_{\varphi}(uv) \leqslant \mu(f)[/math], то есть [math]p_{\varphi}(uv) \lt -\varepsilon[/math], что означает, что [math]f[/math] не является [math]\varepsilon[/math]-оптимальным. Получено противоречие, и, значит, [math]\varepsilon(f) \leqslant -\mu(f)[/math].
|
| [math]\triangleleft[/math] |
| Лемма: |
Отмена цикла минимального среднего веса не увеличивает [math]\varepsilon(f)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
- Пусть [math]C[/math] — цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл [math]C[/math] ребро [math]uv[/math] удовлетворяет свойству [math]\varepsilon(f)[/math]-оптимальности: [math]p_{\varphi}(uv) \geqslant -\varepsilon(f)[/math].
- По предыдущей лемме, [math]\varepsilon(f)=-\mu(f)[/math], то есть [math]p_{\varphi}(uv) \geqslant \mu(f)[/math]. Но поскольку [math]\mu(f)[/math] — средний вес цикла, то [math]p_{\varphi}(uv) = \mu(f) = -\varepsilon(f)[/math].
- По свойству антисимметричности потока, после отмены цикла [math]C[/math], в остаточной сети появятся ребра стоимости [math]\varepsilon[/math]. Таким образом, свойство [math]p_{\varphi}(uv) \geqslant -\varepsilon[/math] все еще выполняется.
|
| [math]\triangleleft[/math] |
| Лемма (доказательство оценки времени работы алгоритма): |
Пусть [math]k=VE(\lceil \log V + 1 \rceil)[/math]. Разобьем работу алгоритма на группы по [math]k[/math] последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре [math]uv[/math], то есть итерации из другой группы не меняют величину [math]f(uv)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Оценка следует непосредственно из этого утверждения. Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть [math]f[/math] — поток до первой итерации рассматриваемой группы, а [math]f'[/math] — поток после последней итерации. Также пусть для простоты обозначений [math]\varepsilon = \varepsilon(f)[/math], [math]\varepsilon'=\varepsilon(f')[/math], при этом [math]\varphi'[/math] — функция потенциалов такая, что [math]f'[/math] удовлетворяет свойству [math]\varepsilon'[/math]-оптимальности. Рассмотрим цикл [math]C[/math], отмененный после первой итерации группы. Выбор [math]k[/math] дает нам [math]\varepsilon' \leqslant \varepsilon \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon}{2V}[/math]. Поскольку средний вес цикла [math]C[/math] равен [math]-\varepsilon[/math], некоторое ребро [math]uv[/math] цикла [math]C[/math] должно иметь приведенную стоимость [math]p_{\varphi'}(uv) \leqslant -\varepsilon \leqslant -2n\varepsilon'[/math]. Таким образом, поток на ребре [math]uv[/math] не изменится при итерациях, происходящих после этой группы. Таким образом, каждая группа фиксирует поток на независимом ребре. |
| [math]\triangleleft[/math] |
Алгоритм поиска цикла минимального среднего веса
Наивный способ
Устроим двоичный поиск.
Установим нижнюю и верхнюю границы величины среднего веса цикла [math]l[/math] и [math]r[/math] соответственно, вычислим серединное значение [math]m[/math] и отнимем полученную величину [math]m[/math] от всех ребер сети. Если теперь в нашей сети есть отрицательный цикл (этот факт можно проверить при помощи алгоритма Форда-Беллмана), значит существует цикл с меньшим средним весом, чем [math]m[/math]. Тогда продолжим поиск среди значений в диапазоне от [math]l[/math] до [math]m[/math], иначе — от [math]m[/math] до [math]r[/math].
Такой алгоритм будет работать за [math]O(\texttt{log} \dfrac{1}{\varepsilon} \cdot EV)[/math], где [math]\varepsilon[/math] — точность выбора величины среднего веса цикла.
Продвинутый алгоритм
Добавим к нашему графу вершину [math]s[/math] и ребра из нее во все остальные вершины.
Запустим алгоритм Форда-Беллмана и попросим его построить нам квадратную матрицу со следующим условием: [math]d[i][u][/math] — длина минимального пути от [math]s[/math] до [math]u[/math] ровно из [math]i[/math] ребер.
Тогда длина оптимального цикла [math]\mu^{*}[/math] минимального среднего веса вычисляется как [math]\min\limits_{u} {\max\limits_{k} {\dfrac{d[n][u]-d[k][u]}{n-k}}}[/math].
Достаточно будет доказать это правило для [math]\mu^{*}=0[/math], так как для других [math]\mu^{*}[/math] можно просто отнять эту величину от всех ребер и получить снова случай с [math]\mu^{*}=0[/math].
Чтобы найти цикл после построения матрицы [math]d[k][u][/math], запомним, при каких [math]u[/math] и [math]k[/math] достигается оптимальное значение [math]\mu^{*}[/math], и, используя [math]d[n][u][/math], поднимемся по указателям предков. Как только мы попадем в уже посещенную вершину — мы нашли цикл минимального среднего веса.
Этот алогоритм работает за [math]O(VE)[/math].
См. такжеПримечанияИсточники информации
