Кружок обучения мастерству программирования при СПбГУ

Лекции группы A0 - Лекция 07 - Семинар по Preflow-Push (Юра Землянский, Коля Мальковский)

Краткий план лекции на тему "Семинар по Preflow-Push"

1. Определения
2. Основные Леммы (вытекают из инварианта), основные Операции
3. Оценки на количества элементарных операций
4. Алгоритмы PreflowPush и MoveToFront
5. Оптимизации [High-Level, Global Relabeling, P2R, Two Phase]
6. СНМ и его использование
7. Offline методы в геометрии

Полный план лекции

1. Определения
1. предпоток, избыток e[v], активная вершина
2. проталкивание (насыщенное, ненасыщенное)
3. высотная функция, инвариант h[v] <= h[w] + 1 для ненасыщенного ребра v --> w
2. Основные Леммы (вытекают из инварианта), основные Операции
1. Из s нет дополняющего пути в t.
2. Операция Push по ребрам вида h[v] = h[w] + 1 (насыщенный, ненасыщенный)
3. Операция ReLabel (подъем)
4. Операция DisCharge (e[v] > 0 => Push down... iff can not ReLabel)
5. e[v] > 0 => существует путь в исток
6. Высоты вершин не более 2n-1 (т.к. вершина поднимается только если e[v] > 0, а тогда сущ путь в исток)
7. Алгоритм сойдется к потоку (т.е. придет в состояние, когда e[v] = 0, для обычной v)
8. Полученный поток максимальный (т.к. не существует дополняющего пути из s в t)
3. Оценки на количества элементарных операций
1. Операций ReLabel O(V^2) (h[v] <= 2n-1)
2. Насыщенных операций Push O(VE) (высота растет)
3. Ненасыщенных операций ReLabel O(V^2*E) (для доказательства этого факта вводим функцию-потенциал = сумма высот)
4. DisCharge : (вызывается только, если e[v] > 0)

          cnt = 0
          while e[v] > 0 and cnt < deg[v] do
            Push(curE), curE = next, cnt++
          if e[v] > 0
            ReLabel

5. Все DisCharge-ы в сумме работают за O(VE) + O(число_вызовов)
   (между подъемами вершины v каждое ребро насыщается максимум 1 раз
4. Алгоритмы PreflowPush и MoveToFront
1. Инитиализация предпотока : h[s] = n, h[v != s] = 0, все ребра исходящие из s насыщены.
2. PreflowPush :

          while run
            for v : e[v] > 0
              DisCharge(v)

3. PreflowPush работает за O(V^2*E) = max из количеств всевозможных операций
4. MoveToFront :

          while run
            for v in List (пробегаем список целиком)
              if e[v] > 0
                DisCharge(v)
                if e[v] > 0
                  MoveToFront(v) (поместить вершину v в начало списка)

5. MoveToFront работает за O(V^3)
   Инвариант списка : ненасыщенные ребра идут вперед
   Поддерживается т.к. если вершина переместилась=поднялась, то в нее не могут входить ненасыщенные ребра.
   Инвариант списка => если мы дошли до конца списка без подъемов, то поток найден.
   => внутри каждой фазы цикла "while run" происходит хотя бы 1 ReLabel, а их O(V^2) => O(V^3)
5. Оптимизации
1. High-Level
   Поддерживаем List[h] - список вершин с избытком (активных) фиксированной высоты.
   Выбираем каждый раз v : e[v] > 0, h[v] = max, делаем DisCharge(v)
   Для этого поддерживаем maxH, и изменяем ее (Если список опустел dec, пока нужно. Если появилась более высокая, inc.)
   Sum (dec) <= Sum (inc) = O(n^2)
2. Global Relabeling
   h[v] <= d[v,t] (расстояние от v до стока)
   За O(E) (1 bfs) можем сделать h[v] := d[v,t] (при этом высоты вершин увеличиваются)
   Этот bfs следует делать каждые C*E операций.
3. Про дырки в высотной функции
   Если h[v] >= n, то весь ее избыток пойдет обратно в s
   Дырка в высотной фугкции ВСЕГДА ровно 1. Она как раз разделяет вершины h[v] >= n и h[v] < n.
   Если нас интересует только величина потока, можно вершины h[v] >= n выкидывать из графа.
   Если сделать 2Phase алгоритм сперва (h[v] < n) --> t, потом (h[v] >= n) --> s, будет быстрее.
4. P2R (Push 2 Level Relabeling)
   [v --> u] не (c[e] - f[e]), а min(c[e] - f[e], rest[u]) (rest[u] - сколько мы можем из u толкнуть вниз)
   И если (c[e] - f[e] > rest[u]) сразу поднять вершину u.


6. СНМ и его использование
1. Offline задача про минимумы на пути в дереве с O(n + m) памяти и O(mlogn) времени
2. Доказательство амортизационной оценки O(mlogn) на сжатие путей в СНМ
7. Offline методы в геометрии
1. K точек. Определить, где они находятся, относительно невыпуклого N-угольника (INSIDE, OUTSIDE, BORDER) за O(NlogN + KlogK) [ScanLine]
2. В случае выпуклого O(N + KlogK)
3. Поиск экстремальных точек для K прямых и выпуклого N-угольника за O(N + KlogK) [2 указателя]
4. Проверка для множества точек, разделяют ли их прямые = построить выпуклую оболочку и (см. выше)