Редактирование: Алгоритм поиска блокирующего потока в ациклической сети

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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)
+
dfs()
     '''if''' (flow == 0)  
+
    <tex>p \leftarrow [s];</tex> //путь <tex>p</tex>
      '''return''' 0
+
    <tex>v \leftarrow s</tex>; //текущая вершина и указатель на вершину первого неудалённого ребра
    '''if''' (<tex>v</tex> == <tex>t</tex>)
+
     if(нет пути из <tex>v</tex>)
      '''return''' flow
+
      if (<tex>v = s</tex>)
     '''for''' (<tex>u</tex> = ptr[<tex>v</tex>] '''to''' n)
+
          завершить алгоритм;
      '''if''' (<tex>vu \in E</tex>)
+
      else
        pushed = dfs(<tex>u</tex>, min(flow, c(<tex>vu</tex>) - f(<tex>vu</tex>)))
+
          удалить <tex>(uv)</tex> из <tex>V(G)</tex>; //<tex>uv</tex> - последнее ребро на пути <tex>p</tex>
        f(<tex>vu</tex>) += pushed
+
          удалить <tex>v</tex> из <tex>p</tex>;
        f(<tex>uv</tex>) -= pushed
+
     do
        '''return''' pushed
+
      //<tex>w</tex> - вершина смежная с <tex>v</tex>
      ptr[<tex>v</tex>]++
+
      <tex>p \leftarrow p+[w]</tex>;
     '''return''' 0
+
      <tex>v \leftarrow w;</tex>
 +
    while(<tex>w \ne t</tex>);
 +
   
 +
    <tex>\delta \leftarrow </tex>min(<tex>c(vw) - f(vw), (vw)\in p</tex>);
 +
    foreach <tex>(vw)\in p </tex>
 +
      <tex>f(vw)\leftarrow f(vw) + \delta;</tex> //увеличиваем поток вдоль пути <tex>p</tex>
 +
      <tex>if</tex> (ребро <tex>(vw)</tex> насыщено)
 +
          удалить <tex>(vw)</tex> из <tex>V(G);</tex>
 +
     dfs();
  
  '''main'''()
+
Если обход в глубину достигает стока, насыщается как минимум одно ребро, иначе как минимум один указатель продвигается вперед. Значит один запуск обхода в глубину работает за <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>.
    '''...'''
 
    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>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>p_{in}=\sum \limits_{u} c(u, v)</tex> и <tex>p_{out}=\sum \limits_{u} c(u, v)</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>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>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>.  
+
Повторим процесс отправки потока из вершин <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>.  
  
  
Строка 60: Строка 55:
 
       while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>)
 
       while (<tex>t</tex> достижима из <tex>s</tex> в <tex>L</tex>)
 
       {
 
       {
         найдём <tex>v</tex> с минимальной пропускной способностью <tex>g</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>;
Строка 70: Строка 65:
  
 
===Асимптотика===
 
===Асимптотика===
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <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> действий.
+
Если информация о входящих и исходящих дугах будет храниться в виде связных списков, то для того, чтобы пропустить поток, на каждой итерации будет выполнено <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 MAXimal :: algo :: Алгоритм Диница]
+
*[http://e-maxx.ru/algo/dinic#8 e-maxx Алгоритм Диница]
 
*[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 Оригинальная публикация алгоритма Малхотры — Кумара — Махешвари.]
 
  
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Задача о максимальном потоке]]
 
[[Категория:Задача о максимальном потоке]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)