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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритмы решения)
(Метод устранения отрицательных циклов в остаточной сети)
Строка 19: Строка 19:
 
== Алгоритмы решения ==
 
== Алгоритмы решения ==
 
===Метод устранения отрицательных циклов в остаточной сети===
 
===Метод устранения отрицательных циклов в остаточной сети===
* Воспользуемся [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети|леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]].
+
Воспользуемся [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети|леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]. Получим следующий алгоритм:
** Найдем любой поток величины <tex>f_0</tex>.
+
 
** При помощи [[Алгоритм Форда-Беллмана|Форда-Беллмана]] найдем отрицательные циклы в остаточной сети.
+
* '''Начало'''
** Избавимся от всех найденных циклов, для этого, пустим по ним максимально возможный поток.
+
* '''Шаг 1'''. Требуется найти максимальный поток минимальной стоимости.
 +
* '''Шаг 2'''. Для каждого ребра зададим поток равный 0.
 +
* '''Шаг 3'''. Построим остаточную сеть <tex>G_f</tex>
 +
* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана| алгоритма Форда-Беллмана]] найдем отрицательный цикл в остаточной сети. Если нет - перейдем к '''шагу 7'''
 +
* '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток.
 +
* '''Шаг 6'''. Перейдем к '''шагу 3'''.
 +
* '''Шаг 7'''. Отрицательных циклов восточной сети нет, значит, максимальный поток минимальной стоимости найден.
 +
* '''Конец'''
 +
 
 
===Метод дополнения потока вдоль путей минимальной стоимости===
 
===Метод дополнения потока вдоль путей минимальной стоимости===
 
[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].
 
[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]].

Версия 14:17, 24 января 2016

Задача о потоке минимальной стоимости

Определение:
Пусть дана сеть [math]G(V,E)[/math]. [math]S, T \in V[/math] — источник и сток. [math]\forall (u,v) \in E[/math] [math]\exists c(u, v), f(u,v)[/math] — стоимость пересылки единицы потока и пропускная способность. Тогда общая стоимость потока из [math]S[/math] в [math]T[/math]:
[math]p(u,v) = \sum\limits_{u,v \in V, f(u,v)\gt 0} c(u,v) \cdot f(u,v)[/math]

Свойства стоимости

  • Поток не может превысить пропускную способность.
[math]f(u,v) \leqslant c(u,v)[/math]
  • Поток из [math]u[/math] в [math]v[/math] должен быть противоположным потоку из [math]v[/math] в [math]u[/math].
[math]f(u, v)=-f(v, u)[/math]
  • Сохранение потока. Для каждой вершины, сумма входящего и исходящего потоков равно 0.
[math] \sum\limits_{w \in V} f(u,w) = 0[/math]


Задача:
Дана сеть [math]G(V,E)[/math]. [math]S, T \in V[/math] — источник и сток. [math]\forall (u,v) \in E[/math] [math]\exists c(u, v), f(u,v)[/math] — стоимость пересылки единицы потока и пропускная способность. Требуется найти максимальный поток, суммарная стоимость которого минимальна.


Алгоритмы решения

Метод устранения отрицательных циклов в остаточной сети

Воспользуемся леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети. Получим следующий алгоритм:

  • Начало
  • Шаг 1. Требуется найти максимальный поток минимальной стоимости.
  • Шаг 2. Для каждого ребра зададим поток равный 0.
  • Шаг 3. Построим остаточную сеть [math]G_f[/math]
  • Шаг 4. При помощи алгоритма Форда-Беллмана найдем отрицательный цикл в остаточной сети. Если нет - перейдем к шагу 7
  • Шаг 5. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток.
  • Шаг 6. Перейдем к шагу 3.
  • Шаг 7. Отрицательных циклов восточной сети нет, значит, максимальный поток минимальной стоимости найден.
  • Конец

Метод дополнения потока вдоль путей минимальной стоимости

Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости.

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

Использование потенциалов Джонсона при поиске потока минимальной стоимости (модификация предыдущего алгоритма).

См. также

Источники информации