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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
Метод интересен прежде всего тем, что [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задачу о назначениях]] можно свести к задаче о поиске потока минимальной стоимости, и тогда эффективность решения задачи о назначениях будет определяться именно асимптотикой работы этого алгоритма.
 +
 
== Мотивация ==
 
== Мотивация ==
 +
 +
Зачем нужно использовать потенциалы Джонсона?
  
 
Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].
 
Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].
  
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]. Для этого нам надо перевзвесить рёбра графа.
+
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Это реализуется с помощью алгоритмов поиска кратчайшего пути в графе. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]]. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]] для этой же цели, так как у него гораздо лучше асимптотика. Для этого нам надо перевзвесить рёбра графа.
  
 
{{Определение
 
{{Определение
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>. Введем в каждой вершине потенциал <tex>\,p_i</tex>. Тогда остаточная стоимость ребра <tex>\,c_{p_{ij}}</tex> определяется как
+
|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>\,c_{p_{ij}} = c_{ij} + p_i - p_j </tex>
 
}}
 
}}
Строка 33: Строка 37:
 
==Асимптотика==
 
==Асимптотика==
 
Пусть все пропускные способности целочисленны.
 
Пусть все пропускные способности целочисленны.
Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.
+
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Метод целиком]] работает за <tex>O(F(V, E) \cdot |f|)</tex>, где <tex>F(V, E)</tex> — время одной итерации.
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] работает за <tex>O(F(V, E) \cdot |f|)</tex>.
+
 
Если использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то <tex>F(V, E)= V log V + E</tex>. В результате получим время работы <tex>O((V log V + E) \cdot |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>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] для поиска кратчайшего пути на каждой итерации.
  
 
== Литература ==
 
== Литература ==

Версия 12:01, 28 февраля 2012

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

Мотивация

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

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

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


Определение:
Пусть дана транспортная сеть [math]\,G(V,E)[/math], где [math]V[/math] — множество вершин графа, а [math]E[/math] — множество рёбер. Введем в каждой вершине потенциал [math]\,p_i[/math]. Тогда остаточная стоимость ребра [math]\,c_{p_{ij}}[/math] определяется как [math]\,c_{p_{ij}} = c_{ij} + p_i - p_j [/math]

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

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

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

Реализация

Модифицируем псевдокод из статьи про поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости:

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

Асимптотика

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

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

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

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

Литература

  • Andrew V. Goldberg An Efficient implementation of a scaling minimum-cost flow algorithm - Journal of Algorithms, 1997