Для каких алгоритмов существует большой разрыв между теоретическим анализом и реальностью?

52

Два способа анализа эффективности алгоритма:

  1. поставить асимптотическую верхнюю границу времени выполнения и
  2. запустить его и собрать экспериментальные данные.

Интересно, известны ли случаи, когда между (1) и (2) существует значительный разрыв. Под этим я подразумеваю, что либо (а) экспериментальные данные предполагают более жесткую асимптотику, либо (б) существуют алгоритмы X и Y, такие, что теоретический анализ предполагает, что X намного лучше, чем Y, а экспериментальные данные предполагают, что Y намного лучше, чем ИКС.

Поскольку эксперименты обычно показывают поведение в среднем случае, я ожидаю, что наиболее интересные ответы относятся к верхним границам среднего случая. Однако я не хочу исключать, возможно, интересные ответы, которые говорят о разных границах, такие как ответ Ноама о Simplex.

Включить структуры данных. Пожалуйста, поставьте один алгоритм / DS за ответ.

оборота Раду ГРИГОРЕ
источник
Было бы полезно, если бы вы пояснили, о каких верхних границах вы говорите. Вы говорите только о проблемах, для которых существует значительный разрыв между наиболее известными верхними и нижними границами для наихудшей временной сложности? Или вы также включаете проблемы, для которых известны жесткие границы сложности времени наихудшего случая, но типичное время выполнения значительно быстрее? Может быть более интересно рассмотреть сглаженную сложность, а не сложность наихудшего случая. Экспериментальные результаты на «типичных» входах или случайных входах мало что могут опровергнуть наличие патологических входов.
Джеймс Кинг
В этом случае я думаю, что есть два вопроса, которые следует задавать отдельно: один о разрывах между сложностью наихудшего случая и сложностью среднего случая / сглаженной, и один о разрывах между теоретической сложностью среднего случая / сглаженной сложности и практическими экспериментальными результатами. Редактировать: вы сделали редактирование, обращаясь к этому, в то время как я писал свой комментарий :)
Джеймс Кинг,

Ответы:

37

Самым ярким примером является, конечно, метод Simplex, который быстро работает на практике, предполагает многозначность, но в теории требует экспоненциального времени. Дэн Спилман только что получил Неванлинну в значительной степени за объяснение этой тайны.

В более общем смысле, многие случаи целочисленного программирования могут быть достаточно хорошо решены с использованием стандартных IP-решателей, например, могут быть решены комбинаторные аукционы для большинства распределений, предпринятых на входах значительного размера - http://www.cis.upenn.edu/~mkearns /teaching/cgt/combinatorial-auctions-survey.pdf

Noam
источник
3
Было ли найдено явное семейство линейных программ, для которых симплекс занимает экспоненциальное время?
Opt
1
Насколько я понимаю, есть много явных семейств, которые требуют экспоненциального времени (например, первое, что дали Клее и Минти: «Насколько хорош симплекс-алгоритм?», 1972). Тем не менее, выбор правила сводки имеет отношение к этим результатам. Я предполагаю, что большинство ссылок на эти результаты можно найти в статье Спилмана и Тенга ( arxiv.org/abs/cs/0111050 ).
MRA
2
@ Сид: Да. куб Кли-Минти: glossary.computing.society.informs.org/notes/Klee-Minty.pdf
в этой статье есть нижние границы для некоторых конкретных правил поворота cs.au.dk/~tdh/papers/random_edge.pdf
Игорь Шинкарь
26

Основания Гребнера . Время работы в худшем случае является двукратно экспоненциальным (по числу переменных). Однако на практике, особенно для хорошо структурированных задач, алгоритмы F4 и F5 эффективны (т.е. завершаются довольно быстро). По-прежнему остается активной областью исследований, чтобы выяснить, какой должна быть правильная гипотеза относительно среднего или ожидаемого времени работы. Предполагается, что это каким-то образом связано с объемом многогранника Ньютона базового идеала.

Жак Каретт
источник
Среднее / ожидаемое при каком распределении? Я думал, что даже определение ожидаемого времени выполнения было трудным для алгебраических задач ...
Джошуа Грохов
1
Я не знаю случаев, быстро решаемых методами F4 и F5, но довольно легко построить систему многочленов с множеством переменных и низкой степенью, которые кодируют экземпляр SAT. В таком случае мне не известно, что алгоритм превосходит DPLL / DPLL +. Я действительно хотел бы знать больше об экспериментальных результатах на этих вещах!
MassimoLauria
@Joshua: на данный момент, любое распространение, которое позволяет результаты ... @Massimo: проблема кодирования X как экземпляра Y почти никогда не побеждает специализированные алгоритмы для X! Но GB и DPLL по существу эквивалентны, поэтому я был бы очень удивлен, увидев эффективную разницу.
Жак Каретт
1
@Massimo: Да, вычисления в GB - это NP-Hard. В зависимости от формулировки. На самом деле, большинство вопросов (завершение, идеальное членство, алгебраически замкнутое поле и логическое) являются полными PSPACE или хуже (EXPSPACE complete). Иными словами, ожидается, что вычисления в ГБ будут намного сложнее, чем задачи, завершенные NP (и даже в среднем случае любой алгоритм для них, такой как F5, скорее всего, не превзойдет DPLL).
Митч
22

O(2((nlogn)))

Я не знаю, есть ли формальный результат в среднем / сглаженная сложность проблемы, но я помню, что читал, что она существовала - возможно, кто-то другой может поспешно указать на формальный результат. Конечно, есть много экспериментальных свидетельств и много быстрых решателей. Мне также любопытно, распространяется ли это свойство на других членов семейства с полным GI.

Ананд Кулкарни
источник
1
O(2nlogn)
2
Ой! Может быть, вы думаете о Бабаи-Кучере, который дает алгоритм среднего случая линейного времени для GI: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Джошуа
Да, Бабай-Кучера - единственный! Спасибо за ссылку.
Ананд Кулькарни
20

От Дэвида Джонсона, расхождение в теоретических и экспериментальных соотношениях аппроксимации: проблема коммивояжера: пример локальной оптимизации, Д.С. Джонсон и Л.А. МакГеох . В этой статье они приводят экспериментальные доказательства асимптотики (поскольку эксперименты достигают размера N = 10 000 000!), Которые не поддаются теоретической асимптотике: алгоритм Джона Бентли «Жадность» или «Многофрагментный» (отношение аппроксимации в худшем случае, по крайней мере, logN / loglogN) побеждает Nearest Insertion и Double MST, оба из которых имеют коэффициенты аппроксимации наихудшего случая 2.

Джошуа Грохов
источник
20

Другим примером, который до недавнего времени не был хорошо понят, является время работы алгоритма k-средних Ллойда , который (с практической точки зрения) был предпочтительным алгоритмом кластеризации в течение более 50 лет. Только недавно, в 2009 году, было доказано ( Ваттани ), что в худшем случае алгоритм Ллойда требует некоторого числа итераций, которое экспоненциально по числу входных точек. С другой стороны, в то же время сглаженный анализ ( Артуром, Манти и Рёглином ) доказал, что сглаженное число итераций является просто полиномиальным, что объясняет эмпирическую эффективность.

MRA
источник
10

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

Раду ГРИГОРЕ
источник
3
Сет Петти доказал, что n операций deque занимают не более O (n alpha * (n)) времени, где «alpha *» - итеративная обратная функция Аккермана, что является довольно небольшим промежутком.
jbapple
9

Есть небольшая проблема с вопросом. На самом деле существует более двух способов анализа алгоритма, и одним из теоретических способов, которым пренебрегали, является ожидаемое время выполнения, а не время выполнения в худшем случае. Это действительно среднее поведение в случае, которое имеет отношение к проведению экспериментов. Вот очень простой пример: представьте, что у вас есть алгоритм для ввода размера n, который занимает время n для каждого возможного ввода размера n, за исключением одного конкретного ввода каждой длины, который занимает время 2 ^ n. Слышать, что время выполнения в худшем случае является экспоненциальным, но средний случай равен [(2 ^ n -1) n + (2 ^ n) 1] / (2 ^ n) = n - (n-1) / 2 ^ n, который ограничения на п. Очевидно, что два типа анализа дают очень разные ответы, но этого следует ожидать, так как мы рассчитываем разные величины.

Выполняя эксперимент несколько раз, даже если мы берем самое большое время прогона для выборки, мы все еще отбираем только небольшую часть пространства возможных входных данных, и поэтому, если трудные случаи редки, то мы, вероятно, пропустим их ,

Относительно легко построить такую ​​проблему: если все первые n / 2 бита равны нулю, то решить экземпляр 3SAT, закодированный с последними n / 2 битами. В противном случае отклонить. Когда n становится большим, проблема имеет примерно то же время выполнения в худшем случае, что и наиболее эффективный алгоритм для 3SAT, где среднее время выполнения гарантированно будет очень низким.

Джо Фитцсимонс
источник
Я уже ответил Джеймсу Кингу выше, что ожидаю, что самые интересные ответы будут касаться ожидаемого времени выполнения. Я отредактирую вопрос, чтобы сделать это более заметным.
Раду GRIGore
9

Вывод типа Дамаса-Милнера доказан полным за экспоненциальное время, и есть легко построенные случаи с экспоненциальным увеличением в размере результата. Тем не менее, на большинстве реальных данных он ведет себя эффективно линейно.

sclv
источник
Есть ли рекомендации, которые вы бы порекомендовали для этого результата? Я хотел бы прочитать больше об этом.
Раду GRIGore
1
Я сам не читал его, но наиболее часто цитируемым документом является Гарри Дж. Марсон, «Разрешимость ML-типирования завершена в течение детерминированного экспоненциального времени», 17-й симпозиум по принципам языков программирования (1990).
sclv
9

PTAS для дерева Штейнера в плоских графах смешно зависит от эпсилона. Однако есть реализация, которая демонстрирует удивительно хорошую производительность на практике.

zotachidil
источник
8

Кучи сопряжения из [1] - они реализуют кучи, где вставка и объединение имеют амортизированную сложность O (log n), но предполагаются равными O (1). На практике они чрезвычайно эффективны, особенно для пользователей слияния.

Я только что обнаружил их только сегодня, читая гл. 5.5 из книги К. Окасаки «Чисто функциональные структуры данных», поэтому я решил поделиться информацией о них.

[1] Fredman, ML, Sedgewick, R., Sleator, DD, и Tarjan, RE 1986. Куча спаривания: новая форма саморегулирующейся кучи. Algorithmica 1, 1 (январь 1986), 111-129. DOI = http://dx.doi.org/10.1007/BF01840439

Blaisorblade
источник
Со времени Окасаки произошли некоторые улучшения, и теперь есть (обязательные) пары связывания с O (0) meld, O (1) insert и findMin, O (lg lg n) lowerKey и O (lg n) deleteMin: arxiv . org / abs / 0903.4130 . В этой куче используется другой механизм сопряжения, чем в исходных кучах Fredman et al.
jbapple
7

В связи с замечанием Ильяраза о ветвлении и связке, Pataki et al. покажите, что уменьшение числа ветвей и границ плюс решетки решает почти все случайные IP-адреса в политизме.

Marco
источник
6

Эвристика Лин-Кернигана для TSP («Эффективная эвристика для задачи коммивояжера», Operations Research 21: 489–516, 1973) очень успешна на практике, но все еще не имеет среднего случая или сглаженного анализа для объяснения ее эффективности. , В отличие от этого, существует сглаженный анализ двухэтапной эвристики для TSP, выполненный Матиасом Энглертом, Хейко Рёглином и Бертольдом Вёкингом (Algorithmica, чтобы появиться).

Бодо Манте
источник
5

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

Ω(nm)

оборота ильяраз
источник
Вы имеете в виду O (мн), или я в замешательстве?
Раду GRIGore
O(nmlog(n2/m))