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

Как обычно, алгоритм нельзя назвать полностью определенным. Для его реализа- ции нужно определить, какой узел с избыточным потоком следует выбрать и как эффективно выбрать ребро для проталкивания. Однако ясно, что каждая итерация этого алгоритма может быть реализована за полиномиальное время.
(Позднее мы обсудим, как реализовать ее c достаточной эффективностью.) Более того, нетруд- но увидеть, что предпоток f и разметка h остаются совместимыми на протяжении работы алгоритма. Если алгоритм завершается (что из его описания далеко не очевидно), то узлов с положительным избыточным потоком не остается (кроме t), а следовательно, предпоток f действительно является потоком. Затем из (7.22) следует, что f будет максимальным потоком при завершении.

Приведем несколько простых наблюдений относительно алгоритма.

(7.24) Во время выполнения алгоритма проталкивания предпотока:

(i) метки высот являются неотрицательными целыми числами;

(ii) если пропускные способности являются целыми числами, то предпоток f

является целым числом;

(iii) предпоток f и разметка h совместимы.

Если алгоритм возвращает предпотокf тоf является потоком с максимальной величиной.

Доказательство. Согласно (7.23), исходный предпотокf и разметка h совмести- мы. Докажем посредством индукции по количеству операций push и relabel, что f и h обладают свойствами из утверждения. Операция проталкивания изменяет предпотокf но границы δ гарантируют, что возвращаемый поток f удовлетворяет ограничениям пропускной способности и что все избыточные потоки остаются неотрицательными, так что f остается предпотоком. Чтобы убедиться в совме- стимости предпотокаf и разметки h, заметим, что операция рush(f, h, v, w) может добавить одно ребро в остаточный граф — обратное ребро (v, w), и это ребро удовлетворяет ограничению крутизны. Операция relabel увеличивает метку v, а следовательно, повышает крутизну всех ребер, выходящих из v. Однако она при- меняется только в том случае, если никакое ребро, выходящее из v в остаточном графе, не направлено вниз — а значит, предпоток f и разметка h совместимы после изменения метки.

Алгоритм завершается, когда ни один узел, кроме 5 или t, не имеет избыточного потока. В этом случае f является потоком по определению; а поскольку предпоток f и разметка h остаются совместимыми на протяжении работы алгоритма, из (7.22) следует, что f является потоком с максимальной величиной. ■

Теперь рассмотрим количество операций push и relabel. Сначала докажем ограничение на количество операций relabel — это поможет доказать предел максимального числа возможных операций проталкивания. Алгоритм никогда не изменяет метку 5 (так как у источника не может быть положительного избы- точного потока). У всех остальных узлов v изначально h(v) = 0, а метка возрастает на 1 при каждом изменении. Следовательно, нужно просто установить предел для максимально возможного значения метки. Узел v становится кандидатом для relabel только в том случае, если у v есть избыточный поток. Единственный ис- точником потока в сети является 5; интуитивно ясно, что избыточный поток в v должен происходить из 5. Следующее следствие из этого факта играет ключевую роль в ограничении меток.

(7.25) Имеется предпоток f Если в узле v имеется избыточный поток, то суще- ствует путь в Gf из v к источнику 5.

Доказательство. Пусть A обозначает множество всех узлов w, для которых су- ществует путь из w в 5 в остаточном графе Gf а B = V - A. Требуется показать, что все узлы с избыточным потоком принадлежат A.

Отметим, что 5 A. Кроме того, никакие ребра e = (х, у), выходящие из A, не могут иметь положительный поток, так как ребро с f (e) > 0 породило бы обратное ребро (y, х) в остаточном графе, и тогда узел у находился бы в A. Теперь рассмотрим сумму избыточных потоков в множестве B и вспомним, что каждый узел в B имеет неотрицательный избыточный поток, так как 5 ⅜ B.

Изменим запись суммы в правой части. Если оба конца ребра e принадлежат B, то f (e) один раз включается в сумму со знаком «+» и один раз со знаком «-»; два слагаемых компенсируются. Если у e только конечный узел принадлежит B, то e выходит из A, а как было показано выше, у всех ребер, выходящих из A, f (e) = 0. Если у e только начальный узел принадлежит B, то f (e) включается в сумму только один раз со знаком «-». Таким образом, получаем

Так как потоки неотрицательны, мы видим, что сумма избыточных потоков в B равна нулю; так как каждый отдельный избыточный поток в B неотрицателен, это означает, что все они должны быть равны 0. ■

Теперь можно доказать, что в процессе выполнения алгоритма метки не изме- няются слишком значительно. Вспомните, что n обозначает число узлов в V.

(7.26) Во время выполнения алгоритма для всех узлов h(v) < 2n - 1.

Доказательство. Исходные метки h(t) = 0 и h(s) = n не изменяются во время

выполнения алгоритма. Рассмотрим произвольный узел v Ф s, t. Алгоритм изменяет метку v только при применении операции relabel; пусть f и h — предпоток и раз- метка, возвращенные операцией relabel (f h, v). Согласно (7.25) существует путь P в остаточном графе Gf из v в s. Обозначим |P| количество ребер в P; заметим, что |P| < n - 1. Ограничение крутизны подразумевает, что высоты узлов могут убывать не более чем на 1 с каждым ребром P; следовательно, h(v) - h(s) < |P |, что доказывает утверждение. ■

Метки монотонно возрастают во время выполнения алгоритма, поэтому это утверждение немедленно устанавливает предел для количества операций изме- нения меток.

(7.27) В процессе выполнения алгоритма метка каждого узла изменяется не более 2n - 1 раз, поэтому общее количество операций relabel меньше 2n2.

Затем будет установлена граница для количества операций проталкивания. Будем различать два вида таких операций: операция рush(f h, v, w) называется на- сыщающей, если либо e = (v, w) является прямым ребром в Е и δ = ce - f (e), либо (v, w) является обратным ребром с e = (w, v) и δ = f (e). Иначе говоря, проталкивание является насыщающим, если после него ребро (v, w) уходит из остаточного графа. Все остальные операции проталкивания будут называться ненасыщающими.

(7.28) В процессе выполнения алгоритма количество насыщающих операций push не превышает 2nm.

Доказательство. Рассмотрим ребро (v, w) в остаточном графе. После насыщаю- щей операции проталкивания рush(f, h, v, w) имеем h(v) = h(w) + 1, а ребро (v,w) по- кидает остаточный граф G , как показано на рис. 7.8. Прежде чем мы снова сможем выполнять проталкивание по этому ребру, сначала необходимо протолкнуть из w в v, чтобы ребро (v, w) появилось в остаточном графе. Но для проталкивания из w в v сначала метка w должна увеличиться минимум на 2 (чтобы узел w находился выше v). Метка w может увеличиться на 2 не более n - 1 раза, так что насыщающее проталкивание из v в w может происходить не более n раз. Каждое ребро e E может породить до двух ребер в остаточном графе, поэтому общее количество на- сыщающих проталкиваний не превышает 2nm. ■

Рис. 7.8. После насыщающего проталкивания рush(f h, v, w) высота v превышает высоту w на 1


Самая сложная часть анализа — доказательство границы для количества нена- сыщающих проталкиваний. Она же становится критическим фактором в теорети- ческой границе времени выполнения.

(7.29) В процессе выполнения алгоритма количество ненасыщающих операций push не превышает 2n2m.

Доказательство. В этом доказательстве мы воспользуемся так называемым методом потенциальных функций. Для предпотока f и совместимой разметки h мы определяем

как сумму высот всех узлов с положительным избыточным потоком. (Функция Ф часто называется потенциальной, потому что она напоминает «потенциальную энергию» всех узлов с положительным избыточным потоком).

В исходном предпотоке и разметке все узлы с положительным избыточным потоком имеют высоту 0, поэтому Ф(/. h)= 9 остается неотрицательной во время выполнения алгоритма. Ненасыщающая операция рush(/ И, v, w) уменьшает Ф(/"*⅛) как минимум на 1, потому что после проталкивания узел v не имеет избыточного потока, а w — единственный узел, получающий новый избыточный поток от опе- рации — имеет высоту на 1 меньше, чем v. Однако каждая насыщающая операция проталкивания и каждая операция rеl аbеl может увеличить Ф(/,Л). Операция rеl аbеl увеличивает ФСЛ А) ровно на 1. Выполняется не более 2п2 операций rеl аbеl, поэтому общее возрастаниеЙ), обусловленное операциями relabel, составит 2и2. Насыщающая операция рush(/ h, v, w) не изменяет метки, но она может уве- личить Ф(/,Л), потому что узел w может неожиданно получить положительный избыточный поток после проталкивания. Это приведет к увеличению Ф(/,Л) на высоту w, которая не превышает 2n - 1. Существуют максимум 2пт насыщающих операций проталкивания, поэтому общее возрастание Ф(/,Л) из-за операций про- талкивания не превышает 2тп(2п - 1). Следовательно, под действием двух фак- торов Ф(/,Л) может возрасти максимум на Атп2 во время выполнения алгоритма.

Но так как Ф остается неотрицательным и убывает минимум на 1 при каждой ненасыщающей операции проталкивания, из этого следует, что количество нена- сыщающих операций проталкивания не может превышать 4mn2. ■

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

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

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