Анализ алгоритма: завершение и время выполнения

Начнем с доказательства некоторых свойств алгоритма; для этого мы воспользу- емся методом индукции по количеству итераций цикла, предполагая, что все про- пускные способности являются целыми числами.

(7.2) На каждой промежуточной стадии алгоритма Форда-Фалкерсона вели- чины потока {f (e)} и остаточные пропускные способности в Gf являются целыми числами.

Доказательство. Истинность этого утверждения до начала цикла очевидна. Теперь предположим, что оно истинно после j итераций. Поскольку все остаточные емкости в G являются целыми числами, значение bottleneck(P, f) для увеличиваю- щего пути, найденного в итерации j + 1, будет целым числом. Из этого следует, что поток f будет иметь целые значения — а значит, и пропускные способности нового остаточного графа будут целыми числами. ■

На основании этого свойства можно доказать, что алгоритм Форда-Фалкерсона завершается. Как и ранее в книге, мы будем искать метрику прогресса, из которой можно будет сделать вывод о завершении.

Сначала покажем, что величина потока строго возрастает при применении увеличения.

(7.3) Пусть f — поток в G, а P — простой путь s-t в G . Тогда v(f) = v(f) + + bottleneck(P,f); а так как bottleneck(P,f) > 0, имеем v(f') > v(f).

Доказательство. Первое ребро e в пути P должно выходить из s в остаточном графе Gf; поскольку путь является простым, он не возвращается к s. Так как в G нет ребер, входящих в s, ребро e должно быть прямым. Мы увеличиваем поток по этому ребру на bottleneck(P, f) и не изменяем поток через любое другое ребро, ин- цидентное s. Следовательно, значениеf превышает значениеfна bottleneck(P,f). ■

Чтобы доказать завершение цикла, нам потребуется еще одно наблюдение: не- обходимо иметь возможность установить границу для максимально возможной величины потока. Граница может быть такой: если все ребра, выходящие из s, могут

быть полностью насыщены потоком, то величина потока будет равна У!rniffnff⅛.

Обозначим эту сумму C; можно утверждать, что v( f) < C для всех потоков f для s-t. (C как оценка максимальной величины потока в G может быть сильно завышенной, но сейчас она для нас удобна как конечная и просто определяемая граница). Ис- пользуя утверждение (7.3), мы теперь можем доказать завершение цикла.

(7.4) Предположим, как указано выше, что все пропускные способности в по- токовой сети G являются целыми числами.

Тогда алгоритм Форда-Фалкерсона завершается не более чем за C итераций цикла.

Доказательство. Ранее было замечено, что величина никакого потока в G не может превышать C (из-за ограничения пропускной способности для ребер, вы- ходящих из i). Согласно (7.3) величина потока, которым управляет алгоритм Фор- да-Фалкерсона, возрастает при каждой итерации; следовательно, согласно (7.2),

при каждой итерации она увеличивается по крайней мере на 1. Так как значение начинается с 0 и не может превысить C, цикл в алгоритме Форда-Фалкерсона вы- полняется не более чем за C итераций. ■

Перейдем к рассмотрению времени выполнения алгоритма Форда-Фалкерсона. Пусть n — количество узлов в G, а m — количество ребер в G. Мы предполагали, что все узлы имеют хотя одно инцидентное ребро, поэтому m > n/ 2, и для упрощения границ можно использовать O(m + n) = O(m).

(7.5) Предположим, все пропускные способности в потоковой сети G являются целыми числами. В этом случае алгоритм Форда-Фалкерсона может быть реали- зован с временем O(mC).

Доказательство. Из (7.4) известно, что алгоритм завершается максимум за C итераций цикла. Рассмотрим объем работы, задействованной в одной итерации при текущем потоке f

Остаточный граф Gf содержит не более 2m ребер, так как каждое ребро G по- рождает не более двух ребер в остаточном графе. Для хранения Gf будет исполь- зоваться представление списка смежности; для каждого узла v будут храниться два связанных списка: с ребрами, входящими в v, и с ребрами, выходящими из v. Чтобы найти путь s-t в Gf, можно воспользоваться поиском в ширину или в глу- бину, работающим за время O(m + n); согласно предположению о том, что m > n/2, O(m + n) — то же, что O(m). Процедура augment(f, P) выполняется за время O(n), так как путь P содержит максимум n - 1 ребро. Для известного нового потока f' новый остаточный граф можно построить за время O(m): для каждого ребра e из G строятся правильные ребра (прямое и обратное) в Gf'.

Несколько более эффективная версия алгоритма будет хранить связанные списки ребер остаточного графа Gf в процедуре, изменяющей поток f посредством увеличения.

7.2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ алгоритма: завершение и время выполнения:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Анализ завершенности и симметричности мандалы
  3. Статья 849. Права заказчика во время выполнения работы
  4. Статья 1196. Возмещение вреда, причиненного физическому лицу во время выполнения им договорных обязательств
  5. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  6. АЛГОРИТМ
  7. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  8. Время сейчас такое – время мудрости пришло!
  9. АЛГОРИТМ УДАЧИ
  10. Завершение допроса.
  11. Алгоритм исцеления:
  12. Алгоритм избавления от боли
  13. Завершенная мандала
  14. 4.5. Завершение беседы