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