Разработка алгоритма
Допустим, мы начинаем с нулевого потока: 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
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- Разработка Плана
- 2.7. Разработка анкеты
- 6. Разработка перспектив
- Разработка и принятие Основного закона