Изменения

== Алгоритм масштабирования потока - алгоритм поиска максимального потока путем регулирования пропускной способности ребер==Пусть дана [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|сеть]] <tex> G </tex>, все рёбра которой имеют целочисленную [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|пропускную способность]]. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v) </tex>.

Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B0|поток]] по ним, а затем по всем остальным. Для этого воспользуемся масштабом <tex> \Delta </tex>. Изначально положим <tex> \Delta == Суть ==2^{\lfloor \log_2 U \rfloor} </tex>.

Этот На каждой итерации в [[Дополняющая_сеть,_дополняющий_путь|дополняющей сети]] алгоритм работает в предположениинаходит [[Дополняющая_сеть, что все пропускные способности ребер целые_дополняющий_путь|дополняющие пути]] с пропускной способностью не меньшей <tex> \Delta </tex> и увеличивает поток вдоль них. Пусть Уменьшив масштаб <tex>U\Delta </tex> - максимальная пропускная способность. Тогда запишем пропускную способность каждого ребра в двоичной записи (для каждого ребра отведем <tex>n+1=\lfloor\log U\rfloor+12 </tex>). Занумеруем биты с младшего (0-ой) по старший (n-ный)раза, переходит к следующей итерации. Тогда

Очевидно, что при <tex>\forall (u,v)\in E:c(u,v)Delta =2^n*a_n(u,v)+...+2*a_1(u,v)+a_0(u,v); a_i(u,v)\in\{0,1\}</tex>алгоритм вырождается в алгоритм [[Алоритм_Эдмондса-Карпа|Эдмондса-Карпа]], вследствие чего является корректным.

Будем решать задачу методом Форда-Фалкерсона сначала для графа с урезанными пропускными способностями <tex>c_0(uКоличество необходимых увеличений путей,v):=a_n(uоснованных на кратчайших путях,v)</tex>. Решив ее и получив поток <tex>f_0</tex>может быть много больше количества увеличений, добавим следующий бит и вычтем грубое приближениеоснованных на путях с высокой пропускной способностью. То есть <tex>\forall (u,v)\in E{|border="0" cellpadding="5" width=30% align=center|[[Файл:c_1(u,v)Flow_scale_1.png|550px|thumb|center|Выбор дополняющих путей в порядке длины]]|[[Файл:=2*a_n(u,v)+a_{n-1Flow_scale_2.png|550px|thumb|center|Выбор пути с высокой пропускной способностью в первую очередь]]|}(u,v)-2*f_0(u,v)</tex>. Далее наше приближение становится точнее и точнее, пока не станет решением для исходной задачи.

== Оценка сложности времени работы =={{Лемма|about=1|statement=Максимальный поток в сети <tex> G </tex> ограничен сверху значением <tex> |f_k| + 2^k E </tex>, где <tex> |f_k| </tex> {{---}} значение потока при масштабе <tex> \Delta = 2^k </tex>.|proof=[[Файл:Flow_scale_3.png|530px|thumb|right|Разрез <tex> C_k </tex>]]

Сложность этого алгоритма В конце итерации с масштабом <tex>O(E\Delta = 2^2k </tex>, сеть <tex> G_{f_k} </tex> может быть разбита на два непересекающихся множества <tex> A_k </tex> и <tex> \overline{A_k} </tex> так, что остаточная пропускная способность каждого ребра, идущего из <tex> A_k </tex> в <tex> \log U)overline{A_k} </tex>, где не превосходит масштаба <tex>\log UDelta </tex> - количество итераций. ДокажемТо есть образуется [[Разрез, что сложность каждой итерации _лемма_о_потоке_через_разрез|разрез]] <tex>O(E^2)C_k = \langle A_k, \overline{A_k} \rangle </tex>.

На первой итерации мы имеем только ребра веса 1. Это значитПри этом, что <tex>|f|\le V</tex>. Значит количество итераций (дополняющих путей) таких рёбер не превосходит <tex>V</tex>, поиск доп. пути занимает <tex>O(E)</tex>. Получаем сложность Значит, значение остаточного потока не может превосходить <tex>O(VE)\le O(Delta E= 2^2)k E </tex>.}}

Теперь рассмотрим переход ко второй {{Лемма|about=2|statement=Суммарное количество увеличивающих путей {{---}} <tex> O(E \log U) </tex>.|proof=На некоторой итерацииалгоритма каждый дополняющий путь имеет пропускную способность не меньше <tex> 2^k </tex>. Граф Дополняющий поток на предыдущем шаге ограничен значением <tex>G_2^{f_0k + 1}E </tex> несвязен. Рассмотрим разрез Следовательно, на каждой итерации количество дополняющих путей не превосходит <tex>(S,T)2E </tex>, где .}}{{Утверждение|statement=Время работы алгоритма {{---}} <tex>SO(E^2 \log U) </tex> и .|proof=В ходе выполнения алгоритма масштаб <tex>T\Delta </tex> - компоненты связности. принимает следующие значения: <tex>(c_0)_S = \{2^{f_0\lfloor \log_2 U \rfloor}(S,T)=\ldots, 2^k, \ldots, 2, 1, 0\} </tex>. Значит в новом графе с пропускными способностями Тогда <tex>c_1|S| = O(\log U) </tex>: {{---}} количество итераций алгоритма. Количество итераций алгоритма {{---}} <tex>O(\forall u\in Slog U) </tex>, значит, vсуммарное количество увеличивающих путей {{---}} <tex> O(E \in T:c_1(u,vlog U)\le1</tex>. Так как  Алгоритм [[Обход_в_ширину|обхода в ширину]] находит каждый дополняющий путь за время <tex>O(S,TE)</tex> . Следовательно, суммарное время работы алгоритма {{-- разрез, то -}} <tex> O(E^2 \log U) </tex>|f.}} == Псевдокод == '''function''_1|=f'_1maxFlowByScaling(SG: '''graph''', s: '''int''',Tt: '''int'''): '''int''' '''int''' flow = 0 <font color=darkgreen> // поток в сети </font> '''int''' scale = <tex>2^{\le c(S,T)lfloor\log_2U\le Erfloor}</tex>. Здесь <font color=darkgreen> // текущий минимальный размер потока, который пытаемся пустить </font> '''while''' scale <tex>f'_1\geqslant </tex> - максимальный поток 1 '''while''' в <tex>G_1G_f </tex> с пропускными способностями существует увеличивающий путь <tex>c_1p </tex>с пропускной способностью не меньше, а чем scale '''int''' minCapacity = <tex>f_1=f_0+f'_1\min\{c(u, v) \colon(u, v) \in p\} </tex>. Так как <font color=darkgreen> // минимальная пропускная способность каждого дополняющего в увеличивающем пути не меньше 1, мы получили оценку </font> увеличить поток по рёбрам <tex> p </tex> на количество итераций. Дополняющий путь же мы можем найти за minCapacity обновить <tex>O(E)G_f </tex> flow = flow + minCapacity scale = scale / 2 '''return''' flow == См. также ==* [[Определение_сети,_потока|Определение сети, потока]]* [[Алоритм_Эдмондса-Карпа|Алоритм Эдмондса-Карпа]]* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона]] == Источники информации ==* [http://www.csd.uwo.ca/~yuri/Papers/iccv07_cap_scaling.pdf ''Olivier Juan, Yuri Boikov'': Capacity Scaling for Graph Cuts in Vision]* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited Algorithm Tutorials. Maximum Flow: Augmenting Path Algorithms Comparison]* [http://logic.pdmi.ras.ru/ics/talks/21stream.pdf ''Андрей Станкевич'': Задача о максимальном потоке]* [https://youtu.be/sEwp5ZAJJps?t=18m9s ''Андрей Станкевич'': Лекториум, дополнительные главы алгоритмов, лекция 12] [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о максимальном потоке]]