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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Жадный Алгоритм== ===Идея=== Идея заключается в том, чтобы по одному находить пути из <tex>s</tex> …»)
 
(Асимптотика)
Строка 11: Строка 11:
  
 
===Асимптотика===
 
===Асимптотика===
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>K</tex> - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + PK)</tex>, что, учитывая, что все указатели в сумме прошли расстояние <tex>O(E)</tex>, дает асимптотику <tex>O(PV + E)</tex>. В худшем случае, когда блокирующий поток насыщает все ребра, асимптотика получается <tex>O(VE)</tex>.
+
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <tex>O(V + K)</tex>, где <tex>K</tex> - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного [[Блокирующий поток|блокирующего потока]] будет <tex>O(P)</tex>, где <tex>P</tex> — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за <tex>O(PV + PK)</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>.
+
<b>Замечание</b> Если в [[Схема алгоритма Диница|алгоритме Диница]] искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности алгоритма Эдмондса-Карпа <tex>(O(VE^2))</tex>.
  
 
==Алгоритм узкого места==
 
==Алгоритм узкого места==

Версия 23:06, 15 января 2011

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

Идея

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

Асимптотика

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

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

Идея

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

Асимптотика

Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за [math]O(V + K)[/math], где [math]K[/math] - число продвижения указателей. Учитывая, что всего запусков обхода в глубину в рамках поиска одного блокирующего потока будет [math]O(P)[/math], где [math]P[/math] — число рёбер, насыщенных этим блокирующим потоком, то весь алгоритм поиска блокирующего потока отработает за [math]O(PV + PK)[/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]ρ[/math]. Затем пускается поток величины [math]ρ[/math] из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.

Асимптотика

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

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

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

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

Источники