Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости — различия между версиями
(→Идея) |
м (rollbackEdits.php mass rollback) |
||
(не показано 49 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | ==Теорема Форда-Фалкерсона== |
− | + | Задача о потоке минимальной стоимости состоит в нахождении среди всех [[Определение сети, потока|потоков]] данной величины наименее затратного. | |
− | |||
− | == | + | {{Лемма |
+ | |about= | ||
+ | о представлении потоков | ||
+ | |statement= | ||
+ | Пусть <tex> f </tex> и <tex> g </tex> {{---}} потоки в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f + f'</tex>, где <tex>f'</tex> {{---}} поток в остаточной сети <tex>G_f</tex>. | ||
+ | |proof= | ||
+ | Рассмотрим произвольное ребро <tex> (u, v) </tex> из <tex> G </tex>. <tex> f'(u, v) = g(u, v) - f(u, v) \leqslant c(u, v) - f(u, v) = c_f(u, v) </tex>. Таким образом, поток через каждое ребро не превосходит пропускной способности остаточной сети. | ||
+ | Антисимметричность и закон сохранения потока проверяются аналогично [[Лемма о сложении потоков|лемме о сложении потоков]]. | ||
+ | }} | ||
− | + | {{Теорема | |
− | + | |statement= | |
− | } | + | Пусть: <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>, <tex> f </tex> {{---}} поток минимальной стоимости в сети <tex> G </tex> среди потоков величины <tex> a </tex>, <tex> P </tex> {{---}} путь минимальной стоимости <tex> s \leadsto t</tex> в остаточной сети. |
− | + | Тогда: | |
− | + | <tex>\forall \delta : 0 \leqslant \delta \leqslant c_f(P)</tex> поток <tex>f + \delta \cdot f_P</tex> {{---}} поток минимальной стоимости среди потоков величины <tex>a + \delta</tex>, где <tex>\delta \cdot f_P</tex> {{---}} поток величины <tex>\delta</tex>, проходящий по пути <tex>P</tex>. | |
− | |||
− | |||
− | == | + | |proof= |
− | + | Пусть <tex> g </tex> {{---}} поток минимальной стоимости величины <tex>a + \delta</tex> в <tex>G</tex>. Представим <tex> g = f + f'</tex>, где <tex> f' </tex> {{---}} поток в остаточной сети <tex>G_f</tex>. Тогда разность <tex> g - f</tex> будет потоком в сети <tex>G_f</tex> и по [[Лемма о сложении потоков|лемме о сложении потоков]] его величина будет равна <tex>\delta</tex>. | |
− | ==Асимптотика== | + | По [[Теорема о декомпозиции|теореме о декомпозиции]] <tex> g - f</tex> можно представить как сумму элементарных потоков вдоль путей <tex>P_i : s \leadsto t</tex> и циклов <tex>C_i</tex>. В этом представлении нет отрицательных циклов, иначе прибавление его к <tex> f </tex> даст поток меньшей стоимости. Если есть положительный цикл, то вычтем его из <tex> g </tex> и получим поток меньшей стоимости. Таким образом, <tex>p(C_i) = 0</tex> для всех циклов. |
+ | |||
+ | Тогда <tex>p(g - f) = \sum\limits_{P_i} p(P_i)\cdot c_f(P_i) \geqslant p(P) \cdot \sum\limits_{P_i}c_f(P_i) \geqslant p(P) \cdot \delta</tex>. | ||
+ | |||
+ | Отсюда <tex> p(g) \geqslant p(f) + p(P) \cdot \delta \geqslant p(g) </tex> и поток <tex>f + \delta \cdot f_P</tex> {{---}} минимальный. | ||
+ | |||
+ | }} | ||
+ | |||
+ | ==Алгоритм== | ||
+ | На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из <tex>s</tex> в <tex>t</tex> в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса. | ||
+ | |||
+ | ===Описание=== | ||
+ | * Начало. | ||
+ | * '''Шаг 1'''. Для каждого ребра зададим поток равный <tex>0</tex>. | ||
+ | * '''Шаг 2'''. Построим остаточную сеть <tex>G_f</tex>. | ||
+ | * '''Шаг 3'''. Если существует путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex> {{---}} перейдем к '''шагу 4''', иначе к '''шагу 6'''. | ||
+ | * '''Шаг 4'''. Найдем путь <tex>s \leadsto t</tex> c минимальной стоимостью: путь <tex> P</tex>. | ||
+ | * '''Шаг 5'''. Дополним поток <tex>f</tex> вдоль пути <tex>P</tex>. | ||
+ | * '''Шаг 6'''. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути. | ||
+ | * Конец. | ||
+ | |||
+ | ===Реализация=== | ||
+ | |||
+ | Пусть задана структура <tex>Edge</tex>: | ||
+ | '''struct''' edge: | ||
+ | '''int''' from | ||
+ | '''int''' to | ||
+ | '''double''' c <font color=green>// пропускная способность ребра</font> | ||
+ | '''double''' flow <font color=green>// поток через ребро</font> | ||
+ | '''double''' price <font color=green>// стоимость перемещения единицы потока через ребро</font> | ||
+ | |||
+ | Будем использовать структуру для хранения ребер графа G. | ||
+ | |||
+ | '''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t): | ||
+ | '''for''' edge '''in''' <tex>E</tex>: | ||
+ | edge.flow = 0 | ||
+ | '''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>: | ||
+ | P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью. | ||
+ | maxFlow = <tex>\displaystyle \min_{edge \in P} edge.c - edge.flow</tex> | ||
+ | '''for''' edge '''in''' P: | ||
+ | edge.flow += maxFlow | ||
+ | '''return''' <tex>E</tex> | ||
+ | |||
+ | ===Асимптотика=== | ||
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>. | Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его <tex>F(V, E)</tex>. В сетях с целочисленной пропускной способностью итераций будет не более <tex>|f|</tex>. | ||
Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>. | Итого получаем время работы <tex>O(F(V, E) \cdot |f|)</tex>. | ||
− | == | + | ==См. также== |
+ | *[[Поток минимальной стоимости| Поток минимальной стоимости]] | ||
+ | *[[Использование потенциалов Джонсона при поиске потока минимальной стоимости| Использование потенциалов Джонсона при поиске потока минимальной стоимости]] | ||
+ | |||
+ | ==Источники информации== | ||
+ | *[https://ru.wikipedia.org/wiki/Теорема_Форда_—_Фалкерсона Wikipedia {{---}} Теорема Форда-Фалкерсона] | ||
* Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993) | * Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993) | ||
+ | |||
+ | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория: Задача о потоке минимальной стоимости]] | [[Категория: Задача о потоке минимальной стоимости]] |
Текущая версия на 19:15, 4 сентября 2022
Теорема Форда-Фалкерсона
Задача о потоке минимальной стоимости состоит в нахождении среди всех потоков данной величины наименее затратного.
Лемма (о представлении потоков): |
Пусть и — потоки в сети . Тогда можно представить как сумму , где — поток в остаточной сети . |
Доказательство: |
Рассмотрим произвольное ребро Антисимметричность и закон сохранения потока проверяются аналогично из . . Таким образом, поток через каждое ребро не превосходит пропускной способности остаточной сети. лемме о сложении потоков. |
Теорема: |
Пусть: — сеть с истоком и стоком , — поток минимальной стоимости в сети среди потоков величины , — путь минимальной стоимости в остаточной сети.
Тогда: поток — поток минимальной стоимости среди потоков величины , где — поток величины , проходящий по пути . |
Доказательство: |
Пусть лемме о сложении потоков его величина будет равна . — поток минимальной стоимости величины в . Представим , где — поток в остаточной сети . Тогда разность будет потоком в сети и поПо теореме о декомпозиции можно представить как сумму элементарных потоков вдоль путей и циклов . В этом представлении нет отрицательных циклов, иначе прибавление его к даст поток меньшей стоимости. Если есть положительный цикл, то вычтем его из и получим поток меньшей стоимости. Таким образом, для всех циклов. Тогда Отсюда . и поток — минимальный. |
Алгоритм
На основании теоремы построим алгоритм. На каждой итерации алгоритма будем находить путь минимальной стоимости из
в в остаточной сети и дополнять поток вдоль него. Выбирать алгоритм для поиска кратчайших путей следует с учетом того, что в ходе алгоритма появляются ребра отрицательного веса.Описание
- Начало.
- Шаг 1. Для каждого ребра зададим поток равный .
- Шаг 2. Построим остаточную сеть .
- Шаг 3. Если существует путь в остаточной сети — перейдем к шагу 4, иначе к шагу 6.
- Шаг 4. Найдем путь c минимальной стоимостью: путь .
- Шаг 5. Дополним поток вдоль пути .
- Шаг 6. Поток минимальной стоимости найден, т.к в остаточной сети не осталось ни одного пути.
- Конец.
Реализация
Пусть задана структура
:struct edge: int from int to double c // пропускная способность ребра double flow // поток через ребро double price // стоимость перемещения единицы потока через ребро
Будем использовать структуру для хранения ребер графа G.
Edge[] findMinCostMaxFlow(, int s, int t): for edge in : edge.flow = 0 while путь в остаточной сети : P = путь с наименьшей стоимостью. maxFlow = for edge in P: edge.flow += maxFlow return
Асимптотика
Каждая итерация выполняется за время работы поиска кратчайшего пути, обозначим его
. В сетях с целочисленной пропускной способностью итераций будет не более .Итого получаем время работы
.См. также
Источники информации
- Wikipedia — Теорема Форда-Фалкерсона
- Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows (1993)