Расширения: сильные полиномиальные алгоритмы

Возможно ли добиться результата, который бы качественно превосходил резуль- тат масштабирующего алгоритма? Одна из возможных целей могла бы выглядеть так: граф из нашего примера (рис. 7.6) состоит из четырех узлов и пяти ребер; хотелось бы использовать количество итераций, полиномиальное по числам 4 и 5, и полностью независимое от значений пропускных способностей.
Такой алгоритм, полиномиальный только по | V | и | E |, и работающий с числами, име- ющими полиномиальное количество битов, называется сильно полиномиальным. На самом деле существует простая и естественная реализация алгоритма Форда- Фалкерсона, которая ведет к такой сильно полиномиальной границе: каждая итерация выбирает увеличивающий путь с минимальным количеством ребер. Диниц, и независимо от него Эдмондс и Карп, доказали, что при таком выборе алгоритм завершается не более чем за O(mn) итераций. Это были первые поли- номиальные алгоритмы для задачи нахождения максимального потока. С тех пор был проделан значительный объем работы, направленной на улучшение времени выполнения алгоритмов нахождения максимального потока. В настоящее время известны алгоритмы с временем выполнения O(mn log n), O(n3) и O(min(n2/3,m1/2) m log n log U), причем последняя граница предполагает, что все пропускные спо- собности задаются целыми числами, не превышающими U. В следующем разделе рассматривается сильно полиномиальный алгоритм нахождения максимального потока, основанный на другом принципе.

7.4.

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

Еще по теме Расширения: сильные полиномиальные алгоритмы:

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