Алгоритм масштабирования потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 2: Строка 2:
 
Этот алгоритм работает в предположении, что все пропускные способности рёбер целые.
 
Этот алгоритм работает в предположении, что все пропускные способности рёбер целые.
  
== Суть ==
+
== Идея ==
Пусть существует граф <tex>G</tex> и <tex>\forall (u,v)\in E\colon c_{(u,v)}\in\mathbb N</tex>. Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем по всем остальным. Пусть <tex>U</tex> - максимальная пропускная способность. Введём параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше, чем <tex>\Delta</tex>, и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым значением параметра. При значении <tex>\Delta</tex>, равном единице, данный алгоритм становится идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса — Карпа]]. Из этого следует, что алгоритм корректен.
+
Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем по всем остальным. Пусть <tex>U</tex> - максимальная пропускная способность. Введём параметр <tex>\Delta = 2^{\lfloor\log_2U\rfloor}</tex>. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше, чем <tex>\Delta</tex>, и увеличивать поток вдоль этих путей. В конце шага будем уменьшать <tex>\Delta</tex> в два раза, и на следующем шаге будем искать увеличивающий путь с новым значением параметра. При значении <tex>\Delta</tex>, равном единице, данный алгоритм становится идентичен [[Алоритм_Эдмондса-Карпа | алгоритму Эдмондса — Карпа]]. Из этого следует, что алгоритм корректен.
 +
 
 +
Пусть <tex> G </tex> — граф, <tex> \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+}, U = \max\limits_{(u, v) \in EG} c(u, v) </tex> — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать <tex> \lceil \log_2 U \rceil = n </tex> бит.
 +
 
 +
<tex> c(u, v) = \sum\limits_{i = 0}^{n - 1} a_i(u, v) 2^n, a_i(u, v) \in {0, 1} </tex>
  
 
== Оценка сложности ==
 
== Оценка сложности ==
Строка 11: Строка 15:
 
== Псевдокод ==
 
== Псевдокод ==
 
  '''Capacity-Scaling'''
 
  '''Capacity-Scaling'''
     <tex>f\leftarrow 0</tex>
+
     <tex> f \leftarrow 0 </tex>
     <tex>\Delta\leftarrow 2^{\lfloor\log_2U\rfloor}</tex>
+
     <tex> \Delta \leftarrow 2^{\lfloor \log_2 U \rfloor}</tex>
     '''while''' <tex>\Delta>0</tex>
+
     '''while''' <tex> \Delta >0</tex>
 
         '''do''' '''while''' в <tex>G_f</tex> существует <tex>s-t</tex> путь с пропускной способностью большей <tex>\Delta</tex>
 
         '''do''' '''while''' в <tex>G_f</tex> существует <tex>s-t</tex> путь с пропускной способностью большей <tex>\Delta</tex>
 
                 '''do''' <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>\Delta</tex>
 
                 '''do''' <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>\Delta</tex>

Версия 22:09, 18 декабря 2011

Алгоритм масштабирования потока — алгоритм поиска максимального потока путём регулирования пропускной способности рёбер. Этот алгоритм работает в предположении, что все пропускные способности рёбер целые.

Идея

Суть алгоритма в нахождении сперва путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток по этим путям, а затем по всем остальным. Пусть [math]U[/math] - максимальная пропускная способность. Введём параметр [math]\Delta = 2^{\lfloor\log_2U\rfloor}[/math]. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше, чем [math]\Delta[/math], и увеличивать поток вдоль этих путей. В конце шага будем уменьшать [math]\Delta[/math] в два раза, и на следующем шаге будем искать увеличивающий путь с новым значением параметра. При значении [math]\Delta[/math], равном единице, данный алгоритм становится идентичен алгоритму Эдмондса — Карпа. Из этого следует, что алгоритм корректен.

Пусть [math] G [/math] — граф, [math] \forall(u, v) \in EG \colon c(u,v) \in \mathbb{Z_+}, U = \max\limits_{(u, v) \in EG} c(u, v) [/math] — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать [math] \lceil \log_2 U \rceil = n [/math] бит.

[math] c(u, v) = \sum\limits_{i = 0}^{n - 1} a_i(u, v) 2^n, a_i(u, v) \in {0, 1} [/math]

Оценка сложности

Scaling.jpg

На каждом шаге алгоритм выполняет в худшем случае [math]O(E)[/math] увеличений потока. Докажем это. Пусть [math]\Delta = 2^k[/math]. В конце шага множество вершин графа можно разбить на две части: [math]A_k[/math] и [math]\overline{A_k}[/math]. Все рёбра, выходящие из [math]A_k[/math], имеют остаточную пропускную способность менее [math]2^k[/math]. Наибольшее количество рёбер между [math]A_k[/math] и [math]\overline{A_k}[/math] равно [math]E[/math]. Следовательно, остаточный поток (поток, который может быть получен на оставшихся шагах) на фазе с текущим значением [math]k[/math] максимально составляет [math]2^kE[/math]. Каждый увеличивающий путь при данном [math]k[/math] имеет пропускную способность как минимум [math]2^k[/math]. На предыдущем шаге, с масштабом [math]k+1[/math], остаточный поток ограничен [math]2^{k+1}E[/math]. Значит максимальное число появившихся увеличивающих путей равно [math]2E[/math]. Увеличивающий путь можно найти за [math]O(E)[/math], используя BFS. Количество шагов [math]O(\log_2U)[/math]. Итоговая сложность [math]O(E^2\log_2U)[/math].

Псевдокод

Capacity-Scaling
    [math] f \leftarrow 0 [/math]
    [math] \Delta \leftarrow 2^{\lfloor \log_2 U \rfloor}[/math]
    while [math] \Delta \gt 0[/math]
        do while в [math]G_f[/math] существует [math]s-t[/math] путь с пропускной способностью большей [math]\Delta[/math]
               do [math]P\leftarrow[/math] путь с пропускной способностью большей [math]\Delta[/math]
                  [math]\delta\leftarrow\min\{c_{ij}\colon(i,j)\in P\}[/math]
                  увеличить поток по рёбрам [math]P[/math] на [math]\delta[/math]
                  обновить [math]G_f[/math]
                  [math]f\leftarrow f+\delta[/math]
           [math]\Delta\leftarrow\Delta/2[/math]

Литература