1632
правки
Изменения
м
Пусть дан граф <tex> G </tex> с целыми пропускными способностями: <tex> \forall(uКоличество необходимых увеличений путей, основанных на кратчайших путях, v) \in EG \colon c(uможет быть много больше количества увеличений,v) \in \mathbb{Z_+} </tex>основанных на путях с высокой пропускной способностью.<tex> U {|border="0" cellpadding="5" width=30% align= \max\limits_{(u, v) \in EG} c(u, v) </tex> — максимальная пропускная способностьcenter|[[Файл:Flow_scale_1. Запишем пропускную способность каждого ребра png|550px|thumb|center|Выбор дополняющих путей в двоичном виде. Тогда каждое число будет занимать <tex> \lfloor \log_2 U \rfloor + 1 = n + 1 </tex> битпорядке длины]]|[[Файл:Flow_scale_2.png|550px|thumb|center|Выбор пути с высокой пропускной способностью в первую очередь]]|}
Методом Форда-Фалкерсона находим поток В конце итерации с масштабом <tex> \Delta = 2^k </tex>, сеть <tex> f_0 G_{f_k} </tex> для графа может быть разбита на два непересекающихся множества <tex> G_0 A_k </tex> с урезанными пропускными способностями и <tex> \overline{A_k} </tex> c_0(uтак, v) = a_n(uчто остаточная пропускная способность каждого ребра, v) идущего из <tex> A_k </tex>.Добавим следующий бит и находим следующее приближение для графа в <tex> G_1 \overline{A_k} </tex> с новыми пропускными способностями , не превосходит масштаба <tex> \Delta </tex> c_1(u. То есть образуется [[Разрез, v) _лемма_о_потоке_через_разрез|разрез]] <tex> C_k = 2 a_n(u\langle A_k, v) + a_\overline{n - 1A_k}(u, v) - 2 f_0(u, v) \rangle </tex>.
После При этом, количество таких рёбер не превосходит <tex> n + 1 E </tex> итерации получим ответ к задаче.Значит, значение остаточного потока не может превосходить <tex> \Delta E = 2^k E </tex>.}}
Количество итераций — В ходе выполнения алгоритма масштаб <tex> \Delta </tex> принимает следующие значения: <tex> O(S = \{2^{\lfloor \log log_2 U) \rfloor}, \ldots, 2^k, \ldots, 2, 1, 0\} </tex>. Докажем, что сложность каждой итерации — Тогда <tex> |S| = O(E^2\log U) </tex>{{---}} количество итераций алгоритма.
На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| </tex>. Поиск каждого дополнительного пути требует Количество итераций алгоритма {{---}} <tex> O(E\log U) </tex> времени, а их значит, суммарное количество не больше <tex> V </tex>. Итоговая сложность первой итерации — увеличивающих путей {{---}} <tex> O(VE) E \leq O(E^2log U) </tex>.
rollbackEdits.php mass rollback
== Алгоритм ==Пусть дана [[Определение_сети,_потока#.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|definitionпоток]] по ним, а затем по всем остальным. Для этого воспользуемся масштабом <tex> \Delta </tex>. Изначально положим <tex> \Delta =2^{\lfloor \log_2 U \rfloor} </tex>.Алгоритм масштабирования потока — На каждой итерации в [[Дополняющая_сеть,_дополняющий_путь|дополняющей сети]] алгоритм поиска максимального потока путём регулирования находит [[Дополняющая_сеть,_дополняющий_путь|дополняющие пути]] с пропускной способности рёберспособностью не меньшей <tex> \Delta </tex> и увеличивает поток вдоль них.Этот алгоритм работает Уменьшив масштаб <tex> \Delta </tex> в предположении, что все пропускные способности рёбер целые<tex> 2 </tex> раза, так как они легко представимы в двоичном видепереходит к следующей итерации.}}
Очевидно, что при <tex> \Delta == Идея ==Идея алгоритма 1 </tex> алгоритм вырождается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по нималгоритм [[Алоритм_Эдмондса-Карпа|Эдмондса-Карпа]], а затем по всем остальнымвследствие чего является корректным.
== Оценка времени работы =={{Лемма|about=1|statement=Максимальный поток в сети <tex> c(uG </tex> ограничен сверху значением <tex> |f_k| + 2^k E </tex>, v) = \sum\limits_где <tex> |f_k| </tex> {{i = 0---}}^n a_i(u, v) значение потока при масштабе <tex> \times Delta = 2^n, a_i(u, v) \in \{0, 1\} k </tex>.|proof=[[Файл:Flow_scale_3.png|530px|thumb|right|Разрез <tex> C_k </tex>]]
{{Лемма|about=2|statement= Оценка сложности =Суммарное количество увеличивающих путей {{---}} <tex> O(E \log U) </tex>.|proof=На некоторой итерации алгоритма каждый дополняющий путь имеет пропускную способность не меньше <tex> 2^k </tex>.Дополняющий поток на предыдущем шаге ограничен значением <tex> 2^{k + 1} E </tex>. Следовательно, на каждой итерации количество дополняющих путей не превосходит <tex> 2E </tex>.}}
{{Утверждение
|statement=
Время работы алгоритма — {{---}} <tex> O(E^2 \log U) </tex>.
|proof=
Алгоритм [[Файл:Scaling.jpgОбход_в_ширину|250px|thumb|right|Разрез обхода в ширину]] находит каждый дополняющий путь за время <tex> \langle A, \overline{A} \rangle </tex>.]]Докажем оценку для второго шага O(для остальных доказательство аналогичноE).Граф <tex> G_{f_0} </tex> — несвязен. Пусть <tex> A </tex> — компонента связностиСледовательно, <tex> s \in A, t \in \overlineсуммарное время работы алгоритма {{A---}} </tex>. Тогда <tex> c_{0_{f_0}}O(A, E^2 \overline{A}log U) = 0 </tex>. Значит, в графе с пропускными способностями <tex> c_1 </tex>:<tex> \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 </tex>.}
== Псевдокод == '''function''' maxFlowByScaling(G: '''graph''', s: '''int''', t: '''int'''): '''int''' '''int''' flow = 0 <font color=darkgreen> // поток в сети </font> '''int''' scale = <tex> 2^{\langle A, lfloor\log_2U\overline{Arfloor} </tex> <font color=darkgreen> // текущий минимальный размер потока, который пытаемся пустить </font> '''while''' scale <tex> \rangle geqslant </tex> — разрез1 '''while''' в <tex> G_f </tex> существует увеличивающий путь <tex> p </tex> с пропускной способностью не меньше, чем scale '''int''' minCapacity = <tex>\min\{c(u, значитv) \colon(u, v) \in p\} </tex> <font color=darkgreen> // минимальная пропускная способность в увеличивающем пути </font> увеличить поток по рёбрам <tex> p </tex> на minCapacity обновить <tex> G_f </tex>}} flow = flow + minCapacity scale = scale / 2 '''return''' flow
== Псевдокод См. также == '''Capacity* [[Определение_сети,_потока|Определение сети, потока]]* [[Алоритм_Эдмондса-Scaling''' <tex> f \leftarrow 0 </tex> <tex> \Delta \leftarrow 2^{\lfloor \log_2 U \rfloor}</tex> '''while''' <tex> \Delta >0</tex>Карпа|Алоритм Эдмондса-Карпа]] '''do''' '''while''' в <tex>G_f</tex> существует <tex>s* [[Алгоритм_Форда-t</tex> путь с пропускной способностью большей <tex>\Delta</tex> '''do''' <tex>P\leftarrow</tex> путь с пропускной способностью большей <tex>\Delta</tex> <tex>\delta\leftarrow\min\{c_{ij}\colon(iФалкерсона,j)\in P\}</tex> увеличить поток по рёбрам <tex>P</tex> на <tex>\delta</tex> обновить <tex>G_f</tex> <tex>f\leftarrow f+\delta</tex> <tex>\Delta\leftarrow\Delta/2</tex>_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона]]
== Литература Источники информации ==
* [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://wwwlogic.cs-seminarpdmi.spbras.ru/reportsics/34talks/21stream.pdf ''Андрей Станкевич'': Задача о максимальном потоке]* [https://youtu.be/sEwp5ZAJJps?t=18m9s ''Андрей Станкевич'': Лекториум, дополнительные главы алгоритмов, лекция 12] [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о максимальном потоке]]
