Изменения

Перейти к: навигация, поиск

Поток минимальной стоимости

2509 байт добавлено, 19:16, 16 сентября 2019
Алгоритм: Оказывается бывают отрицательные стоимости
== Определение задачи ==Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]].==
{{Определение
|definition=Дано число <tex>f_0</tex> и транспортная Пусть дана сеть <tex>\,G(V,E)</tex> с источником . <tex>s S, T \in V</tex> {{---}} источник и стоком сток. Ребра <tex>t (u,v) \in VE</tex> имееют пропускную способность <tex> c(u, v), </tex> поток <tex> f(u,v) </tex>и цену за единицу потока <tex>a(u, где ребра v) </tex>. Тогда '''общая стоимость потока''' из <tex>S</tex> в <tex>T</tex>::<tex>p(u,v) = \sum\limits_{u,v \in EV, f(u,v)>0} a(u,v) \cdot f(u,v)</tex> имеют }}===Свойства сети===* Поток не может превысить пропускную способность . :<tex>f(u,v) \leqslant c(u,cv)</tex>* Поток из <tex>u</tex> в <tex>v</tex> должен быть противоположным потоку из <tex>v</tex> в <tex>u</tex>. :<tex>f(u,v)=-f(v, u)</tex> * Сохранение потока. Для каждой вершины, сумма входящего и цену исходящего потоков равно <tex>0</tex>.:<tex>\,psum\limits_{w \in V} f(u,vw)= 0</tex>.
Суть задачи — найти {{Задача|definition = Дана сеть <tex>G(V,E)</tex>. <tex>S, T \in V</tex> {{---}} источник и сток. Ребра <tex>(u,v) \in E</tex> имееют пропускную способность <tex> c(u, v), </tex> поток ''<tex> f''(''u'', ''v''):</tex> {{---}}и цену за единицу потока <tex> a(u, v) </tex>. Требуется найти максимальный поток, суммарная стоимость которого минимальна.}}
:<tex>p(f) = \sum_{u,v \in V} p(u,v) \cdot f(u,v) - min </tex>.
:<tex>|f| = \sum_{u,v \in V} f(u,v) = f_0</tex>
}}
== Алгоритмы решения ==
===Метод устранения отрицательных циклов в остаточной сети===Воспользуемся [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети|леммой об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]. Получим следующий алгоритм:====Алгоритм====*Найти любой поток величины '''Начало.'''* '''Шаг 1'''. Определим для каждого прямого ребра <tex>f_0(u,v)</tex>обратное ребро <tex>(v, после чего избавиться от всех циклов отрицательной стоимости в остаточном графеu)</tex>. Чтобы избавиться от циклаОпределим его характеристики: <tex>c(v,u)=0</tex>, <tex>f(v,u)=-f(u,v)</tex>, <tex>a(v,u)=-a(u, надо пустить по нему максимально возможный v)</tex>.* '''Шаг 2'''. Для каждого ребра зададим потокравный <tex>0</tex>. Циклы ищутся * '''Шаг 3'''. Найдем произвольный максимальный поток(любым алгоритмом нахождения максимального потока), построим для него остаточную сеть, где каждому ребру будет соответствовать величина <tex>a(u,v) \cdot (c(u,v) - f(u,v))</tex>.* '''Шаг 4'''. При помощи [[Алгоритм Форда-Беллмана|алгоритма Форда - Беллмана]]найдем отрицательный цикл в построенной сети. Если отрицательный цикл не нашелся {{---}} перейдем к '''шагу 6'''.*[[Поиск_потока_минимальной_стоимости_методом_дополнения_вдоль_путей_минимальной_стоимости|Поиск '''Шаг 5'''. Избавимся от отрицательного цикла, для этого пустим по нему максимально возможный поток. Величина потока равна минимальной остаточной пропускной способности в цикле. Перейдем к '''шагу 4'''.* '''Шаг 6'''. Отрицательных циклов в остаточной сети нет, значит, максимальный поток минимальной стоимости методом найден.* '''Конец.''' ====Асимптотика====Алгоритм Форда-Беллмана работает за <tex>O(VE)</tex>, улучшение цикла за <tex>O(E)</tex>. Если обозначить максимальную стоимость потока как <tex>C</tex>, а максимальную пропускную способность как <tex>U</tex>, то алгоритм совершит <tex>O(ECU)</tex> итераций поиска цикла, если каждое улучшение цикла будет улучшать его на 1. В итоге имеем <tex>O(V E^2 C U + maxFlow)</tex>, где <tex>maxFlow</tex> - асимптотика поиска максимального потока. ===Метод дополнения потока вдоль путей минимальной стоимости]].===*[[Использование_потенциалов_Джонсона_при_поиске_потока_минимальной_стоимости{{main|Использование потенциалов Джонсона при поиске Поиск потока минимальной стоимости (модификация предыдущего алгоритма)]].методом дополнения вдоль путей минимальной стоимости}}
== Задача о назначениях =Использование потенциалов Джонсона===Условие:* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.Решение данной задачи легко сводится к поиску {main|Использование потенциалов Джонсона при поиске потока минимальной стоимости - [[Сведение_задачи_о_назначениях_к_задаче_о_потоке_минимальной_стоимости|задача о назначениях]].}}
== Источник См. также ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)[[Сведение задачи о назначениях к задаче о потоке минимальной стоимости|Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]* [[Венгерский алгоритм решения задачи о назначениях|Венгерский алгоритм решения задачи о назначениях]]
== Ссылки Источники информации ==*[http://ru.wikipedia.org/wiki/Поток_минимальной_стоимости Википедия {{- --}} Поток минимальной стоимости]
*[http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/min-cost-max-flow-2009 Визуализатор алгоритма нахождения максимального потока минимальной стоимости]
*[http://habrahabr.ru/blogs/algorithm/61884/ Хабрахабр {{- --}} Максимальный поток минимальной стоимости]* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. {{---}} М.:Издательский дом "Вильямс", 2010. {{---}} 1296 с.: ил. {{---}} Парал. тит. англ. {{---}} ISBN 978-5-8459-0857-5 (рус.)
[[Категория:Алгоритмы и структуры данных]]
[[Категория: Задача о потоке минимальной стоимости]]
6
правок

Навигация