Алгоритм поиска блокирующего потока в ациклической сети — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея)
(Алгоритм узкого места)
Строка 24: Строка 24:
 
===Идея===
 
===Идея===
 
Для каждой вершины  вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>\rho</tex>. Затем пускается поток величины <tex>\rho</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
 
Для каждой вершины  вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>\rho</tex>. Затем пускается поток величины <tex>\rho</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
 +
 +
===Подробное описание===
 +
Для каждой вершины вычислим входящий и исходящий потенциал вершин — сумму пропускных способностей дуг сети Диница, входящих и исходящих из вершины соответственно. Входящий потенциал истока и исходящий потенциал стока положим равными бесконечности. Определим потенциал или пропускную способность вершины в сети как минимум из ее входящего и исходящего потенциалов. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с нулевым потенциалом поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с нулевым потенциалом, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с ненулевым потенциалом.
 +
 +
После этого приступим к построению блокирующего потока. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою. Протолкнем <tex>p</tex> единиц потока из вершины с минимальным потенциалом в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя. Повторим процесс отправки потока из вершин <tex>(k+1)</tex>-го слоя, содержащих избыток потока, в смежные им вершины <tex>(k+2)</tex>-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины <tex>p</tex>, отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины <tex>v</tex>, осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам <tex>(k-1)</tex>-го слоя, затем <tex>(k-2)</tex>-го. И так до тех пор, пока весь потока величины <tex>p</tex>, отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину <tex>p</tex>.
 +
  
 
  <tex>MPM algorithm(s, t)</tex>
 
  <tex>MPM algorithm(s, t)</tex>

Версия 01:11, 25 декабря 2011

Жадный Алгоритм

Идея

Идея заключается в том, чтобы по одному находить пути из [math]s[/math] в [math]t[/math], пока это возможно.

Корректность

Данная идея корректна, поскольку [math]dfs[/math] найдёт все пути из [math]s[/math] в [math]t[/math], если из [math]s[/math] достижима [math]t[/math], а пропускная способность каждого ребра [math]c(u, v)\gt 0[/math] поэтому, насыщая рёбра, мы хотя бы единожды достигнем стока [math]t[/math], следовательно блокирующий поток всегда найдётся.

Асимптотика

Используя [math]dfs[/math] каждый путь находится за [math]O(E)[/math]. Поскольку каждый путь насыщает как минимум одно ребро, всего будет [math]O(E)[/math] путей. Итого общая асимптотика составляет [math]O(E^2)[/math].

Удаляющий обход

Идея

По-прежнему по одному находятся пути из [math]s[/math] в [math]t[/math], но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока. То есть, если для текущей вершины [math]v[/math] выполнено [math]dfs(v) = false[/math], нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину.

Корректность

Аналогично предыдущему пункту.

Асимптотика

Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за [math]O(V + K)[/math], где [math]K[/math] - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет [math]O(P)[/math], где [math]P[/math] — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за [math]O(PV + \sum\limits_i{K_i})[/math], что, учитывая, что все указатели в сумме прошли расстояние [math]O(E)[/math], дает асимптотику [math]O(PV + E)[/math]. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается [math]O(VE)[/math].

Замечание Если в алгоритме Диница искать блокирующий поток удаляющим обходом, то его эффективность составит [math]O(V^2E)[/math], что уже лучше эффективности алгоритма Эдмондса-Карпа [math]O(VE^2)[/math].

Алгоритм узкого места

Идея

Для каждой вершины вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина [math]r[/math] с минимальным потенциалом [math]\rho[/math]. Затем пускается поток величины [math]\rho[/math] из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.

Подробное описание

Для каждой вершины вычислим входящий и исходящий потенциал вершин — сумму пропускных способностей дуг сети Диница, входящих и исходящих из вершины соответственно. Входящий потенциал истока и исходящий потенциал стока положим равными бесконечности. Определим потенциал или пропускную способность вершины в сети как минимум из ее входящего и исходящего потенциалов. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с нулевым потенциалом поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с нулевым потенциалом, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с ненулевым потенциалом.

После этого приступим к построению блокирующего потока. Пусть вершина [math]v[/math] принадлежит [math]k[/math]-ому слою. Протолкнем [math]p[/math] единиц потока из вершины с минимальным потенциалом в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины [math]v[/math]) проталкиваемый поток соберется в вершинах [math](k+1)[/math]-го слоя. Повторим процесс отправки потока из вершин [math](k+1)[/math]-го слоя, содержащих избыток потока, в смежные им вершины [math](k+2)[/math]-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое. Заметим, что в этом слое содержится только сток, ибо все остальные вершины, ранее ему принадлежащие, были удалены из сети Диница, как вершины, имеющие нулевой потенциал. Следовательно, весь поток величины [math]p[/math], отправленный из вершины с минимальным потенциалом полностью соберется в стоке. На втором этапе вновь, начиная с вершины [math]v[/math], осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам [math](k-1)[/math]-го слоя, затем [math](k-2)[/math]-го. И так до тех пор, пока весь потока величины [math]p[/math], отправленные из вершины с минимальным потенциалом, не соберется в истоке. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину [math]p[/math].


[math]MPM algorithm(s, t)[/math]
[math]for each (uv) \in E[/math]
  [math]f(uv)[/math] = 0;
Вычисляем остаточную сеть [math]R[/math];
Найдём вспомогательный граф [math]L[/math] для [math]R[/math];
[math]while (t \in L)[/math]
[math]begin[/math]
  [math]while[/math] ([math]t[/math] достижима из [math]s[/math] в [math]L[/math])
  [math]begin[/math]
    найдём [math]v[/math] с миниальной пропускной способностью [math]g[/math];
    проталкиваем [math]g[/math] единиц потока из [math]v[/math] в [math]t[/math];
    проталкиваем [math]g[/math] единиц потока из [math]s[/math] в [math]v[/math];
    изменяем [math]f[/math], [math]L[/math] и [math]R[/math];
  [math]end[/math]
  вычисляем новый вспомогательный граф [math]L[/math] из [math]R[/math];
[math]end[/math]

Асимптотика

Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено [math]O(V + E_i)[/math] действий, где [math]V[/math] соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а [math]E_i[/math] — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено [math]\sum\limits_i{O(V+E_i)} = O(V^2)[/math] действий.

Замечание Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.

Волновой алгоритм

Используя предпотоки, позволяет найти блокирующий поток за [math]O(V^2)[/math]. Модификация алгоритма Диница, основанная на этом алгоритме, называется алгоритмом Карзанова.

Источники