Алгоритм "поднять-в-начало"

Материал из Викиконспекты
Версия от 00:45, 7 января 2013; Whiplash (обсуждение | вклад) (→‎Корректность алгоритма)
Перейти к: навигация, поиск

Алгоритм "поднять-в-начало" (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] — множество допустимых ребер.


Лемма (Допустимая сеть является ациклической):
Допустимая сеть [math]G_{f, h} = (V, E_{f, h})[/math] является ациклической.
Доказательство:
[math]\triangleright[/math]

Пусть в [math]G_{f, h}[/math] существует циклический путь [math]p = \left \langle v_0, v_1, \dots, v_k \right \rangle[/math], где [math]k \gt 0[/math].

[math] ~ ~ h[v_{i - 1}] = h[v_{i}] + 1[/math] для [math]i = 1, 2, \dots, k[/math], так как каждое ребро данного пути допустимое. Просуммировав равенства вдоль циклического пути, получаем:

[math]\sum \limits_{i = 1}^{k} h(v_{i - 1}) = \sum \limits_{i = 1}^{k} (h(v_{i}) + 1) = \sum \limits_{i = 1}^{k} h(v_{i}) + k[/math]

Вершина циклического пути [math]p[/math] встречается при суммировании по одному разу. Значит, [math]k = 0[/math], что противоречит первоначальному предположению. Следовательно, допустимая сеть является ациклической.
[math]\triangleleft[/math]


Лемма (Об изменении допустимой цепи с помощью операции проталкивания):
Если вершина [math]u[/math] переполнена и ребро [math](u, v)[/math] допустимое, то применяемая операция [math]push(u, v)[/math] не создает новые допустимые ребра, но может привести к тому, что ребро [math](u, v)[/math] станет недопустимым.
Доказательство:
[math]\triangleright[/math]

Из [math]u[/math] в [math]v[/math] можно протолкнуть поток, так как ребро [math](u, v)[/math] допустимое, по определению. Из-за того что [math]u[/math] — переполнена, вызываем операцию [math]push(u, v)[/math]. В результате выполнения операции может быть создано остаточное ребро [math](v, u)[/math]. Поскольку ребро [math](u, v)[/math] допустимое, то [math]h[v] = h[u] - 1[/math], а это значит, что ребро [math](v, u)[/math] не может стать допустимым.

Если выполненная операция [math]push(u, v)[/math] является насыщающим проталкиванием, то после ее выполнения [math]c_{f}(u, v) = 0[/math] и ребро [math](u, v)[/math] становится недопустимым.
[math]\triangleleft[/math]


Лемма (Об изменении допустимой цепи с помощью операции подъема):
Если вершина [math]u[/math] переполнена и не имеется допустимых ребер, выходящих из [math]u[/math], то применяется операция [math]relabel(u)[/math]. После подъема появляется по крайней мере одно допустимое ребро, выходящее из [math]u[/math], но нет допустимых ребер, входящих в [math]u[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим вершину [math]u[/math]. Если [math]u[/math] переполнена, то, согласно лемме (2), к ней может быть применима либо операция проталкивания, либо операция подъема. А так как не существует допустимых ребер для [math]u[/math], то протолкнуть поток не возможно, значит, применяется операция [math]relabel(u)[/math]. После данного подъема [math]h[u] = 1 + min \{ h[v]: (u, v) \in E_{f} \}[/math]. Значит, если [math]u[/math] — вершина указанного множества, в которой реализуется минимум, то [math](u, v)[/math] становится допустимым. А это значит, что после подъема существует, хотя бы одно, допустимое ребро, выходящее из [math]u[/math].

Пусть, после подъема существует такая вершина [math]u[/math], что ребро [math](v, u)[/math] допустимо. Тогда после подъема [math]h[v] = h[u] + 1[/math], а перед ним [math]h[v] \gt h[u] + 1[/math]. Но между вершинами, высоты которых отличаются более чем на 1, не существует остаточных ребер. Кроме того, подъем вершины не меняет остаточную сеть. Значит, ребро [math](v, u)[/math] не может находится в допустимой сети, так как оно не принадлежит остаточной сети.
[math]\triangleleft[/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) - f(u, v) > 0 and h[u] = h[v] + 1
                push(u, v)
            else
                current[u] = next[v]

Операция завершится только тогда, когда избыток [math]e(u)[/math] станет равным нулю, и ни подъем, ни перемещение указателя [math]current[u][/math] не влияет на значение [math]e(u)[/math].

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


Лемма (О применимости операции push):
Когда discharge вызывает в операцию [math]push(u, v)[/math], то для пары вершин [math](u, v)[/math] применима операция проталкивания.
Доказательство:
[math]\triangleright[/math]
Проверки операции discharge, сделанные до вызова операции проталкивания, гарантируют то, что операция [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]


Лемма (О применимости операции relabel):
Когда discharge вызывает в операцию [math]relabel(u)[/math], то для вершины [math]u[/math] применим подъем.
Доказательство:
[math]\triangleright[/math]

Из леммы об изменении допустимой цепи (для операции relabel) и условия [math]e(u) \gt 0[/math] следует, что для доказательства данной леммы необходимо показать, что все ребра, выходящие из [math]u[/math], являются недопустимыми.

Каждый проход операции discharge(u) начинается с головы списка [math]N[u][/math] и оканчивается, когда [math]current[u] = null[/math]. Именно тогда вызывается [math]relabel(u)[/math], и начинается новый проход. К концу прохода все ребра, выходящие из [math]u[/math], станут недопустимыми, так как из леммы об изменении допустимой цепи (для операции push) следует, что операции проталкивания не создают допустимых ребер. То есть любое допустимое ребро могло быть создано только в результате выполнения операции подъема. Но вершина [math]u[/math] не подвергается подъему во время прохода, а любая другая вершина [math]v[/math], для которой вызывалась операция подъема, во время данного прохода, не имеет после подъема допустимых ребер, что следует из леммы об изменении допустимой цепи (для операции relabel). Значит, в конце прохода все ребра, выходящие из [math]u[/math], останутся недопустимыми.
[math]\triangleleft[/math]

Алгоритм

Инициализируем предпоток и высоты, с помощью операции initializePreflow. Список [math]L[/math] — список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель [math]current[/math] каждой вершины [math]u[/math], чтобы он указывал на первую вершину в списке [math]u[/math].

Пройдем по списку [math]L[/math], разгружая вершины, начиная с первой вершины. И если операция discharge изменила высоту вершины, то перемещаем ее в начало списка [math]L[/math]. Передвинем указатель на следующую вершину списке [math]L[/math]. Если после разгрузки была изменена высота, то берем следующую вершину в новом списке [math]L[/math]. 

 relabelToFront(s, t)
     initializePreflow(s)
     L = V / {s, t}
     for u [math]\in[/math] V / {s, t}
         current[u] = head[N[u]]
     u = head[L]
     while u != null
         oldHeight = h[u]
         discharge(u)
         if h[u] > oldHeight
             передвинуть u в начало списка L
         u = nextVartex[u]

В приведенном псевдокоде предполагается, что для каждой вершины [math]u[/math] уже создан список [math]N[u][/math].

[math]nextVartex[u][/math] возвращает вершину, следующую за [math]u[/math] в списке [math]L[/math]. Если [math]u[/math] — последняя вершина в списке, то [math]nextVartex[u] = null[/math].

Инвариант цикла: "при каждом выполнении проверки условия вхождения в цикл while, список [math]L[/math] является топологическим упорядочением вершин допустимой сети [math]G_{f, h} = (V, E_{f, h})[/math], и ни одна вершина, стоящая в списке перед [math]u[/math], не имеет избыточного потока".

Корректность алгоритма

Для доказательства корректности алгоритма, то есть чтобы показать что операция [math]relabelToFront[/math] вычисляет поток, покажем, что она является реализацией универсального алгоритма проталкивания предпотока. Для начала, заметим, что она выполняет операции [math]push[/math] и [math]relabel[/math] только тогда, когда они применимы, следует из лемм о применимости операций push и relabel. Покажем, что когда операция [math]relabelToFront[/math] завершится, не применима ни одна основная операция. Для этого подробно рассмотрим операцию [math]relabelToFront[/math]:

  1. После вызова [math]initializePreflow[/math] [math]h[s] = |V|[/math] и [math]h[u] = 0[/math] для всех [math]u \in V \setminus {s}[/math]. Так как [math]|V| \ge 2[/math], то ни одно ребро не является допустимым. Значит, [math]E_{f, h} = \varnothing[/math] и любой порядок множества [math]V \setminus \{s, t\}[/math] является топологическим упорядочением [math]G_{f, h}[/math].
  2. Проверим, что топологическое упорядочение сохранится при проведении итераций цикла while. Для начала заметим, что сеть может изменится только из-за операций проталкивания и подъема. Из леммы об изменении допустимой цепи нам известно, что после операции проталкивания новые допустимые ребра не появляются, а это значит, что они могли появится только во время выполнения операции подъема. После того как для вершины [math]u[/math] применили операцию подъема, больше не существует допустимых ребер, входящих в [math]u[/math], но могут быть допустимые ребра, выходящие из нее. Таким образом, перемещая [math]u[/math] в начало списка [math]L[/math], все допустимые ребра, выходящие из [math]u[/math], удовлетворяют условию топологического упорядочения.
  3. Проверим, что ни одна вершина, предшествующая [math]u[/math] в списке [math]L[/math], не имеет избытка потока. Пусть вершина [math]u'[/math] — вершина [math]u[/math] на следующей итерации.
    1. Если [math]u[/math] подверглась подъему, то вершин предшествующих [math]u'[/math] на следующей итерации, кроме [math]u[/math], нет или если высота [math]u[/math] не изменилась, то там остались те же вершины, что и ранее. Так как [math]u[/math] подверглась разгрузке, то она не содержит избытка потока. Значит, если [math]u[/math] подверглась подъему в процессе разгрузки, то ни одна вершина, предшествующая [math]u'[/math], не содержит избытка потока.
    2. Если высота [math]u[/math] не поменялась во время разгрузки, то вершины, стоящие в списке [math]L[/math] перед ней, не получили избыток потока, так как [math]L[/math] топологически упорядочен все время в процессе разгрузки, поэтому каждая операция проталкивания продвигает поток только по вершинам дальше по списку. В этом случае ни одна вершина, предшествующая [math]u'[/math], также не имеет избытка потока.
  4. После завершения цикла [math]u = null[/math], поэтому избыток всех вершин равен [math]0[/math] (инвариант цикла). Значит, ни одна основная операция неприменима.

Оценка быстродействия

Теорема:
Время выполнения операции [math]relabelToFront[/math] для любой сети [math]G = (V, E)[/math] составляет [math]O(V^{3})[/math].
Доказательство:
[math]\triangleright[/math]

Пусть фаза — время между двумя последовательными операциями подъема. Так как всего, по лемме (6), выполняется [math]O(V^{2})[/math] подъемов, значит, в алгоритме всего [math]O(V^{2})[/math] фаз.

Если операция discharge не выполняет подъем, то следующий ее вызов происходит дальше по списку [math]L[/math] [math]([/math]длина [math]L[/math] меньше [math]|V|)[/math]. Если же подъем выполняется, то следующий вызов происходит уже в другой фазе алгоритма. Значит, каждая фаза содержит не более [math]|V|[/math] вызовов discharge.

Таким образом, цикл while процедуры [math]relabelToFront[/math] выполняет работу (без учета операций вызываемых в discharge), за [math]O(V^{3})[/math].

Оценим работу выполнения внутри операции discharge:

  1. Обновление указателя [math]current[u][/math] выполняется [math]O(deg(u))[/math] в том случае, когда вершина [math]u[/math] подвергается подъему. Значит, для всех вершин время составляет [math]O(V deg(u))[/math]. Следовательно, согласно лемме о рукопожатиях, время равно [math]O(VE)[/math].
  2. Пусть [math]u[/math] — произвольная вершина сети. Она может быть поднята не более [math]O(V)[/math] раз, время каждого подъема [math]O(deg(u))[/math]. Значит, время всех подъемов ограничивается [math]O(VE)[/math].
  3. Из леммы (8) следует, что количество насыщающих проталкиваний составляет [math]O(VE)[/math]. Ненасыщающее проталкивание уменьшает избыток до [math]0[/math], после чего разрядка останавливается. Следовательно, ненасыщающих проталкиваний не больше, чем вызовов discharge, то есть [math]O(V^{3})[/math].
Таким образом, время выполнения операции [math]relabelToFront[/math] составляет [math]O(V^{3} + VE)[/math], что эквивалентно [math]O(V^{3})[/math].
[math]\triangleleft[/math]

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_%22поднять-в-начало%22&oldid=28971»