Русская Википедия:Поток минимальной стоимости
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи потока определённой величины через транспортную сеть.
Определения
Дана транспортная сеть <math>G(V,E)</math> с источником <math>s \in V</math> и стоком <math>t \in V</math>, где рёбра <math>e \in E</math> имеют пропускную способность <math>c(e)</math>, поток <math>f(e)</math> и цену <math>a(e)</math>. Цена пересылки потока для ребра <math>e</math> равна <math>f(e) \cdot a(e)</math>. Необходимо найти поток величиной <math>d</math> единиц.
Суть задачи — найти поток f(u, v), минимизирующий его общую стоимость:
- <math>\sum_{u,v \in V} a(u,v) \cdot f(u,v)</math>
Накладываются следующие условия:
Ограничение пропускной способности: <math>0 \leqslant f(u,v) \leqslant c(u,v)</math>. Поток не может превысить пропускную способность. Антисимметричность: <math>\ f(u,v) = - f(v,u)</math>. Поток из <math>u</math> в <math>v</math> должен быть противоположным потоку из <math>v</math> в <math>u</math>. Сохранение потока: <math>\ \sum_{w \in V} f(u,w) = 0</math>. Необходимый поток: <math>\sum_{w \in V} f(s,w) = d</math>
Отношение к другим задачам
Другой вариант этой задачи — найти максимальный поток имеющий минимальную цену среди максимальных.
Более общая проблема — циркуляция потока минимальной стоимости, которая может быть использована для решения данной задачи. Ставим нижнюю границу для всех рёбер равную нулю и проводим дополнительное ребро из стока <math>t</math> в источник <math>s</math> с пропускной способностью <math>c(t,s)=d</math> и нижней границей <math>l(t,s)=d</math>.
Примечательно, что для <math>d = 1</math>, задача нахождения потока минимальной стоимости соответствует задаче о поиске кратчайшего пути. В случае же, когда стоимость <math>a(e) = 0</math> для всех рёбер графа, задача может быть решена адаптированными алгоритмами поиска максимального потока:
- Как только <math>|f| \geqslant d</math> впервые, останови алгоритм.
- Пусть <math>p</math> величина последнего дополнения потока.
- Замени последний поток на поток со значением <math>p - (|f| - d)</math>.
Существует также и альтернативный вариант решения задачи с нулевой стоимостью рёбер:
- Создай новую вершину-источник <math>s'</math>.
- Добавь ребро <math>e' = (s', s)</math> с пропускной способностью <math>c(e') = d</math>.
- Таким образом максимальный поток будет ограничен <math>d</math>.
Решения
- Задача о потоке минимальной стоимости может быть решена с помощью линейного программирования.
- Найти любой поток данной величины, после чего избавиться от всех циклов отрицательной стоимости в остаточном графе. Чтобы избавиться от цикла, надо пустить по нему максимально возможный поток. Циклы ищутся алгоритмом Беллмана - Форда. Для доказательства работы алгоритма покажем, что поток <math>f</math> графа <math>G</math> не является потоком минимальной стоимости пока остаточная сеть графа <math>G_f</math> содержит отрицательный цикл <math>C</math>. Пусть <math>f^*</math> - поток графа <math>G</math> такой, что <math>l(f^*) < l(f)</math> и, следовательно, оба потока отличны друг от друга. Для всех рёбер <math>e \in E</math> обозначим <math>f'(e) = f^*(e) - f(e)</math> и получим <math>f'</math> - циклический поток. Так как <math>f'</math> образован из максимум <math>m' < m</math> циклов <math>f'_i</math> <math>(1 \leqslant i \leqslant m')</math>, справедливо следующее: <math>l(f') = l(f^*) - l(f) = \sum_{1 \leqslant i \leqslant m'} l(f'_i)</math>, а значит, существует такой <math>j</math>, что <math>l(f'_j) < 0</math>. Для оптимизиации алгоритма можно выбирать каждую итерацию циклы с минимальной средней стоимостью <math>\overline{l}(C) = \frac{l(C)}{|C|} = \frac{\sum_{e \in C} l(e)}{|C|}</math>. Для доказательства времени работы алгоритма разобьем ход его выполнения на фазы, каждая из которых будет состоять из отдельных итераций. Пусть <math>f</math> - поток к началу <math>i</math>-той фазы. Фаза <math>i</math> считается завершенной, когда найден поток <math>g</math> такой, что <math>\mu(g) \leqslant (1 - 1/n) \cdot \mu(f)</math> или <math>\mu(g) \leqslant 0</math>, где <math>\mu(f) = -\overline{l}(C)</math>. При <math>\mu(g) \leqslant 0</math> алгоритм прекращает работу. Далее пусть <math>\mu_0</math> - значение <math>\mu</math> к началу первой фазы и <math>\mu_i</math> - значение <math>\mu</math> к началу <math>i</math>-той фазы (<math>1 \leqslant i \leqslant T</math>). Таким образом действительно: <math>\mu_i \leqslant (1 - 1/n) \cdot \mu_{i-1} \leqslant \frac{\mu_{i-1}}{e^{1/n}}</math>, а также <math>\mu_0 \leqslant L = \sum_{e \in E} |l(e)|</math>. Вследствие свойства целочисленности <math>\mu_{T-1} \geqslant 1/n</math> следует <math>T - 1 \leqslant \log_{e^{1/n}}(nL) = \frac{\ln(nL)}{\ln(e^{1/n})} = n\ln(nL)</math> и <math>T \leqslant n\ln(nL) + 1</math>. Итерации условно можно разбить на несколько видов: Тип 1 - цикл <math>C</math> содержит только рёбра с негативной стоимостью и Тип 2 - цикл <math>C</math> содержит минимум одно ребро с положительной стоимостью. При каждой итерации первого типа будет "насыщено" и удалено хотя бы одно ребро. При этом все образованные рёбра будут иметь положительную стоимость (так как имеют обратное направление в остаточной сети). Таким образом алгоритм завершится после как минимум <math>m</math> последовательных итераций первого типа. Если же в фазе содержатся более <math>m</math> итераций, после <math>m-1</math> итераций максимум будет выполнена итерация второго типа. Покажем однако, что такое невозможно: Пусть <math>g</math> - поток первой итерации второго типа. Заметим, что действительно <math>\forall e \in E(G_g) : l(e) \geqslant -\mu(f)</math>, т.е. нет новых рёбер с отрицательной стоимостью. Пусть <math>C</math> - цикл в <math>G_g</math> с минимальным <math>\overline{l}(C)</math> и <math>H</math> - рёбра с отрицательной стоимостью в <math>C</math>: <math>\mu(g) = \sum_{e \in C} \frac{-l(e)}{|C|} \leqslant \sum_{e \in H} \frac{-l(e)}{|C|} \leqslant |H| \cdot \frac{\mu(f)}{|C|}</math>. Из <math>|H| \leqslant |C| - 1</math> следует <math>|H|/|C| \leqslant 1 - 1/|C| \leqslant 1 - 1/n</math>. Таким образом <math>\mu(g) \leqslant (1 - 1/n) \cdot \mu(f)</math>. Противоречие - мы уже достигли конца фазы, а значит итераций второго типа не существует и каждая фаза заканчивается через <math>m-1</math> итераций первого типа. Цикл с минимальным средним весом может быть найден за <math>O(|V||E|)</math>. Доказательство: Пусть <math>d_k(v)</math> - стоимость самого выгодного пути к <math>v \in V</math> через ровно <math>k</math> рёбер, тогда действительно <math>d_0(v) = 0</math> и <math>d_{k+1}(v) = \min_{e = (w, v) \in E_f}(d_k(w) + l(e))</math>. Выходит, что все значения <math>d_k(v)</math> можно подсчитать за <math>O(nm)</math> используя динамическое программирование. Лемма: Значение <math>\overline{l}(C)</math> цикла с минимальной средней стоимостью равно <math>\alpha = \min_{v \in V}\max_{j=0}^{n-1}(\frac{d_n(v) - d_j(v)}{n - j})</math>. Пусть <math>C</math> - цикл с минимальной средней стоимостью. Если увеличить стоимость всех рёбер на <math>\delta</math>, то <math>C</math> останется циклом с минимальной средней стоимостью, однако значение цикла увеличится на <math>\delta</math>. таким образом можно увеличить все стоимости рёбер так, что <math>\overline{l}(C) = 0</math>. Покажем, что <math>\alpha \geqslant 0</math>: Выеберем любую вершину <math>v</math> и путь <math>P</math>, заканчивающийся в <math>v</math> и имеющий стоимость <math>d_n(v)</math>. <math>P</math> должен содержать цикл <math>C</math>. Пусть <math>P'</math> - путь <math>P</math> не содержащий цикла <math>C</math> и имеющий длину <math>j</math>. Тогда в цикле имеется <math>n - j</math> рёбер. Из-за <math>l(C) \geqslant 0</math> справедливо <math>d_n(v) = l(P) = l(C) + l(P') \geqslant l(P') \geqslant d_j(v)</math> и для каждой вершины <math>v</math> существует <math>j \in \{1, ..., n-1\}</math> такой, что <math>d_n(v) \geqslant d_j(v)</math>. Покажем, что <math>\alpha \leqslant 0</math>: Для этого докажем, что существует вершина <math>w</math> для которой истино <math>d_n(w) \leqslant d_j(w)</math> для всех <math>j \in \{1, ..., n-1\}</math>. Пусть <math>v</math> - вершина цикла с минимальной средней стоимостью <math>C</math>, <math>P</math> - кратчайший путь, заканчивающийся на <math>v</math> и не содержащий в себе цикла. пусть <math>p < n</math> количество вершин в <math>P</math>. Также ввёдем вершину <math>w</math>, которая лежит на <math>C</math> на расстоянии <math>n - p</math> вершин от <math>v</math>. Путь от <math>v</math> к <math>w</math> назовём <math>Q</math>. Пусть <math>R</math> - путь из <math>w</math> к <math>v</math>, а <math>S</math> - путь минимальной длины <math>j</math> из источника графа к <math>w</math>. Тогда истино следующее: <math>d_n(w) \leqslant l(P) + l(Q) = d_p(v) + l(Q)</math>, а также <math>d_p(v) \leqslant d_{j+r}(v) \leqslant d_j(w) + l(R)</math> и из них следует, что <math>d_n(w) \leqslant d_j(w) + l(R) + l(Q)</math>. Путь <math>Q \odot R</math> имеет стоимость 0, т.к. <math>l(C) = 0</math>. Таким образом <math>d_n(w) \leqslant d_j(w)</math> для всех <math>j \in \{1, ..., n-1\}</math>. Учитывая лемму, получим <math>\alpha \leqslant 0</math>. Время выполнения такого алгоритам составит <math>O(m^2 \cdot n^2 \cdot \log(nL))</math>, так как в процессе выполнения алгоритма пройдут <math>n\log(nL) + 1</math> фаз, в каждой из которых <math>m</math> итераций, требующих <math>O(nm)</math> времени. Основываясь не предидущей оценке времени можно составить и следующую: <math>O(m^3 \cdot n^2 \cdot \log(n))</math>.
- Использовать модификацию алгоритма Форда — Фалкерсона, в которой на каждом шаге выбирается увеличивающий путь минимальной цены. Для выбора пути можно воспользоваться алгоритмом Беллмана-Форда.
- Улучшение предыдущего алгоритма: используя потенциалы, можно свести задачу к задаче без отрицательных рёбер, после чего вместо алгоритма Беллмана-Форда воспользоваться алгоритмом Дейкстры. Алгоритм Беллмана-Форда придётся применить лишь на самом первом шаге.
Ссылки
См. также
Литература
