Есть ли другой алгоритм, время выполнения которого в наихудшем случае является экспоненциальным, в то время как на практике он работает очень хорошо, кроме Симплексного алгоритма?

9

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

Существуют ли (детерминированные) примеры для этой ситуации, кроме алгоритма Симплекс?

ds.algorithms Arman
источник
1
Вы можете быть заинтересованы в связанном вопросе: cstheory.stackexchange.com/questions/305/…
Radu GRIGore

Ответы:

13

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

Янне Х. Корхонен
источник
13

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

Суреш Венкат
источник
13

Вывод типа Хиндли-Милнера является EXPTIME-полным, но в программах, которые обычно пишут люди, он довольно близок к линейному.

Нил Кришнасвами
источник
1
Разве это не немного отличается? Насколько я помню, мы могли бы охарактеризовать необходимое условие для плохой работы Хиндли-Милнера (глубоко вложенное позволяет), и поэтому причина, по которой HM хорош на практике, состоит в том, что на практике это вложение ограничено довольно низко (обычно мы отступаем по мере продвижения углубляясь в привязки и нервничая, когда мы направляемся к крайнему правому краю экрана ...) Конечно, я уже делал это утверждение по памяти и совсем недавно не смог восстановить ссылку на него.
Роб Симмонс
2
Нет, это не обязательное условие. Вы можете задать последовательность привязок let (без вложенности!), Чтобы она возводила квадрат в размер выведенного типа с каждой дополнительной записью в последовательности. См. Cstheory.stackexchange.com/questions/2428/… для примера.
Нил Кришнасвами
Пример написан на SML, и я более знаком с тем, как OCaml выполняет свою работу, но если бы эта последовательность привязок была «let», то я думаю, что они были бы вложенными. Только потому, что они определяют глобальные функции, они не являются таковыми, но здесь происходит неявное вложение: данное определение имеет доступ ко всем определениям выше и ни одному из них ниже.
amnn
1
@amnn: упомянутое вложение было вложением, позволяющим в связанной форме - то есть let z = (let y = e in e') in e''в противоположность чем let y = e in let z = e' in e''.
Нил Кришнасвами
9

Программа Брендана Маккея « Красавица» («Нет АВТОМорфизмов, да?») Решает проблему канонической маркировки графов (одновременно решая проблемы изоморфизма графов и автоморфизмов графов) и имеет экспоненциальную производительность в худшем случае (Миядзаки, 1996). Тем не менее, он работает очень быстро для большинства графов, особенно с несколькими автоморфизмами.

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

Деррик Стоули
источник
Я думал, что красавица также использовала некоторую случайность, чтобы помочь в уточнении? В этом случае это может быть очень похоже на симплексный алгоритм (хотя, очевидно, нет понятия сглаженного анализа для изоморфизма графов).
Джошуа Грохов
1
Он не использует случайность, так как он должен сделать последовательную каноническую маркировку. Однако он может использовать пользовательскую процедуру, инвариантную к вершине, чтобы помочь разбить вершины. Иногда этот инвариант выглядит случайным образом, как он был создан (часто это сложная функция для последовательностей степени расстояния), но это просто для уменьшения коллизий.
Деррик Столи
1
Этот вершинно-инвариант можно сравнить с антициклическими правилами симплексного алгоритма.
Деррик Столи
4

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

Питер Шор
источник
1

Есть алгоритм для нахождения смешанных равновесий Нэша, который похож на симплексный алгоритм для LP. (Я забыл название.) Это имеет экспоненциальную сложность наихудшего случая, но у меня есть смутное воспоминание, что он часто ведет себя хорошо на практике.

Уоррен Шуди
источник
Вы имеете в виду алгоритм Лемке-Хаусона?
Рахул Савани
1

Упаковка в бункер (много вариантов) - это проблема, сложность которой, как известно, NP-трудна:

http://en.wikipedia.org/wiki/Bin_packing_problem

Однако многие эвристики применительно к «практическим» версиям работают очень хорошо. Для одномерной упаковки в мусорное ведро некоторые из этих эвристик, например, в первую очередь; уменьшение первой подгонки; наиболее подходящий; наиболее подходящие убытки очень привлекательны для показа студентам. Студенты часто могут открыть для себя некоторые базовые эвристики.

Иосиф Малкевич
источник
Есть много примеров, даже если проблема является NP-полной, простые алгоритмы могут иметь дело с этим. Особенно с алгоритмами приближения. Но я на самом деле ищу алгоритмы экспоненциального времени, ваш пример связан с трудной проблемой, которую легко решить с помощью простых алгоритмов. Может быть, существует экспоненциальный алгоритм времени, чтобы точно решить упаковку бинов (или другую проблему); и на практике это занимает полиномиальное время.
Арман
0

Алгоритм персистентности (происхождение от Edelsbrunner-Letscher-Zomorodian, с множеством изменений с тех пор) является наихудшим кубическим случаем, но, похоже, из экспериментов обычно работает в линейном времени.


источник