Расширения: улучшенная версия алгоритма

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

(7.30) Если на каждом шаге выбирается узел с избыточным потоком на макси- мальной высоте, количество ненасыщающих операций проталкивания в процессе выполнения алгоритма не превышает 4n3.

Доказательство. Рассмотрим максимальную высоту // = ⅛г) любо-

го узла с избыточным потоком во время выполнения алгоритма. В анализе будет использоваться максимальная высота Н вместо потенциальной функции ‘1’ из предыдущей границы O(n2m).

Максимальная высота H может увеличиться только из-за изменения меток (так как поток всегда проталкивается к узлам с меньшей высотой), поэтому общее возрастание H в алгоритме не может превышать 2n2 согласно (7.26). Значение H начинается с 0 и остается неотрицательным, поэтому количество изменений H не превышает 4n2.

Теперь рассмотрим поведение алгоритма в фазе времени, в которой H остается постоянной величиной. Утверждается, что каждый узел может иметь максимум одну ненасыщающую операцию push в этой фазе. Действительно, в этой фазе поток проталкивается от узлов на высоте H к узлам на высоте H - 1; и после ненасыщаю- щей операции push от v он должен получить поток от узла на высоте H + 1, прежде чем от него снова можно будет проталкивать поток.

Так как количество ненасыщающих операций push между изменениями H не превышает n, а H изменяется не более 4n2 раз, общее количество ненасыщающих операций push не превышает 4n3. ■

В продолжение (7.30) интересно заметить, что по проведенным экспериментам вычислительным «узким местом» метода является количество операций relabel, и более эффективное время выполнения было получено для модификаций, ко- торые увеличивают метки быстрее, чем по единице. Это обстоятельство будет рассмотрено подробнее в упражнениях.

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

Еще по теме Расширения: улучшенная версия алгоритма:

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