Разработка алгоритма

Итак, требуется найти максимальный поток в сети. Как взяться за решение этой задачи? Эксперименты показывают, что такие методы, как динамическое про- граммирование, не работают — по крайней мере для задачи о нахождения макси- мального потока не существует алгоритма, который можно было бы естественно рассматривать как относящийся к парадигме динамического программирования.
В отсутствии других идей можно поразмыслить над простыми жадными методами, чтобы понять, почему они не работают.

Допустим, мы начинаем с нулевого потока: f(e) = 0 для всех e. Очевидно, это состояние соблюдает ограничения пропускной способности и сохранения; про- блема в том, что в нем величина потока равна 0. Попробуем увеличить значение f «проталкивая» поток по пути из 5 в t, до границ, установленных пропускными способностями ребер. Таким образом, на рис. 7.3 можно было бы выбрать путь, состоящий из ребер {(5, u), (и, v), (v, t)}, увеличить поток по каждому из этих ребер до 20 и оставить f(e) = 0 для двух других. Это позволит выполнить ограничения пропускной способности (поток не превышает пропускной способности ребер) и ограничения сохранения потока (при увеличении потока для ребра, входящего во внутренний узел, мы также увеличиваем его для ребра, выходящего из узла). Теперь величина потока равна 20; возникает резонный вопрос: является ли она максимумом, возможным для изображенного графа? Если немного подумать, становится понятно, что в графе можно построить поток с величиной 30. Про- блема в том, что мы «зашли в тупик» (не существует пути s-t, в который можно было бы напрямую протолкнуть поток без превышения пропускной способности), а максимальный поток еще не достигнут.

Необходим более общий механизм про- талкивания потока из 5 в t, который бы позволял увеличить величину текущего потока в подобных ситуациях.

Фактически нам хотелось бы выполнить операцию, обозначенную на рис. 7.3, c пунктирной линией. В ребро (5, v) проталкиваются 10 единиц потока; в результате в v входит слишком большой поток. Соответственно мы «отменяем» 10 единиц по- тока в (u, v); при этом восстанавливается ограничение сохранения потока для v, но зато из и выходит слишком малый поток. На последнем шаге 10 единиц потока про- талкиваются в ребро (u, t), что приводит к восстановлению состояния сохранения для u. В результате в графе обнаруживается действительный поток величины 30. На рис. 7.3 темными ребрами обозначается поток перед операцией, а пунктирны- ми — возможность его увеличения.

Рис. 7.3. (a) Сеть на рис. 7.2. (b) Проталкивание 20 единиц потока по пути s, u, v, t. (с) Новый увеличивающий путь использует ребро (u, v) в обратном направлении


В этом и заключается более общий механизм проталкивания потока: проталки- вание ведется в прямом направлении для ребер со свободной пропускной способ- ностью и в обратном направлении для ребер, по которым уже передается поток, для его перевода в другом направлении. Определим понятие остаточного графа, который предоставит систематический механизм поиска подобных операций.

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

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

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