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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
м (rollbackEdits.php mass rollback)
 
(не показаны 153 промежуточные версии 10 участников)
Строка 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>dfs</tex>, каждый путь находится за <tex>O(E)</tex>, где <tex>E</tex> — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет <tex>O(E)</tex> путей. Итого общая асимптотика составляет <tex>O(E^2)</tex>.
Используя <tex>dfs</tex> каждый путь находится за <tex>O(E)</tex>. Поскольку каждый пусть насыщает как минимум одно ребро, всего будет <tex>O(E)</tex> путей. Итого общая асимптотика составляет <tex>O(E^2)</tex>.
 
  
 
==Удаляющий обход==
 
==Удаляющий обход==
 +
Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока <tex>t</tex>. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.
 +
 +
  '''int''' dfs('''int''' <tex>v</tex>, '''int''' flow)
 +
    '''if''' (flow == 0)
 +
      '''return''' 0
 +
    '''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)
 +
 +
 +
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <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>s</tex> в <tex>t</tex>, но применяется следующая оптимизация: в процессе обхода в глубину удаляются все ребра, вдоль которых нельзя дойти до стока. То есть, если для текущей вершины <tex>v</tex> <tex>dfs(v) = false</tex>, нужно удалить из графа эту вершину и все инцидентные ей ребра. С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину.
+
Для каждой вершины  вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее запускаем цикл, на каждой итерации которого определяем вершину <tex>v</tex> с минимальным потенциалом <tex>p</tex>. Затем пускается поток величины <tex>p</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(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>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>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>.  
  
<b>Замечание</b> Если в [[Схема алгоритма Диница|алгоритме Диница]] искать блокирующий поток удаляющим обходом, то его эффективность составит <tex>O(V^2E)</tex>, что уже лучше эффективности алгоритма Эдмондса-Карпа <tex>(O(VE^2))</tex>.
 
  
==Алгоритм узкого места==
+
MPM algorithm(<tex>s, t</tex>)
===Идея===
+
{
Для каждой вершины  вводится потенциал потока, равный максимальному дополнительному потоку, который может пройти через эту вершину. Далее следует цикл. На каждой его итерации определяется вершина <tex>r</tex> с минимальным потенциалом <tex>ρ</tex>. Затем пускается поток величины <tex>ρ</tex> из истока в сток, проходящий через эту вершину. При этом если остаточная пропускная способность ребра равна нулю, то это ребро удаляется. Также, удаляются все вершины, у которых не остаётся ни одного входящего и/или ни одного выходящего ребра. При удалении вершины все смежные ребра удаляются.
+
    foreach <tex>(uv) \in E</tex>
 +
      <tex>f(uv) \leftarrow 0 </tex>;
 +
    Вычисляем остаточную сеть <tex>R</tex>;
 +
    Найдём вспомогательный граф <tex>L</tex> для <tex>R</tex>;
 +
    while (<tex>t \in L</tex>)
 +
    {
 +
      while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>)
 +
      {
 +
        найдём <tex>v</tex> с минимальной пропускной способностью <tex>g</tex>;
 +
        проталкиваем <tex>g</tex> единиц потока из <tex>v</tex> в <tex>t</tex>;
 +
        проталкиваем <tex>g</tex> единиц потока из <tex>s</tex> в <tex>v</tex>;
 +
        изменяем <tex>f</tex>, <tex>L</tex> и <tex>R</tex>;
 +
      }
 +
      вычисляем новый вспомогательный граф <tex>L</tex> из <tex>R</tex>;
 +
    }
 +
}
  
 
===Асимптотика===
 
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(V + E_i)</tex> действий, где <tex>V</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых ребер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum_i{O(V+E_i)} = O(V^2)</tex> действий.
+
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <tex>O(K + E_i)</tex> действий, где <tex>K = O(V)</tex> соответствует числу рёбер, для которых остаточная пропускная способность уменьшилась, но осталась положительной, а <tex>E_i</tex> — числу удалённых рёбер. Таким образом, для поиска блокирующего потока будет выполнено <tex>\sum\limits_i{O(K+E_i)} = O(K^2)</tex> действий.
 +
 
 +
== См. также ==
 +
* [[Блокирующий поток]]
 +
* [[Схема алгоритма Диница]]
  
<b>Замечание</b> Алгоритм Малхотры — Кумара — Махешвари для поиска блокирующего потока использует алгоритм узкого места.
+
==Источники информации==
 +
* [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://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 Оригинальная публикация алгоритма Малхотры — Кумара — Махешвари.]
  
==Волновой алгоритм==
 
Используя предпотоки, позволяет найти блокирующий поток за <tex>O(V^2)</tex>. Модификация алгоритма Диница, основанная на этом алгоритме, называется алгоритмом Карзанова.
 
  
==Источники==
+
[[Категория:Алгоритмы и структуры данных]]
* http://ru.wikipedia.org
+
[[Категория:Задача о максимальном потоке]]
* http://e-maxx.ru
 
* http://algolist.manual.ru
 

Текущая версия на 19:07, 4 сентября 2022

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

Идея заключается в том, чтобы по одному находить пути из истока [math]s[/math] в сток [math]t[/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]E[/math] — число рёбер в графе. Поскольку каждый путь насыщает как минимум одно ребро, всего будет [math]O(E)[/math] путей. Итого общая асимптотика составляет [math]O(E^2)[/math].

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

Аналогично предыдущей идее, однако будем удалять в процессе обхода в глубину из графа все рёбра, вдоль которых не получится дойти до стока [math]t[/math]. Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое не удалённое ребро, и увеличивать этот указатель в цикле внутри обхода в глубину. Корректность при этом сохраняется согласно предыдущему пункту.

 int dfs(int [math]v[/math], int flow) 
   if (flow == 0) 
     return 0
   if ([math]v[/math] == [math]t[/math])
     return flow
   for ([math]u[/math] = ptr[[math]v[/math]] to n)
     if ([math]vu \in E[/math])
       pushed = dfs([math]u[/math], min(flow, c([math]vu[/math]) - f([math]vu[/math])))
       f([math]vu[/math]) += pushed
       f([math]uv[/math]) -= pushed
       return pushed
     ptr[[math]v[/math]]++
   return 0
 main()
   ...
   flow = 0
   for (int i = 1 to n)
     ptr[i] = 0
   do
     pushed = dfs([math]s[/math], [math]\infty[/math])
     flow += pushed
   while (pushed > 0)


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

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

  • Для каждой вершины [math]v[/math] вычислим входящий и исходящий потенциал: [math]p_{in}=\sum \limits_{u} c(u, v)[/math] и [math]p_{out}=\sum \limits_{u} c(v, u)[/math]. Пусть [math]p_{in}(s)=\infty[/math] и [math]p_{out}(t)=\infty[/math]. Определим потенциал или пропускную способность вершины в сети [math]p(v)=min(p_{in}(v), p_{out}(v))[/math]. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через неё проходить. Ясно, что через вершины с [math]p(v)=0[/math] поток проходить не может. Следовательно, их можно удалить из вспомогательной сети. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удалёнными. Если в результате появятся новые вершины с [math]p(v)=0[/math], удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с [math]p(v)\ne0[/math].
  • После этого приступим к построению блокирующего потока. Пусть вершина [math]v[/math] принадлежит [math]k[/math]-ому слою и [math]p(v)=min (p(w), w \in L_k)[/math], где [math]L_k[/math][math]k[/math]-й слой. Протолкнем [math]p(v)[/math] единиц потока из вершины [math]v[/math] в смежные с ней вершины по исходящим дугам с остаточной пропускной способностью [math]c_f \ne 0[/math]. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины [math]v[/math]) проталкиваемый поток соберется в вершинах [math](k+1)[/math]-го слоя.
  • Повторим процесс отправки потока из вершин [math](k+1)[/math]-го слоя, содержащих избыток потока, в смежные им вершины [math](k+2)[/math]-го слоя. И так до тех пор, пока весь поток не соберется в последнем слое, в котором содержится только сток [math]t[/math], ибо все остальные вершины, ранее ему принадлежащие, были удалены, поскольку их потенциалы нулевые. Следовательно, весь поток величины [math]p(v)[/math], отправленный из вершины [math]v[/math], где [math]p(v)[/math] - минимальный полностью соберется в [math]t[/math].
  • На втором этапе вновь, начиная с вершины [math]v[/math], осуществляется подвод потока уже по входящим дугам. В результате на первом шаге недостаток потока переадресуется к узлам [math](k-1)[/math]-го слоя, затем [math](k-2)[/math]-го. И так до тех пор, пока весь поток величины [math]p(v)[/math], отправленный в вершину [math]v[/math], где [math]p(v)[/math] - минимальный, не соберется в истоке [math]s[/math]. Таким образом, поток и во вспомогательной и в основной сети увеличится на величину [math]p[/math].


MPM algorithm([math]s, t[/math])
{
   foreach [math](uv) \in E[/math]
     [math]f(uv) \leftarrow 0 [/math];
   Вычисляем остаточную сеть [math]R[/math];
   Найдём вспомогательный граф [math]L[/math] для [math]R[/math];
   while ([math]t \in L[/math])
   {
     while ([math]t[/math] достижима из [math]s[/math] в [math]L[/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]L[/math] из [math]R[/math];
   }
}

Асимптотика

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

См. также

Источники информации