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

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

Версия 22:26, 15 января 2011

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

Суть

Пусть есть граф [math]G[/math], [math]\forall (u,v)\in E\colon u_{(u,v)}\in\mathbb N[/math]. Суть алгоритма в нахождении сначала путей с высокой пропускной способностью, чтобы сразу сильно увеличивать поток. Пусть [math]U[/math] - максимальная пропускная способность. Введем параметр [math]\Delta = 2^{\lfloor\log_2U\rfloor}[/math]. На каждом шаге будем искать в остаточном графе увеличивающие пути с пропускной способностью не меньше [math]\Delta[/math] и увеличивать поток вдоль этих путей. В конце шага будем уменьшать [math]\Delta[/math] в два раза, и на следующем шаге будем искать увеличивающий путь с новым [math]\Delta[/math]. При [math]\Delta == 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_2U\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]

Литература