Алгоритм поиска блокирующего потока в ациклической сети — различия между версиями
(→Подробное описание) |
(→Удаляющий обход) |
||
(не показано 47 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
− | ==Жадный | + | ==Жадный алгоритм== |
Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока]] <tex>s</tex> в [[Определение_сети,_потока|сток]] <tex>t</tex>, пока это возможно. [[Обход в глубину, цвета вершин| Обход в глубину]] найдёт все пути из <tex>s</tex> в <tex>t</tex>, если из <tex>s</tex> достижима <tex>t</tex>, а [[Определение_сети,_потока|пропускная способность]] каждого ребра <tex>c(u, v)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока <tex>t</tex>, следовательно блокирующий поток всегда найдётся. | Идея заключается в том, чтобы по одному находить пути из [[Определение_сети,_потока|истока]] <tex>s</tex> в [[Определение_сети,_потока|сток]] <tex>t</tex>, пока это возможно. [[Обход в глубину, цвета вершин| Обход в глубину]] найдёт все пути из <tex>s</tex> в <tex>t</tex>, если из <tex>s</tex> достижима <tex>t</tex>, а [[Определение_сети,_потока|пропускная способность]] каждого ребра <tex>c(u, v)>0</tex> поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока <tex>t</tex>, следовательно блокирующий поток всегда найдётся. | ||
Строка 5: | Строка 5: | ||
==Удаляющий обход== | ==Удаляющий обход== | ||
− | Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое | + | Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту. |
− | + | '''int''' dfs('''int''' <tex>v</tex>, '''int''' flow) | |
− | + | '''if''' (flow == 0) | |
− | + | '''return''' 0 | |
− | if( | + | '''if''' (<tex>v</tex> == <tex>t</tex>) |
− | + | '''return''' flow | |
− | + | '''for''' (<tex>u</tex> = ptr[<tex>v</tex>] '''to''' n) | |
− | + | '''if''' (<tex>vu \in E</tex>) | |
− | + | pushed = dfs(<tex>u</tex>, min(flow, c(<tex>vu</tex>) - f(<tex>vu</tex>))) | |
− | + | f(<tex>vu</tex>) += pushed | |
− | + | f(<tex>uv</tex>) -= pushed | |
− | + | '''return''' pushed | |
− | + | ptr[<tex>v</tex>]++ | |
− | + | '''return''' 0 | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''main'''() | |
+ | '''...''' | ||
+ | flow = 0 | ||
+ | '''for''' ('''int''' i = 1 '''to''' n) | ||
+ | ptr[i] = 0 | ||
+ | '''do''' | ||
+ | pushed = dfs(<tex>s</tex>, <tex>\infty</tex>) | ||
+ | flow += pushed | ||
+ | '''while''' (pushed > 0) | ||
− | <b>Замечание</b> Если в [[Схема алгоритма Диница|алгоритме Диница]] искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] <tex>O(VE^2)</tex>. | + | |
+ | Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>V</tex> — число вершин в графе, а <tex>K</tex> — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + \sum\limits_i{K_i})</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается <tex>O(VE)</tex>. | ||
+ | |||
+ | <b>Замечание:</b> Если в [[Схема алгоритма Диница|алгоритме Диница]] искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] <tex>O(VE^2)</tex>. | ||
==Алгоритм Малхотры — Кумара — Махешвари== | ==Алгоритм Малхотры — Кумара — Махешвари== | ||
===Идея=== | ===Идея=== | ||
− | Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину <tex>v</tex> с минимальным потенциалом <tex>p</tex>. Затем пускается поток величины <tex>p</tex> из истока в сток, проходящий через эту вершину. При этом если [[Дополняющая сеть, дополняющий путь|остаточная пропускная способность]] ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные | + | Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину <tex>v</tex> с минимальным потенциалом <tex>p</tex>. Затем пускается поток величины <tex>p</tex> из истока в сток, проходящий через эту вершину. При этом если [[Дополняющая сеть, дополняющий путь|остаточная пропускная способность]] ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные рёбра удаляются. |
===Подробное описание=== | ===Подробное описание=== | ||
− | Для каждой вершины <tex>v</tex>вычислим входящий и исходящий потенциал <tex> | + | * Для каждой вершины <tex>v</tex> вычислим входящий и исходящий потенциал: <tex>p_{in}=\sum \limits_{u} c(u, v)</tex> и <tex>p_{out}=\sum \limits_{u} c(v, u)</tex>. Пусть <tex>p_{in}(s)=\infty</tex> и <tex>p_{out}(t)=\infty</tex>. Определим потенциал или пропускную способность вершины в [[Определение сети, потока|сети]] <tex>p(v)=min(p_{in}(v), p_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через неё проходить. Ясно, что через вершины с <tex>p(v)=0</tex> поток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, дополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удалёнными. Если в результате появятся новые вершины с <tex>p(v)=0</tex>, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с <tex>p(v)\ne0</tex>. |
− | После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою. Протолкнем <tex>p</tex> единиц потока из вершины | + | * После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою и <tex>p(v)=min (p(w), w \in L_k)</tex>, где <tex>L_k</tex> — <tex>k</tex>-й слой. Протолкнем <tex>p(v)</tex> единиц потока из вершины <tex>v</tex> в смежные с ней вершины по исходящим дугам с [[Дополняющая сеть, дополняющий путь | остаточной пропускной способностью]] <tex>c_f \ne 0</tex>. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя. |
+ | |||
+ | * Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины <tex>(k+2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток <tex>t</tex>, ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины <tex>p(v)</tex>, отправленный из вершины <tex>v</tex>, где <tex>p(v)</tex> - минимальный полностью соберется в <tex>t</tex>. | ||
+ | |||
+ | * На втором этапе вновь, начиная с вершины <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем <tex>(k-2)</tex>-го. И так до тех пор, пока весь поток величины <tex>p(v)</tex>, отправленный в вершину <tex>v</tex>, где <tex>p(v)</tex> - минимальный, не соберется в истоке <tex>s</tex>. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>. | ||
Строка 53: | Строка 60: | ||
while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>) | while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>) | ||
{ | { | ||
− | найдём <tex>v</tex> с | + | найдём <tex>v</tex> с минимальной пропускной способностью <tex>g</tex>; |
проталкиваем <tex>g</tex> единиц потока из <tex>v</tex> в <tex>t</tex>; | проталкиваем <tex>g</tex> единиц потока из <tex>v</tex> в <tex>t</tex>; | ||
проталкиваем <tex>g</tex> единиц потока из <tex>s</tex> в <tex>v</tex>; | проталкиваем <tex>g</tex> единиц потока из <tex>s</tex> в <tex>v</tex>; | ||
Строка 63: | Строка 70: | ||
===Асимптотика=== | ===Асимптотика=== | ||
− | Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых | + | Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий. |
+ | |||
+ | == См. также == | ||
+ | * [[Блокирующий поток]] | ||
+ | * [[Схема алгоритма Диница]] | ||
− | ==Источники== | + | ==Источники информации== |
− | *[http://e-maxx.ru/algo/dinic | + | * [http://e-maxx.ru/algo/dinic MAXimal :: algo :: Алгоритм Диница] |
*[http://www.facweb.iitkgp.ernet.in/~arijit/courses/autumn2006/cs60001/lec-flow-4.pdf The MPM Algorithm] | *[http://www.facweb.iitkgp.ernet.in/~arijit/courses/autumn2006/cs60001/lec-flow-4.pdf The MPM Algorithm] | ||
*[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%B0%D0%BB%D1%85%D0%BE%D1%82%D1%80%D1%8B_%E2%80%94_%D0%9A%D1%83%D0%BC%D0%B0%D1%80%D0%B0_%E2%80%94_%D0%9C%D0%B0%D1%85%D0%B5%D1%88%D0%B2%D0%B0%D1%80%D0%B8 Алгоритм Малхотры — Кумара — Махешвари] | *[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%B0%D0%BB%D1%85%D0%BE%D1%82%D1%80%D1%8B_%E2%80%94_%D0%9A%D1%83%D0%BC%D0%B0%D1%80%D0%B0_%E2%80%94_%D0%9C%D0%B0%D1%85%D0%B5%D1%88%D0%B2%D0%B0%D1%80%D0%B8 Алгоритм Малхотры — Кумара — Махешвари] | ||
+ | *[http://eprints.utas.edu.au/160/1/iplFlow.pdf Оригинальная публикация алгоритма Малхотры — Кумара — Махешвари.] | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Задача о максимальном потоке]] | [[Категория:Задача о максимальном потоке]] |
Версия 00:33, 18 апреля 2019
Содержание
Жадный алгоритм
Идея заключается в том, чтобы по одному находить пути из истока в сток , пока это возможно. Обход в глубину найдёт все пути из в , если из достижима , а пропускная способность каждого ребра поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока , следовательно блокирующий поток всегда найдётся.
Используя
, каждый путь находится за , где — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет путей. Итого общая асимптотика составляет .Удаляющий обход
Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока
. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.int dfs(int, int flow) if (flow == 0) return 0 if ( == ) return flow for ( = ptr[ ] to n) if ( ) pushed = dfs( , min(flow, c( ) - f( ))) f( ) += pushed f( ) -= pushed return pushed ptr[ ]++ return 0
main() ... flow = 0 for (int i = 1 to n) ptr[i] = 0 do pushed = dfs(, ) flow += pushed while (pushed > 0)
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за , где — число вершин в графе, а — число продвижения указателей. Ввиду того, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет , где — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за , что, учитывая, что все указатели в сумме прошли расстояние , дает асимптотику . В худшем случае, когда блокирующий поток насыщает все рёбра, асимптотика получается .
Замечание: Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит , что уже лучше эффективности алгоритма Эдмондса-Карпа .
Алгоритм Малхотры — Кумара — Махешвари
Идея
Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные рёбра удаляются.
с минимальным потенциалом . Затем пускается поток величины из истока в сток, проходящий через эту вершину. При этом еслиПодробное описание
- Для каждой вершины сети . Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через неё проходить. Ясно, что через вершины с поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удалёнными. Если в результате появятся новые вершины с , удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с . вычислим входящий и исходящий потенциал: и . Пусть и . Определим потенциал или пропускную способность вершины в
- После этого приступим к построению блокирующего потока. Пусть вершина принадлежит -ому слою и , где — -й слой. Протолкнем единиц потока из вершины в смежные с ней вершины по исходящим дугам с остаточной пропускной способностью . Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины ) проталкиваемый поток соберется в вершинах -го слоя.
- Повторим процесс отправки потока из вершин -го слоя, содержащих избыток потока, в смежные им вершины -го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток , ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины , отправленный из вершины , где - минимальный полностью соберется в .
- На втором этапе вновь, начиная с вершины , осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам -го слоя, затем -го. И так до тех пор, пока весь поток величины , отправленный в вершину , где - минимальный, не соберется в истоке . Таким образом, поток и во вспомогательной и в основной сети увеличится на величину .
MPM algorithm() { foreach ; Вычисляем остаточную сеть ; Найдём вспомогательный граф для ; while ( ) { while ( достижима из в ) { найдём с минимальной пропускной способностью ; проталкиваем единиц потока из в ; проталкиваем единиц потока из в ; изменяем , и ; } вычисляем новый вспомогательный граф из ; } }
Асимптотика
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено
действий, где соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено действий.