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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация)
(не показано 25 промежуточных версий 7 участников)
Строка 1: Строка 1:
== Потенциал Джонсона ==
+
Метод интересен прежде всего тем, что [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|задачу о назначениях]] можно свести к задаче о поиске потока минимальной стоимости, и тогда эффективность решения задачи о назначениях будет определяться именно асимптотикой работы этого алгоритма.
 +
 
 +
== Мотивация ==
 +
 
 +
Зачем нужно использовать потенциалы Джонсона?
 +
 
 +
Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].
 +
 
 +
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Это реализуется с помощью алгоритмов поиска кратчайшего пути в графе. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]]. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]] для этой же цели, так как у него гораздо лучше асимптотика. Для этого нам надо перевзвесить рёбра графа.
 +
 
 
{{Определение
 
{{Определение
|definition=Пусть дана транспортная сеть <math>\,G(V,E)</math>. Введем в каждой вершине потенциал <math>\,P_i</math>. Тогда остаточная стоимость ребра <math>\,C_{P_{ij}}</math> определяется как
+
|definition=Пусть дана транспортная сеть <tex>\,G(V,E)</tex>, где <tex>V</tex> — множество вершин графа, а <tex>E</tex> — множество рёбер. Введем в каждой вершине потенциал <tex>p(v)</tex>. Тогда потенциальный вес (то есть стоимость) ребра <tex>(u, v)</tex> определяется как
<math>\,C_{P_{ij}} = C_{ij} + P_i - P_j </math>
+
<tex>w_p(u, v) = w(u, v) + p(u) - p(v) </tex>
 
}}
 
}}
Заметим что сумма остаточных стоимостей ребер вдоль любого пути отличается от суммы стоимостей вдоль того же самого пути на разность между потенциалом первой и последней вершины.
+
Заметим, что сумма потенциальных весов ребер вдоль любого пути отличается от суммы весов вдоль того же самого пути на разность между потенциалом первой и последней вершины.
  
 
== Использование потенциалов Джонсона ==
 
== Использование потенциалов Джонсона ==
Если <math>\forall i, j \,C_{P_{ij}} \geqslant 0</math> то при поиске минимального по стоимости пути от истока до стока можно пользоваться алгоритмом Дейкстры, а не алгоритмом Форда-Беллмана, что сильно улучшает ассимптотику алгоритма.  
+
Возьмём значения потенциалов в вершинах равными минимальному расстоянию от истока до них, а расстояния найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть <tex>p(v)</tex> - длина кратчайшего пути от истока в вершину <tex>v</tex> в новой сети. Научимся делать это, не запуская каждый раз Форда-Беллмана.
 +
 
 +
Для начала докажем, что в сети с корректными потенциалами <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex>.
 +
 
 +
Пусть <tex>s, v_1, v_2, \ldots, v_k, t</tex> - кратчайший путь из <tex>s</tex> в <tex>t</tex>, и <tex>d(u, v)</tex> - длина кратчайшего пути между вершинами <tex>u</tex> и <tex>v</tex> в исходной сети без потенциалов. Тогда <tex>w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) = d(s, t)</tex> и <tex>w_p(s, v_1) + w_p(v_1, v_2) + \ldots + w_p(v_k, t) = p(s) + w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) - p(t) = p(s) + d(s, t) - p(t) = p(s) + p(t) - p(t) = p(s) = 0</tex>. Таким образом, сумма всех потенциальных весов ребер на кратчайшем пути из <tex>s</tex> в <tex>t</tex> равна нулю. Кроме того, для любого ребра <tex>(u, v)</tex> <tex>w_p(u, v) \geq 0</tex>. Следственно, <tex>w_p(u, v) = 0</tex> для любого ребра <tex>(u, v)</tex>, лежащего на кратчайшем пути из <tex>s</tex> в <tex>t</tex>.
 +
 
 +
Более того, потенциальный вес всех ребер, обратных ребрам из кратчайшего пути, тоже равен <tex>0</tex>. И правда, <tex>w_p(u, v) = w(u, v) + d(s, u) - d(s, v) = 0</tex>. Умножив на <tex>-1</tex>, получаем <tex>0 = -w(u, v) - d(s, u) + d(s, v) = w(v, u) + d(s, v) - d(s, u) = w_p(v, u)</tex>
 +
 
 +
Из доказанных выше фактов следует, что при добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из <tex>s</tex>, чтобы насчитать новые потенциалы. Пусть <tex>d_1(u, v)</tex> - кратчайшее расстояние, найденное алгоритмом Дейкстры, из <tex>u</tex> в <tex>v</tex> в сети с появившимися новыми ребрами, но старыми потенциалами, а <tex>d(u, v)</tex> - кратчайшее расстояние в новой сети без потенциалов. Нетрудно заметить, что <tex>d_1(s, v) = d(s, v) - p(v)</tex>, следственно, <tex>d(s, v) = d_1(s, v) + p(v)</tex>. Зная настоящие расстояния от истока до каждой вершины, мы теперь можем проставить новые потенциалы. Для каждой вершины <tex>v</tex> <tex>p(v) \gets d(s, v) = d_1(s, v) + p(v)</tex>.
 +
 
 +
Кроме того, мы также нашли новый кратчайший путь из истока из сток - а значит, на следующей итерации алгоритма мы можем пустить поток по нему и повторить все заново.
 +
 
 +
==Реализация==
 +
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
 +
 
 +
'''for''' <tex>e \in E</tex> {
 +
      <tex>f[e] \leftarrow 0</tex>
 +
}
 +
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[v] </tex> — кратчайшее расстояние <tex>s \leadsto v</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>s</tex>, чтобы насчитать <tex>d_1</tex>
 +
      '''for''' <tex>v \in V</tex> {
 +
            <tex>p[v] \leftarrow p[v] + d_1[v]</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
 +
 
  
Пусть каждом шаге алгоритма значения потенциалов в вершинах будут равны минимальному по цене расстоянию от стока до них, или <math>+\infty</math> если она недостижима. Так как <math>\,C_{ij} + P_i</math> это длина какого-то пути до вершины <math>\,j</math>, а <math>\,P_j</math> - длина минимального пути, то <math>C_{P_{ij}} \geqslant 0</math>, что от нас и требовалось.
+
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория: Задача о потоке минимальной стоимости]]

Версия 21:37, 14 декабря 2019

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

Мотивация

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

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

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


Определение:
Пусть дана транспортная сеть [math]\,G(V,E)[/math], где [math]V[/math] — множество вершин графа, а [math]E[/math] — множество рёбер. Введем в каждой вершине потенциал [math]p(v)[/math]. Тогда потенциальный вес (то есть стоимость) ребра [math](u, v)[/math] определяется как [math]w_p(u, v) = w(u, v) + p(u) - p(v) [/math]

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

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

Возьмём значения потенциалов в вершинах равными минимальному расстоянию от истока до них, а расстояния найдём с помощью алгоритма Форда-Беллмана. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма. Однако, после добавления потока вдоль кратчайшего увеличивающего пути в сети могут появиться новые ребра, равно как и исчезнуть старые, и будет необходимо пересчитать потенциалы, чтобы они оставались корректными, то есть [math]p(v)[/math] - длина кратчайшего пути от истока в вершину [math]v[/math] в новой сети. Научимся делать это, не запуская каждый раз Форда-Беллмана.

Для начала докажем, что в сети с корректными потенциалами [math]w_p(u, v) = 0[/math] для любого ребра [math](u, v)[/math], лежащего на кратчайшем пути из [math]s[/math] в [math]t[/math].

Пусть [math]s, v_1, v_2, \ldots, v_k, t[/math] - кратчайший путь из [math]s[/math] в [math]t[/math], и [math]d(u, v)[/math] - длина кратчайшего пути между вершинами [math]u[/math] и [math]v[/math] в исходной сети без потенциалов. Тогда [math]w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) = d(s, t)[/math] и [math]w_p(s, v_1) + w_p(v_1, v_2) + \ldots + w_p(v_k, t) = p(s) + w(s, v_1) + w(v_1, v_2) + \ldots + w(v_k, t) - p(t) = p(s) + d(s, t) - p(t) = p(s) + p(t) - p(t) = p(s) = 0[/math]. Таким образом, сумма всех потенциальных весов ребер на кратчайшем пути из [math]s[/math] в [math]t[/math] равна нулю. Кроме того, для любого ребра [math](u, v)[/math] [math]w_p(u, v) \geq 0[/math]. Следственно, [math]w_p(u, v) = 0[/math] для любого ребра [math](u, v)[/math], лежащего на кратчайшем пути из [math]s[/math] в [math]t[/math].

Более того, потенциальный вес всех ребер, обратных ребрам из кратчайшего пути, тоже равен [math]0[/math]. И правда, [math]w_p(u, v) = w(u, v) + d(s, u) - d(s, v) = 0[/math]. Умножив на [math]-1[/math], получаем [math]0 = -w(u, v) - d(s, u) + d(s, v) = w(v, u) + d(s, v) - d(s, u) = w_p(v, u)[/math]

Из доказанных выше фактов следует, что при добавлении потока вдоль кратчайшего пути в сети с корректными потенциалами не появляется ребер с отрицательным весом (однако сами потенциалы уже становятся некорректными). Но так как ребер отрицательного веса нет, то мы можем пустить алгоритм Дейкстры из [math]s[/math], чтобы насчитать новые потенциалы. Пусть [math]d_1(u, v)[/math] - кратчайшее расстояние, найденное алгоритмом Дейкстры, из [math]u[/math] в [math]v[/math] в сети с появившимися новыми ребрами, но старыми потенциалами, а [math]d(u, v)[/math] - кратчайшее расстояние в новой сети без потенциалов. Нетрудно заметить, что [math]d_1(s, v) = d(s, v) - p(v)[/math], следственно, [math]d(s, v) = d_1(s, v) + p(v)[/math]. Зная настоящие расстояния от истока до каждой вершины, мы теперь можем проставить новые потенциалы. Для каждой вершины [math]v[/math] [math]p(v) \gets d(s, v) = d_1(s, v) + p(v)[/math].

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

Реализация

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

for [math]e \in E[/math] {
     [math]f[e] \leftarrow 0[/math]
}
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: [math]p[v] [/math] — кратчайшее расстояние [math]s \leadsto v[/math], 
если за длину ребра принимается его стоимость.
while (существует путь [math]s \leadsto t[/math] в остаточной сети [math]G_f[/math]) {
      Восстановить [math]P [/math] — кратчайший в смысле стоимости путь [math]s \leadsto t[/math], найденный на предыдущем шаге
      дополнить поток [math]f[/math] вдоль [math]P[/math]
      Запустить алгоритм Дейкстры из [math]s[/math], чтобы насчитать [math]d_1[/math]
      for [math]v \in V[/math] {
           [math]p[v] \leftarrow p[v] + d_1[v][/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], что получается при использовании алгоритма Форда-Беллмана для поиска кратчайшего пути на каждой итерации.


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

Литература

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