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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Исправление конспекта)
(Исправления 2)
Строка 1: Строка 1:
 
== Мотивация ==
 
== Мотивация ==
 +
 +
Идея аналогична идее, использующейся в [[Алгоритм Джонсона|алгоритме Джонсона]].
  
 
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]. Для этого нам надо перевзвесить рёбра графа.
 
При [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] нам требуется находить минимальный по стоимости поток из истока в сток. Поскольку стоимость некоторых рёбер может быть отрицательной, нам приходится использовать [[Алгоритм Форда-Беллмана|алгоритм Форда-Беллмана]] для поиска кратчайшего пути. Однако гораздо эффективней было бы применить [[Алгоритм Дейкстры|алгоритм Дейкстры]]. Для этого нам надо перевзвесить рёбра графа.
Строка 7: Строка 9:
 
<tex>\,C_{P_{ij}} = C_{ij} + P_i - P_j </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>, что от нас и требовалось.
+
Возьмём значения потенциалов в вершинах равными минимальному по цене расстоянию от стока до них или <tex>+\infty</tex>, если она недостижима. Так как <tex>\,C_{ij} + P_i</tex> - это длина какого-то пути до вершины <tex>\,j</tex>, а <tex>\,P_j</tex> - длина минимального пути, то <tex>C_{P_{ij}} \geqslant 0</tex>, что от нас и требовалось.
 
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.
 
Значения потенциалов найдём с помощью [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]]. Таким образом, нам его придётся запустить всего один раз, а не на каждом шаге алгоритма.
 +
 +
==Реализация==
 +
Модифицируем псевдокод из статьи про [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]:
 +
 +
'''for''' <tex>e \in E</tex> {
 +
      <tex>f[e] \leftarrow 0</tex>
 +
}
 +
Запустим алгоритм Форда-Беллмана, в результате для каждой вершины: <tex>p[e] </tex> - расстояние <tex>s \leadsto e</tex>,
 +
если за длину ребра принимается его стоимость.
 +
'''for''' <tex>v \in V</tex> {
 +
      <tex>c[v] \leftarrow c[v] + p[v.from] - p[v.to]</tex>
 +
}
 +
'''while''' (существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>) {
 +
      <tex>P \leftarrow</tex> кратчайший в смысле стоимости путь <tex>s \leadsto t</tex>
 +
      дополнить поток <tex>f</tex> вдоль <tex>P</tex>
 +
}
 +
  
 
==Асимптотика==
 
==Асимптотика==
 +
Пусть все пропускные способности целочислены.
 
Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.
 
Обозначим время работы поиска кратчайшего пути <tex>F(V, E)</tex>.
[[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости|Поиске потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]] работает за <tex>O(F(V, E) \cdot |f|)</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|)</tex>.
+
Если использовать [[Алгоритм Дейкстры|алгоритм Дейкстры]] с Фиббоначевыми кучами, то <tex>F(V, E)= V log V + E</tex>. В результате получим время работы <tex>O((V log V + E) \cdot |f|)</tex>.
 +
 
 +
Это лучше, чем <tex>O((V E) \cdot |f|)</tex>, что получается при использовании [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]].
  
== См. также ==
+
== Литература ==
* [[Алгоритм Дейкстры]]
+
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
* [[Алгоритм Форда-Беллмана]]
 
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
 
* [[Алгоритм Джонсона]]
 
  
 
[[Категория: Задача о потоке минимальной стоимости]]
 
[[Категория: Задача о потоке минимальной стоимости]]

Версия 03:34, 9 января 2012

Мотивация

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

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


Определение:
Пусть дана транспортная сеть [math]\,G(V,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[e] [/math] - расстояние [math]s \leadsto e[/math], 
если за длину ребра принимается его стоимость.
for [math]v \in V[/math] {
     [math]c[v] \leftarrow c[v] + p[v.from] - p[v.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]F(V, E)[/math]. Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости работает за [math]O(F(V, E) \cdot |f|)[/math]. Если использовать алгоритм Дейкстры с Фиббоначевыми кучами, то [math]F(V, E)= V log V + E[/math]. В результате получим время работы [math]O((V log V + E) \cdot |f|)[/math].

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

Литература

  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.