Выбор хороших увеличивающих путей - Нахождение потока в сети

В предыдущем разделе было показано, что любой выбор увеличивающего пути приводит к возрастанию величины потока; так мы пришли к границе С для количества увеличений, где При относительно небольших C такая граница выглядит разумно; однако при больших C она становится слишком слабой.

Чтобы понять, насколько плохо может сложиться ситуация, рассмотрим граф на рис. 7.2, но со следующими пропускными способностями: ребра (s, v), (s, u), (v, t) и (u, t) имеют пропускную способность 100, а у ребра (u, v) пропускная способность равна 1 (рис. 7.6). Легко увидеть, что максимальный поток равен 200: f(e) = 100 для ребер (s, v), (s, u), (v, t) и (u, t), а для ребра (u, v) он равен 0. Этот поток может быть получен в результате серии из двух увеличений, использующих пути с узлами s, u, t и s, v, t. Но подумайте, насколько плохо поведет себя алгоритм Форда-Фалкерсона при аномальном выборе увеличивающих путей. Допустим, мы начинаем с увеличивающего пути P₁, содержащего узлы s, u, v, t в указанном порядке (рис. 7.6). Для этого пути bottleneck(P₁, f) = 1. После увеличения имеем f(e) = 1 для ребра e = (u, v), поэтому в остаточном графе появляется обратное ребро. Для следующего увеличивающего пути выбирается путь Р₂ путь Р₂ из узлов s, v, u, t в таком порядке. При втором увеличении мы также получаем bottleneck(P₂, f) = 1. После второго увеличения имеем f(e) = 0 для ребра e = (u, v), поэтому ребро снова находится в остаточном графе. Далее P₁ и P₂ поочередно выбираются для увеличения. В этом случае для того, чтобы добраться до желаемого потока с величиной 200, потребуется 200 увеличений. Именно эта граница была доказана в (7.4), так как в данном примере C = 200.

Разработка ускоренного алгоритма потока

В этом разделе мы покажем, что при более разумном выборе путей эту границу можно существенно улучшить. В области поиска хороших вариантов выбора увеличивающих путей в задаче о максимальном потоке, минимизирующих количество итераций, была проведена значительные исследования. Сейчас мы сосредоточимся на одном из самых естественных методов, а в конце раздела будут кратко упомянуты и другие методы. Вспомните, что увеличение наращивает величину максимального потока на критическую пропускную способность выбранного пути; следовательно, если выбирать пути с большой критической пропускной способностью, ситуация значительно улучшится. Естественно будет выбрать путь с наибольшей критической пропускной способностью. С другой стороны, необходимость поиска таких путей замедлит каждую отдельную итерацию. Чтобы избежать замедления, мы не будем беспокоиться о выборе пути, который бы имел в точности наибольшую критическую пропускную способность. Вместо этого мы введем масштабирующий параметр Δ и будем искать пути с критической пропускной способностью не менее Δ.

Рис. 7.6. Четыре итерации алгоритма Форда-Фалкерсона с неудачным выбором увеличивающих путей: увеличения чередуются между путем P₁ с узлами s, u, v, t (в указанном порядке) и путем Р₂ с узлами s, u, v, t (в указанном порядке)

Пусть G_f(Δ) — подмножество остаточного графа, состоящее только из ребер с пропускной способностью не менее Δ. Мы будем работать со значениями Δ, которые являются степенью 2. Ниже приведен алгоритм.

Анализ алгоритма

Для начала заметим, что новый алгоритм максимального потока с масштабированием представляет собой простую реализацию исходного алгоритма Форда-Фалкерсона. Новые циклы, значение Δ и сокращенный остаточный граф G_f(Δ) нужны только для того, чтобы управлять выбором остаточного пути — чтобы ребра с большой остаточной пропускной способностью использовались как можно дольше. Следовательно, все свойства, доказанные для исходного алгоритма Форда-Фалкерсона истинны и для новой версии; поток остается целочисленным в этом алгоритме, а следовательно, все остаточные пропускные способности также являются целочисленными.

(7.15) Если пропускные способности являются целочисленными, то в алгоритме максимального потока с масштабированием поток и остаточные пропускные способности также остаются целочисленными. Из этого следует, что при Δ = 1, G_f(Δ) не отличается от G_f — а следовательно, когда алгоритм завершает построение потока, f имеет максимальную величину.

Теперь рассмотрим время выполнения. Назовем итерацию внешнего цикла (с фиксированным значением Δ) фазой Δ-масштабирования. Легко дать верхнюю границу для количества разных фаз Δ-масштабирования в контексте значения которое также использовалось в предыдущем разделе. Начальное значение Δ не превышает C, уменьшается вдвое и никогда не опускается ниже 1. Следовательно,

(7.16) Количество итераций внешнего цикла не превышает 1 + [log₂ С].

Сложнее ограничить число увеличений, выполняемых в каждой фазе масштабирования. Идея заключается в том, что мы используем пути, значительно увеличивающие поток, поэтому увеличений должно быть относительно немного. Во время фазы Δ-масштабирования используются только ребра с остаточной пропускной способностью не менее Δ. Используя (7.3), получаем

(7.17) В фазе Δ-масштабирования каждое увеличение повышает величину потока минимум на Δ.

Здесь принципиально то, что в конце фазы Δ-масштабирования поток f не может слишком сильно отличаться от максимального возможного значения.

(7.18) Пусть f — поток в конце фазы Δ-масштабирования. В G существует разрез s-t (A, B), для которого c(A, B) ≤ v(f) + mΔ, где m — количество ребер в графе G. Соответственно, величина максимального потока в сети не превышает v(f) + mΔ.

Доказательство. Это доказательство аналогично доказательству (7.9), которое устанавливало максимальную величину потока, возвращаемого исходным алгоритмом максимального потока.

Как и в том доказательстве, необходимо найти разрез (A, B) с нужным свойством. Обозначим A множество всех узлов v в G, для которых в G_f(Δ) существует путь s-v. Множество всех остальных узлов обозначается B: B = V - A. Мы видим, что (A, B) действительно является разрезом s-t, в противном случае фаза бы не закончилась.

Теперь рассмотрим ребро e = (u, v) в G, для которого u ∈ A и v ∈ B. Утверждается, что c_e < f(e) + Δ. В противном случае e было бы прямым ребром в графе G_f(Δ), а так как u ∈ A, существует путь s-u в G_f(Δ); присоединяя e к этому пути, мы получаем путь s-v в G_f(Δ), что противоречит предположению о v ∈ B. Аналогично можно утверждать, что для любого ребра e' = (u', v') в G, для которого u' ∈ B и v' ∈ A, выполняется f(e) < Δ. Если бы f(e') ≥ Δ, то ребро e' породило бы обратное ребро e" = (v', u') в графе G_f(Δ), а поскольку v' ∈ A, в G_f(Δ) существует путь s-v'; присоединяя e" к этому пути, мы получаем путь s-u' в G_f(Δ), что противоречит предположению о u' ∈ B.

Итак, все ребра e из A почти насыщены — они удовлетворяют условию c_e < f(e) + Δ — все ребра, направленные в A, почти пусты — они удовлетворяют условию f(e) < Δ. Теперь мы можем воспользоваться (7.6), чтобы прийти к нужному выводу:

Первое неравенство следует из ограничений на величину потока в ребрах, пересекающих разрез, а второе — из того простого факта, что граф содержит только m ребер.

Величина максимального потока ограничивается пропускной способностью любого разреза по (7.8). Мы используем разрез (A, B) для получения границы, заявленной во втором утверждении. ■

(7.19) Количество увеличений в фазе масштабирования не превышает 2m.

Доказательство. Истинность утверждения в первой фазе масштабирования очевидна; в этой фазе каждое из ребер, выходящих из s, может использоваться не более чем для одного увеличения. Теперь рассмотрим более позднюю фазу масштабирования Δ; обозначим f_p поток в конце предыдущей фазы масштабирования. В этой фазе в качестве параметра использовалось значение Δ' = 2Δ. Согласно (7.18) максимальный поток f* не превышает v(f*) ≤ v(f_p) + mΔ' = v(f_p) + 2mΔ. В фазе Δ-масштабирования каждое увеличение повышает поток минимум на Δ, а следовательно, увеличений не может быть более 2m. ■

Одно увеличение выполняется за время O(m), включая время, необходимое для подготовки графа и нахождения соответствующего пути. При этом используется максимум 1 + [log₂ C] фаз масштабирования, а в каждой фазе выполняется не более 2m увеличений. Соответственно мы приходим к следующему результату.

(7.20) Масштабирующий алгоритм нахождения максимального потока в графе с m ребрами и целочисленными пропускными способностями находит максимальный поток не более чем за 2m(1 + [log₂ C]) увеличений. Он может быть реализован для выполнения за максимальное время O(m² log₂ C).

При больших C эта граница намного лучше границы O(mC), действующей для произвольной реализации алгоритма Форда-Фалкерсона. В примере, приведенном в начале раздела, пропускные способности были равны 100, но с таким же успехом они могут быть равны 2¹⁰⁰; в этом случае обобщенный алгоритм Форда-Фалкерсона может занять время, пропорциональное 2¹⁰⁰, тогда как масштабирующий алгоритм будет выполнен за время, пропорциональное log₂(2¹⁰⁰) = 100.

Различие можно рассматривать так: обобщенный алгоритм Форда-Фалкерсона требует времени, пропорционального значению пропускных способностей, тогда как масштабирующему алгоритму достаточно времени, пропорциональному количеству битов, необходимых для представления пропускных способностей во входных данных. В результате масштабирующие алгоритмы выполняются за время, полиномиальное по размеру входных данных (то есть количеству ребер и числовому представлению пропускных способностей); тем самым достигается традиционная цель — обеспечение полиномиального времени выполнения алгоритма. Плохие реализации алгоритма Форда-Фалкерсона, требующие около C итераций, этого стандарта полиномиальности не достигают. (Вспомните, что в разделе 6.4 для описания таких алгоритмов, полиномиальных по величине входных значений, но не по количеству битов, необходимых для их представления, использовался термин “псевдополиномиальность”).

Расширения: сильные полиномиальные алгоритмы

Возможно ли добиться результата, который бы качественно превосходил результат масштабирующего алгоритма? Одна из возможных целей могла бы выглядеть так: граф из нашего примера (рис. 7.6) состоит из четырех узлов и пяти ребер; хотелось бы использовать количество итераций, полиномиальное по числам 4 и 5, и полностью независимое от значений пропускных способностей. Такой алгоритм, полиномиальный только по |V| и |E|, и работающий с числами, имеющими полиномиальное количество битов, называется сильно полиномиальным. На самом деле существует простая и естественная реализация алгоритма Форда-Фалкерсона, которая ведет к такой сильно полиномиальной границе: каждая итерация выбирает увеличивающий путь с минимальным количеством ребер. Диниц, и независимо от него Эдмондс и Карп, доказали, что при таком выборе алгоритм завершается не более чем за O(mn) итераций. Это были первые полиномиальные алгоритмы для задачи нахождения максимального потока. С тех пор был проделан значительный объем работы, направленной на улучшение времени выполнения алгоритмов нахождения максимального потока. В настоящее время известны алгоритмы с временем выполнения O(mn log n), O(n³) и O(min(n^2/3, m^1/2)m log n log U), причем последняя граница предполагает, что все пропускные способности задаются целыми числами, не превышающими U. В следующем разделе рассматривается сильно полиномиальный алгоритм нахождения максимального потока, основанный на другом принципе.