Поток минимальной стоимости (Hkmkt bnunbgl,ukw vmknbkvmn)
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи потока определённой величины через транспортную сеть.
Определения
[править | править код]Дана транспортная сеть с источником и стоком , где рёбра имеют пропускную способность , поток и цену . Цена пересылки потока для ребра равна . Необходимо найти поток величиной единиц.
Суть задачи — найти поток f(u, v), минимизирующий его общую стоимость:
Накладываются следующие условия:
Ограничение пропускной способности: . Поток не может превысить пропускную способность. Антисимметричность: . Поток из в должен быть противоположным потоку из в . Сохранение потока: . Необходимый поток:
Отношение к другим задачам
[править | править код]Другой вариант этой задачи — найти максимальный поток имеющий минимальную цену среди максимальных.
Более общая проблема — циркуляция потока минимальной стоимости, которая может быть использована для решения данной задачи. Ставим нижнюю границу для всех рёбер равную нулю и проводим дополнительное ребро из стока в источник с пропускной способностью и нижней границей .
Примечательно, что для , задача нахождения потока минимальной стоимости соответствует задаче о поиске кратчайшего пути. В случае же, когда стоимость для всех рёбер графа, задача может быть решена адаптированными алгоритмами поиска максимального потока:
- Как только впервые, останови алгоритм.
- Пусть величина последнего дополнения потока.
- Замени последний поток на поток со значением .
Существует также и альтернативный вариант решения задачи с нулевой стоимостью рёбер:
- Создай новую вершину-источник .
- Добавь ребро с пропускной способностью .
- Таким образом максимальный поток будет ограничен .
Решения
[править | править код]- Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
- Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда. Для доказательства работы алгоритма покажем, что поток графа не является потоком минимальной стоимости пока остаточная сеть графа содержит отрицательный цикл . Пусть - поток графа такой, что и, следовательно, оба потока отличны друг от друга. Для всех рёбер обозначим и получим - циклический поток. Так как образован из максимум циклов , справедливо следующее: , а значит, существует такой , что . Для оптимизиации алгоритма можно выбирать каждую итерацию циклы с минимальной средней стоимостью . Для доказательства времени работы алгоритма разобьем ход его выполнения на фазы, каждая из которых будет состоять из отдельных итераций. Пусть - поток к началу -той фазы. Фаза считается завершенной, когда найден поток такой, что или , где . При алгоритм прекращает работу. Далее пусть - значение к началу первой фазы и - значение к началу -той фазы (). Таким образом действительно: , а также . Вследствие свойства целочисленности следует и . Итерации условно можно разбить на несколько видов: Тип 1 - цикл содержит только рёбра с негативной стоимостью и Тип 2 - цикл содержит минимум одно ребро с положительной стоимостью. При каждой итерации первого типа будет "насыщено" и удалено хотя бы одно ребро. При этом все образованные рёбра будут иметь положительную стоимость (так как имеют обратное направление в остаточной сети). Таким образом алгоритм завершится после как минимум последовательных итераций первого типа. Если же в фазе содержатся более итераций, после итераций максимум будет выполнена итерация второго типа. Покажем однако, что такое невозможно: Пусть - поток первой итерации второго типа. Заметим, что действительно , т.е. нет новых рёбер с отрицательной стоимостью. Пусть - цикл в с минимальным и - рёбра с отрицательной стоимостью в : . Из следует . Таким образом . Противоречие - мы уже достигли конца фазы, а значит итераций второго типа не существует и каждая фаза заканчивается через итераций первого типа. Цикл с минимальным средним весом может быть найден за . Доказательство: Пусть - стоимость самого выгодного пути к через ровно рёбер, тогда действительно и . Выходит, что все значения можно подсчитать за используя динамическое программирование. Лемма: Значение цикла с минимальной средней стоимостью равно . Пусть - цикл с минимальной средней стоимостью. Если увеличить стоимость всех рёбер на , то останется циклом с минимальной средней стоимостью, однако значение цикла увеличится на . таким образом можно увеличить все стоимости рёбер так, что . Покажем, что : Выеберем любую вершину и путь , заканчивающийся в и имеющий стоимость . должен содержать цикл . Пусть - путь не содержащий цикла и имеющий длину . Тогда в цикле имеется рёбер. Из-за справедливо и для каждой вершины существует такой, что . Покажем, что : Для этого докажем, что существует вершина для которой истино для всех . Пусть - вершина цикла с минимальной средней стоимостью , - кратчайший путь, заканчивающийся на и не содержащий в себе цикла. пусть количество вершин в . Также ввёдем вершину , которая лежит на на расстоянии вершин от . Путь от к назовём . Пусть - путь из к , а - путь минимальной длины из источника графа к . Тогда истино следующее: , а также и из них следует, что . Путь имеет стоимость 0, т.к. . Таким образом для всех . Учитывая лемму, получим . Время выполнения такого алгоритам составит , так как в процессе выполнения алгоритма пройдут фаз, в каждой из которых итераций, требующих времени. Основываясь не предидущей оценке времени можно составить и следующую: .
- Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
- Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.
Ссылки
[править | править код]См. также
[править | править код]Литература
[править | править код]- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.