Алгоритм "поднять-в-начало" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Операция разгрузки (discharge))
м
Строка 1: Строка 1:
 
'''Алгоритм "поднять-в-начало" (relabel-to-front)''' основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
 
'''Алгоритм "поднять-в-начало" (relabel-to-front)''' основан на [[Метод проталкивания предпотока|методе проталкивание предпотока]], но из-за тщательного выбора порядка выполнения операций [[Метод проталкивания предпотока#Проталкивание (push)|проталкивания]] и [[Метод проталкивания предпотока#Подъем (relabel)|подъема]], время выполнения данного алгоритма составляет <tex>O(V^{3})</tex>, что асимптотически не хуже, чем <tex>O(V^{2}E)</tex>.
  
== Определения ==
+
== Допустимые ребра ==
 
<tex>G = (V, E)</tex> - [[Определение сети, потока#Определение сети|сеть]] с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> - [[Метод проталкивания предпотока#Определения|предпоток]] в <tex>G</tex>, <tex>h</tex> - [[Метод проталкивания предпотока#Определения|функция высоты]].
 
<tex>G = (V, E)</tex> - [[Определение сети, потока#Определение сети|сеть]] с истоком <tex>s</tex> и стоком <tex>t</tex>, <tex>f</tex> - [[Метод проталкивания предпотока#Определения|предпоток]] в <tex>G</tex>, <tex>h</tex> - [[Метод проталкивания предпотока#Определения|функция высоты]].
 
{{Определение
 
{{Определение

Версия 23:37, 26 декабря 2012

Алгоритм "поднять-в-начало" (relabel-to-front) основан на методе проталкивание предпотока, но из-за тщательного выбора порядка выполнения операций проталкивания и подъема, время выполнения данного алгоритма составляет [math]O(V^{3})[/math], что асимптотически не хуже, чем [math]O(V^{2}E)[/math].

Допустимые ребра

[math]G = (V, E)[/math] - сеть с истоком [math]s[/math] и стоком [math]t[/math], [math]f[/math] - предпоток в [math]G[/math], [math]h[/math] - функция высоты.

Определение:
Допустимое ребро (admissible edge) - ребро [math]uv[/math], у которого [math]c_{f}(u, v) \gt 0[/math] и [math]h(u) = h(v) + 1[/math]. В противном случае [math]uv[/math] называется недопустимым (inadmissible).


Определение:
Допустимая сеть (admissible network) - сеть [math]G_{f, h} = (V, E_{f, h})[/math], где [math]E_{f, h}[/math] - множество допустимых ребер.


Идея

Операция разгрузки (discharge)

Разгрузка (discharge) - операция, которая применяется к переполненной вершине [math]u[/math], для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая [math]u[/math], делая недопустимые ребра, выходящие из вершины [math]u[/math], допустимыми.

Будем хранить для каждой вершины [math]u[/math] список [math]N[u][/math] (список вершин смежных с ней). То есть список [math]N[u][/math] содержит каждую вершину [math]v[/math] такую, что в сети [math]G = (V, E) ~ (u, v) \in E[/math] или [math](v, u) \in E[/math].

На первую вершину в списке указывает указатель [math]head[N[u]][/math]. Для перехода к следующей вершине в списке за [math]w[/math], поддерживается указатель [math]next[w][/math]. Он равен [math]null[/math] если [math]w[/math] - последняя вершина в списке.

Для каждой вершины [math]u[/math] указатель [math]current[u][/math] - указатель на текущую вершину списка. Изначально [math]current[u] = head[N[u]][/math].

discharge(u)
    while e[u] > 0
        v = current[u]
        if v = null
            relabel(u)
            current[u] = head[N[u]]
        else
            if c(u, v) > 0 and h[u] = h[v] + 1
                push(u, v)
            else
                current[u] = next[v]

Докажем то, что когда операция discharge вызывает операции push и relable, эти операции применимы.

Лемма:
Когда операция [math]discharge[/math] вызывает в операцию [math]push(u, v)[/math], то для пары вершин [math](u, v)[/math] применима операция проталкивания.
Доказательство:
[math]\triangleright[/math]
Проверки операции [math]discharge[/math], сделанные до вызова операции проталкивания, гарантируют то, что операция [math]push[/math] будет вызвана только тогда, когда она применима. То есть [math]e(u) \gt 0[/math], [math]c_{f}(u, v) \gt 0[/math] и [math]h(u) = h(v) + 1[/math].
[math]\triangleleft[/math]
Лемма:
Когда операция [math]discharge[/math] вызывает в операцию [math]relabel(u)[/math], то для вершины [math]u[/math] применим подъем.

Схема алгоритма

Анализ

Источники