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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 45: Строка 45:
 
Оценка времени работы остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общее время работы алгоритма — <tex> O(E^2 \log U) </tex>.  
 
Оценка времени работы остальных итераций доказывается аналогично второму случаю. Количество итераций — <tex> O(\log U) </tex>. Значит, общее время работы алгоритма — <tex> O(E^2 \log U) </tex>.  
 
}}
 
}}
 +
 +
== Псевдокод ==
 +
'''Max_Flow_By_Scaling(G,s,t)'''
 +
    <tex>f \leftarrow 0</tex>
 +
    <tex>\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}</tex>
 +
    '''while''' <tex>\Delta \geq 1</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>
 +
    '''return''' <tex>f</tex>
  
 
== Литература ==
 
== Литература ==

Версия 22:44, 28 февраля 2012

Алгоритм

Пусть дана сеть [math] G [/math], все ребра которой имеют целочисленную пропускную способность. Обозначим за [math] U [/math] максимальную пропускную способность: [math] U = \max\limits_{(u, v) \in E} c(u, v) [/math].

Идея алгоритма заключается в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным.

Если записать пропускную способность любого ребра в двоичном виде, то длина полученной битовой последовательности не будет превышать [math] \lfloor \log_2 U \rfloor + 1 = n + 1 [/math] бит, а значение пропускной способности определяется формулой: [math] c(u, v) = \sum\limits_{i = 0}^n a_i(u, v) \times 2^i, a_i(u, v) \in \{0, 1\} [/math].

Методом Форда-Фалкерсона находим поток [math] f_0 [/math] для сети [math] G_0 [/math] с урезанными пропускными способностями [math] c_0(u, v) = a_n(u, v) [/math]. Добавим следующий бит и находим следующее приближение для графа [math] G_1 [/math] с новыми пропускными способностями [math] c_1(u, v) = 2 a_n(u, v) + a_{n - 1}(u, v) - 2 f_0(u, v) [/math].

После [math] n + 1 [/math] итерации получим ответ к задаче, так как [math] c_{n}(u, v) = c(u, v) [/math].

Оценка времени работы

Утверждение:
Время работы алгоритма — [math] O(E^2 \log U) [/math].
[math]\triangleright[/math]

Докажем, что время работы каждой итерации — [math] O(E^2) [/math].

Лемма:
Время работы первой итерации алгоритма — [math] O(E^2) [/math].
Доказательство:
[math]\triangleright[/math]
На первом шаге ребра имеют пропускную способность [math] 1 [/math]. Значит, [math] |f_0| \leq V [/math]. Поиск каждого дополнительного пути требует [math] O(E) [/math] времени, а их количество не больше [math] V [/math]. Итоговое время работы первой итерации — [math] O(VE) \leq O(E^2) [/math].
[math]\triangleleft[/math]
Лемма:
Время работы второй итерации алгоритма — [math] O(E^2) [/math].
Доказательство:
[math]\triangleright[/math]
Разрез [math] \langle A, \overline{A} \rangle [/math].

Пусть вершина [math] s [/math]источник графа, вершина [math] t [/math]сток. Дополняющая сеть [math] G_{0_{f_0}} [/math]несвязна. Обозначим за [math] A [/math] компоненту связности графа, содержащую вершину [math] s [/math]. Тогда [math] t \notin A [/math]. Источник и сток лежат в разных компонентах связности, значит [math] c_{0_{f_0}}(A, \overline{A}) = c_0(A, \overline{A}) - f_0(A, \overline{A}) = 0 [/math].

Следовательно, в сети [math] G_1 [/math] с пропускными способностями [math] c_1 [/math]: [math] \forall u \in A, v \in \overline{A} \colon c_1(u, v) \leq 1 [/math].

Рассмотрим максимальный поток [math] f'_1 [/math] в сети [math] G_1 [/math]. [math] \langle A, \overline{A} \rangle [/math]разрез, значит: [math] |f'_1| = f'_1(A, \overline{A}) \leq c(A, \overline{A}) \leq E, f_1 = f_0 + f'_1 [/math].

Пропускная способность каждого дополняющего пути не меньше [math] 1 [/math], а поиск каждого занимает [math] O(E) [/math] времени. Значит, итоговое время работы — [math] O(E^2) [/math].
[math]\triangleleft[/math]
Оценка времени работы остальных итераций доказывается аналогично второму случаю. Количество итераций — [math] O(\log U) [/math]. Значит, общее время работы алгоритма — [math] O(E^2 \log U) [/math].
[math]\triangleleft[/math]

Псевдокод

Max_Flow_By_Scaling(G,s,t)
    [math]f \leftarrow 0[/math]
    [math]\Delta \leftarrow 2^{\lfloor\log_2U\rfloor}[/math]
    while [math]\Delta \geq 1[/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]
    return [math]f[/math]

Литература