Алгоритм масштабирования потока — различия между версиями
(→Оценка сложности) |
(→Оценка сложности) |
||
Строка 27: | Строка 27: | ||
Количество итераций — <tex> O(\log U) </tex>. Докажем, что сложность каждой итерации — <tex> O(E^2) </tex>. | Количество итераций — <tex> O(\log U) </tex>. Докажем, что сложность каждой итерации — <tex> O(E^2) </tex>. | ||
− | На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| </tex>. Поиск каждого дополнительного пути | + | На первом шаге ребра имеют пропускную способность <tex> 1 </tex>. Значит, <tex> |f_0| \leq |VG| </tex>. Поиск каждого дополнительного пути требует <tex> O(E) </tex> времени, а их количество не больше <tex> V </tex>. Итоговая сложность первой итерации — <tex> O(VE) \leq O(E^2) </tex>. |
}} | }} | ||
Версия 00:13, 19 декабря 2011
Определение: |
Алгоритм масштабирования потока — алгоритм поиска максимального потока путём регулирования пропускной способности рёбер. Этот алгоритм работает в предположении, что все пропускные способности рёбер целые, так как они легко представимы в двоичном виде. |
Содержание
Идея
Идея алгоритма в нахождении путей с высокой пропускной способностью в первую очередь, чтобы сразу сильно увеличивать поток по ним, а затем по всем остальным.
Пусть дан граф
с целыми пропускными способностями: . — максимальная пропускная способность. Запишем пропускную способность каждого ребра в двоичном виде. Тогда каждое число будет занимать бит.
Методом Форда-Фалкерсона находим поток
для графа с урезанными пропускными способностями . Добавим следующий бит и находим следующее приближение для графа с новыми пропускными способностями .После
итерации получим ответ к задаче.Оценка сложности
Утверждение: |
Время работы алгоритма — . |
Количество итераций — На первом шаге ребра имеют пропускную способность . Докажем, что сложность каждой итерации — . . Значит, . Поиск каждого дополнительного пути требует времени, а их количество не больше . Итоговая сложность первой итерации — . |
Псевдокод
Capacity-Scalingwhile do while в существует путь с пропускной способностью большей do путь с пропускной способностью большей увеличить поток по рёбрам на обновить