Практичны ли какие-либо современные алгоритмы максимального потока?

30

Для решения проблемы максимального потока , кажется, существует ряд очень сложных алгоритмов, по крайней мере один из которых был разработан совсем недавно, в прошлом году. Макс Орлина течет за O (MN) времени или лучше дает алгоритм, который работает в O (VE).

С другой стороны, алгоритмы, которые я чаще всего вижу реализованными, таковы (я не утверждаю, что провел исчерпывающий поиск; это просто случайное наблюдение):

  • Эдмондс-Карп: ,O(VE2)
  • Push-релабель: или O ( V 3 ) с использованием выбора вершины FIFO,О(В2Е)О(В3)
  • Алгоритм Диника: .О(В2Е)

Являются ли алгоритмы с лучшим асимптотическим временем выполнения просто непрактичными для размеров задач в реальном мире? Кроме того, я вижу, что «Динамические деревья» задействованы в довольно многих алгоритмах; они когда-либо использовались на практике?

Примечание: этот вопрос был первоначально спросил на переполнение стека, здесь , но мне сказали , что это будет лучше подходит здесь.

РЕДАКТИРОВАТЬ : я задал связанный вопрос на cs.stackexchange , в частности, об алгоритмах, которые используют динамические деревья (иначе говоря , деревья среза ссылок), которые могут быть интересны для людей, следующих за этим вопросом.

ds.algorithms graph-algorithms application-of-theory max-flow Роб Лахлан
источник
1
Говоря в общем смысле, является ли алгоритм «практичным» по сравнению с «реализованным», это немного отличается. в идеале авторы должны были бы выпускать реализации своих собственных алгоритмов, и в этом случае их было бы "практично" использовать. Несомненно, это часто более исключение в литературе TCS. но его часто не «практический» , чтобы «реализовать» другие авторы алгоритмы только дают описания в работах , написанных в псевдокоде, которые иногда значительно или очень сложные ... успешная реализация включает в себя хорошую проверку на корректность, процесс иногда пугающий ...
ВЗН
3
У Эндрю Голдберга была очень хорошая кодовая база для различных вариантов максимального потока, основанная на его работе с push-релаксом. Я использовал код в прошлом, и он был очень чистым. К сожалению, сайт, кажется, больше не существует.
Суреш Венкат
3
@vzn Меня интересует, пригодны ли алгоритмы для практической реализации. Есть алгоритмы, которые этого не делают, и некоторые люди привыкли называть эти «галактические алгоритмы», потому что они имеют отличное асимптотическое поведение, но слишком много накладных расходов, и в настоящее время нет практической выгоды для их реализации. (Термины более низкого порядка имеют значение, в конце концов.) Умножение матриц - лучший пример, который я могу себе представить, где асимптотически лучшие решения никогда не видят практического применения. Мне любопытно, является ли Макс поток похожей ситуацией.
Роб Лахлан
5
является ли алгоритм «практичным» по сравнению с «реализованным», это немного отличается. - Это правильно. Алгоритм может быть реализован без практичности, но не наоборот.
Джефф
2
Вот код из Экспериментального исследования алгоритмов минимального разреза .
Остин Бьюкенен

Ответы:

22

Я являюсь одним из авторов статьи, указанной выше.

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

Я также хотел бы добавить, что в этом узком (но все же практическом) контексте часто алгоритмы, которые хорошо работают, имеют плохие теоретические гарантии. Например, ссылка [5] из нашей статьи (алгоритм Бойкова-Колмогорова) широко используется в сообществе компьютерного зрения, но не имеет сильно ограниченного времени выполнения.

Наконец, если кому-то интересно, данные наших экспериментов доступны здесь: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html.

Код также скоро будет доступен.

Дхрув Батра
источник
очень аккуратно, что вы присоединились к группе! Добро пожаловать! один вопрос о статье [с момента ее нахождения]. было бы очень интересно услышать больше о процессе выбора алгоритмов, используемых в статье, - он, похоже, не в полной мере остановился на этом. может быть, вы могли бы где-нибудь поделиться «закулисными» справочными заметками [например, веб-страница?] о том, какие алгоритмы были выбраны, а какие опущены, почему, какие проблемы возникали при получении / запуске реализаций, что вы думаете о более экзотическом такие алгоритмы, как недавний Орлин и их перспективы для возможной реализации, и так далее!
vzn
7

Есть несколько способов ответить на этот вопрос, но не обязательно согласованный ответ. как правило, алгоритмы, которые были реализованы и выпущены для публичного распространения, являются «практическими». однако, некоторые алгоритмы, которые были разработаны, но еще не реализованы, могут быть практичными, но, так сказать, «у них нет присяжных» **.

Хорошая стратегия для практических целей - поискать опрос. Кроме того, для тех, кто интересуется практическими алгоритмами, сравнительные тесты с данными реального мира могут быть отличным ориентиром в отношении их ожидаемого поведения в реальном мире.

сравнительного опроса может быть достаточно, но это приведет к ошибкам в пользу жизнеспособных алгоритмов. это недавний, тщательный эмпирический анализ 14 «современных» алгоритмов максимального потока, сравнительно эмпирически сопоставленных со случаями обработки зрения, где у максимального потока много применений. «Уровень техники» используется для обозначения «реализованных» алгоритмов.

[1] Возвращение к MaxFlow: эмпирическое сравнение алгоритмов Maxflow для задач с плотным зрением , Верма и Батра, 2012

** некоторые теоретические алгоритмы относятся к категории, которая все чаще в сообществе TCS неофициально упоминается как «галактическая», но, к сожалению, авторы TCS в настоящее время прямо не маркируют свои алгоритмы в этой категории, и не существует опубликованных или общепринятых критериев для «Галактические» алгоритмы, хотя есть ссылки в блогах .

практичность в этом смысле, возможно, является новым зарождающимся измерением для теоретического изучения. в идеале было бы исследование алгоритмов максимального потока конкретно по этой «практической» оси / критериям, но, скорее всего, этого не было на момент написания. это более недавно признанная / признанная концепция в TCS, которая еще не была полностью формализована (в отличие, например, от широко распространенного признания алгоритмов P как «эффективных»).

ВЗН
источник
3
+1. Я не уверен, почему это было понижено; Я читаю статью, на которую вы ссылались, и она очень помогла мне найти практические подходы, по крайней мере, в этой проблемной области.
Роб Лахлан
3
Роберт Седжвик сказал в своем недавнем выступлении, что разработчик алгоритма, который не проводит эксперименты, рискует потеряться в абстракции. Речь идет о поиске путей в графах, и в некоторой степени также связана с maxflow. Это не отвечает на вопрос, но может быть кому-то интересно.
Juho
5
@Rob, единственная релевантная часть в этом ответе - это ссылка на статью, и в ответе мало что объясняется, почему эта статья вообще связана. Я предполагаю, что ОП нашел ссылку на Google и не прочитал ее. Остальная часть ответа - это некоторые общие замечания и комментарии, излагающие личную точку зрения О.П. по вопросам, в отношении которых он не является экспертом и не имеет к этому никакого отношения. Ответы не являются сообщениями в блоге. Ссылка на соответствующий документ может быть хорошим комментарием, но не дает ответа. Это плохой ответ, если он один. Вот почему я проголосовал за это.
Каве
2
@ Достаточно справедливо. Я нашел эту статью полезным индикатором того, что люди считают практически полезными алгоритмами. Я согласен, что многое осталось без ответа.
Роб Лахлан
3
Я тоже не понимаю отрицательных голосов. Нет никаких оснований полагать, что автор НЕ прочитал связанную статью, и она, похоже, актуальна. Я вижу желание не повышать, но не понижать.
Суреш Венкат