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

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


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

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

Scaling Max-Flow

В исходном состоянии f(e) = 0 для всех e в G

Инициализировать Δ наибольшей степенью 2, не превышающей максимальную пропускную способность из s: Δ < maxe out of sce Пока Δ > 1

Пока существует путь s-t в графе G (Δ)

Присвоить P простой путь s-t в G (Δ) f = augment( f,P)

Обновить f до f и обновить G (Δ)

Конец Пока Δ = Δ/2 Конец Пока Вернуть f

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

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

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