AlMag 22 авг 2010 в 18:41

Методы применения алгоритма нахождения максимального потока в сети

7 мин

47K

Алгоритмы*

+38

Комментарии 14

inspush 24 авг 2010 в 14:11

торт!

red1ynx 24 авг 2010 в 14:19

Спасибо, интересно.
Только лучше использовать специализированные алгоритмы. Например, для паросочетаний тот же Кун работает за O(n^2), когда max-flow за O(n^3).

AlMag 24 авг 2010 в 14:25

Ну, этим можно пользоваться, когда у Вас уже накожен поток и ограничения позволяют его пустить. Тогда только исток и сток добавить. Экономия времени.

Например, для паросочетаний тот же Кун работает за O(n^2)

O(N*M) точнее. Плюс эвристики позволяют хорошо сэкономить на случайных графах

EgorK 24 авг 2010 в 14:49

В посте по ссылке какой-то очень сложный алгоритм потока представлен. На олимпиадах обычно используется алгоритм попроще, который работает за O(E * F), где F — число раз, которые мы находим новый путь из истока в сток (в случае, если все ребра имеют пропускную способность 0 или 1 — это просто максимальный поток). В большинстве случаев он опережает остальные алгоритмы по скорости

AlMag 24 авг 2010 в 15:10

если писать чистого Форда-Фалкерсона, то он может по времени не пройти на некоторых тестах (с большим весом ребер). По ссылке сразу реализован максимальный поток минимальной стоимости.
Здесь в разделе «потоки и связанные с ними задачи» можно разобраться с большинством существующих методов пускания потока.

red1ynx 24 авг 2010 в 16:12

А сайт по ссылке ваш?

AlMag 24 авг 2010 в 16:25

нет, это многоуважаемого e-maxx

tagir_valeev 24 авг 2010 в 15:01

У задачи минимального разреза есть очень интересное применение — сшивка текстур.
Тут статья с SIGGRAPH и куча картинок и видюшек по теме:
www.cc.gatech.edu/cpl/projects/graphcuttextures/

vicnaum 24 авг 2010 в 18:12

Класс.

Склейка панорам в фотошопе по ходу по такому же алгоритму работает (с четкими границами, Seams). Да и не только в нём.

tagir_valeev 24 авг 2010 в 19:06

Кстати, если кому-то потребуется этот алгоритм в реальной жизни, горячо рекомендую реализацию Юрия Бойкова и Владимира Колмогорова. Качать тут:
vision.csd.uwo.ca/code/ (бесплатно для некоммерческого использования).