Использование потенциалов Джонсона при поиске потока минимальной стоимости

2014-12-13T14:56:15Z

188.162.64.36:

Метод интересен прежде всего тем, что [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задачу о назначениях]] можно свести к задаче о поиске потока минимальной стоимости, и тогда эффективность решения задачи о назначениях будет определяться именно асимптотикой работы этого алгоритма.

== Мотивация ==

Зачем нужно использовать потенциалы Джонсона?

Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].

При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Это реализуется с помощью алгоритмов поиска кратчайшего пути в графе. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]]. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]] для этой же цели, так как у него гораздо лучше асимптотика. Для этого нам надо перевзвесить рёбра графа.

{{Определение
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>\,p_i</tex>. Тогда остаточная стоимость ребра <tex>\,c_{p_{ij}}</tex> определяется как
<tex>\,c_{p_{ij}} = c_{ij} + p_i - p_j </tex>
}}
Заметим, что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.

== Использование потенциалов Джонсона ==
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,c_{ij} + p_i</tex> — это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,p_j</tex> — длина минимального пути, то <tex>c_{p_{ij}} \geqslant 0</tex>, что от нас и требовалось.
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.

==Реализация==
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
<font size=30> НЕ ЧИТАЙТЕ, В РЕАЛИЗАЦИИ НАПИСАНА ПОЛНАЯ ЧУШЬ, после второй итерации, скорее всего, появятся ребра отрицательного веса </font>

'''for''' <tex>e \in E</tex> {
<tex>f[e] \leftarrow 0</tex>
}
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — расстояние <tex>s \leadsto e</tex>,
если за длину ребра принимается его стоимость.
'''for''' <tex>e \in E</tex> {
<tex>c[e] \leftarrow c[e] + p[e.from] - p[e.to]</tex>
}
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
Найти <tex>P </tex> — кратчайший в смысле стоимости путь <tex>s \leadsto t</tex> с помощью алгоритма Дейкстры
дополнить поток <tex>f</tex> вдоль <tex>P</tex>
}

==Асимптотика==
Пусть все пропускные способности целочисленны.
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Метод целиком]] работает за <tex>O(F(V, E) \cdot |f|)</tex>, где <tex>F(V, E)</tex> — время одной итерации.

Время, затраченное на одну итерацию, определяется скоростью поиска кратчайшего пути.
Если для этой цели использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то поиск мы осуществим за <tex>O(V \log V + E)</tex>.

Не стоит так же забывать, что для расчёта потенциалов мы один раз запустили Алгоритм Форда-Беллмана.
В результате получим время работы <tex>O((V \log V + E) \cdot |f| + V E)</tex>.

Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации.

В применении к [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задаче о назначениях]]: пусть у нас есть <tex>N</tex> назначений. Построим специальным образом граф. Искомый поток в нём имеет имеет мощность <tex>N</tex>. Количество вершин — <tex>O(N)</tex>, рёбер — <tex>O(N^2)</tex>. Итого получаем асимптотику <tex>O(N^2 \log N + 2N^3) = O(N^3)</tex>.

== Литература ==
* ''Andrew V. Goldberg'' An Efficient implementation of a scaling minimum-cost flow algorithm - Journal of Algorithms, 1997

[[Категория:Алгоритмы и структуры данных]]
[[Категория: Задача о потоке минимальной стоимости]]

Викиконспекты - Вклад участника [ru]

Использование потенциалов Джонсона при поиске потока минимальной стоимости