Графы-4: максимальный поток

Введение

Рассматривается ориентированный граф («сеть»), в котором есть две выделенные вершины: исток s и сток t. Исток не имеет входящих рёбер, сток — исходящих рёбер. Кроме того, если в сети существует ребро (u, v), то не существует ребра (v, u). Для каждого ребра (u, v) задана пропускная способность («capacity»), обозначаемая обычно c(u, v) или A(u, v). Ниже она задаётся матрицей, так же как и сам граф: пропускная способность несуществующих рёбер равна нулю.

Требуется найти максимальный поток F, который может пропустить сеть в силу заданных пропускных способностей. Поток в сети задаётся матрицей потоков, проходящих по рёбрам. Должно выполняться условие F(u, v) ≤ A(u, v).

Алгоритмы

Известно два основных класса алгоритмов, решающих задачу максимизации потока на сети:

  1. Класс алгоритмов Форда-Фалкерсона (Ford-Fulkerson algorithm), строящих дополняющие цепи.
  2. Алгоритмы проталкивания предпотока (preflow pushing algorithm, push-relabel algorithm), пытающихся максимально заполнить сеть, оперируя избытком «жидкости» в вершинах.

Алгоритмы Форда-Фалкерсона

Алгоритмы основаны на теореме Форда-Фалкерсона. Общий принцип работы:

  1. Устанавливается F(u, v) = 0, для всех пар u, v.
  2. Пока можно построить новую дополняющую цепь на остаточном графе, дополняем F(u, v) в силу построенной цепи.

Остаточный граф (residual graph) — граф с пропускными способностями рёбер равными A(u, v) — F(u, v), если A(u, v) > 0 (прямая дуга), или F(v, u), если A(u, v) = 0 (обратная дуга).

Дополняющей цепью называется цепь попарно-инцидентных на остаточном графе вершин, соединяющая исток и сток. Пропускная способность дополняющей цепи равна минимуму из пропускных способностей рёбер, её составляющих. Применение дополняющей цепи увеличивает общий поток на свою пропускную способность, при этом для прямых дуг поток увеличивается на это число, а для обратных — уменьшается.

Разные реализации общей идеи по-разному решают вопрос поиска очередной дополняющей цепи. Существует два классических алгоритма 1970-х: алгоритм Эдмондса-Карпа (реализован в BGL) сложности O(N M2) ≤ O(N5) и алгоритм Ефима Диница сложности O(N2 M) ≤ O(N4). К новым алгоритмам этого семейства можно отнести алгоритм Бойкова-Колмогорова (описание из BGL, статья).

Алгоритмы проталкивания предпотока

В 1980-х появилось новое семейство алгоритмов построения максимального потока типа, отличного от ранее известных алгоритмов Форда-Фалкерсона. В данном контексте будем называть F предпотоком. Для предпотока выполняются следующие условия: F(u, v) ≤ A(u, v) и F(u, v) = —F(v, u).

Пусть для каждой вершины v задана высота h[v]  ≥ 0 и избыток e[v] ≥ 0. Вершины, в которых избыток больше нуля, называются активными. Для любых вершин u, v, кроме стока и истока, должно быть выполнено условие: если (u, v) принадлежит остаточному графу, то h[u] ≤ h[v] + 1. Обычно полагают h[s] = N, h[t] = 0. Избыток в вершине равен разностью между суммой потоков на исходящих рёбрах и суммой потоков на входящих рёбрах.

Основная идея алгоритма состоит в первоначальном максимальном заполнении исходящих рёбер истока и «проталкивании» избытка из активных вершин по рёбрам остаточного графа в вершины, имеющими высоту, меньшую на 1. Если весь избыток вывести не удалось, то высота вершины увеличивается. Алгоритм останавливается, когда не остаётся активных вершин.

Базовая версия алгоритма (реализация на e-maxx.ru) без упорядочивания активных вершин имеет оценку сложности O(N2 M) ≤ O(N4). Вариант, «прогоняющий» вершины через очередь имеет оценку сложности O(N3). Вариант, поднимающий в начало очереди активных вершин вершину, в случае увеличения её высоты (реализация на e-maxx.ru, описание реализации BGL), имеет оценку O(N2 sqrt(M)) ≤ O(N3).

Реализация

Была написана реализация алгоритмов Эдмондса-Карпа и проталкивания предпотока с переупорядочиванием поднятых вершин (maxFlowPushRelabel) и с обработкой активных вершин в порядке очереди («базовый», maxFlowPushing).

Алгоритмы реализованы как функции-шаблоны и имеют параметр шаблона WeightMatrix, задающий тип матрицы пропускных способностей.

Кроме того, алгоритм Форда-Фалкерсона принимает тип-параметр Augmentor, который считается классом, определяющим статическую функцию augment, строящую следующую дополняющую цепь. Имеется одна реализация: EdmondsKarp, строящая цепь поиском в ширину. Таким образом, функция maxFlowFordFulkerson<EdmondsKarp> реализует алгоритм Эдмондса-Карпа.

Аналогично, алгоритмы проталкивания предпотока принимают тип-параметр Heights, который считается классом, определяющим статическую функцию heights, инициализирующую массив высот вершин. Определён один такой класс: HeightsBFS, который вычисляет высоты поиском в ширину в обратном направлении (против направления рёбер), начиная со стока. Впрочем, эксперименты не обнаружили существенного влияния способа инициализации высот на скорость работы алгоритмов.

Задания

  1. Прочитать и понять код, почему первое выводимое число всегда 1, а последнее — 0?
  2. Каким ещё образом можно реализовать выборку наивысшей активной вершины?
  3. Можно ли объединить код maxFlowPushing и maxFlowPushRelabel в одну функцию-шаблон?
Реклама

One response

  1. […] — самая популярная запись каждый год одна и та же: Графы-4: максимальный поток, 2011 года, абсолютно периферийная для меня. Это некие […]

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: