Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Нахождение максимального пропускного потока

Поиск:
Заметим, во-первых, что это задача линейного программирования, так что ее можно решать симплекс-методом. Более того, теорема о максимальном потоке и минимальном разрезе - в точности теорема двойственности для задачи линейного программирования.

Hо для этой конкретной задачи есть более просто описываемый алгоритм - алгоритм Форда-Фалкерсона (в сущности, это и есть симплекс-метод, примененный в конкретной ситуации).

Алгоритм, грубо говоря, жадный. Hайдем сначала хоть какой-то поток ненулевого веса (нужно найти путь из истока в сток, желательно, с максимальным весом (чтобы алгоритм быстрее работал); можно для этого применить соответствующим образом модифицированный алгоритм Дейкстры).

После этого на кажом шаге алгоритма смотрим, можем ли мы модифицировать наш поток так, чтобы его вес стал больше. Если так модифицировать нельзя, то мы нашли максимальный поток.

Модификация заключается в следующем. Попытаемся "прибавить" к нашему потоку новый. Для этого рассмотим новый граф с теми же вершинами, но новыми пропускными способностями ребер: если пропускная способность ребра от вершины A к вершине B равна c, а в нашем потоке по этому ребру пущено x, то в новом графе есть ребро от A к B с пропускной способностью c-x и ребро от B к A с пропускной способностью x (грубо говоря, мы можем увеличить поток по этому ребру максимум на c-x или уменьшить максимум на x).

После этого в новом графе ищем какой-нибудь поток из истока в сток ненулевого веса (снова можно применить что-нибудь вроде Дейкстры). Если такого нет - ура, тот поток, который у нас был - максимальный. Если есть - складываем эти два потока, получаем новый, с большим весом. Повторяем процесс.

К сожалению, этот алгоритм (как и симплекс-метод) не гарантирует, что время работы полиномиально (если нет ограничений на пропускные способности). В _подавляющем_ _большинстве_ случаев это так, но можно придумать "плохие" примеры, для которых время работы будет экспоненциальным (но в практических задачах они вряд ли встретятся).

Если известно, что пропускные способности ребер - "небольшие" целые числа, то алгоритм действительно работает за O(N3).






Просмотров: 3665

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную