Мощные алгоритмы, слишком сложные для реализации

67

Какие алгоритмы законной полезности просто слишком сложны для реализации?

Позвольте мне прояснить: я не ищу алгоритмы, такие как текущий асимптотический алгоритм оптимального умножения матриц (Coppersmith-Winograd), который разумно реализовать, но имеет константу, которая делает его бесполезным на практике. Я ищу алгоритмы, которые могли бы иметь практическую ценность, но настолько сложны для кодирования, что они никогда не были реализованы, реализованы только в крайне искусственных условиях или только для приложений исключительно специального назначения.

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

ds.algorithms ds.data-structures big-list implementation Elliot Jans
источник

1

делая это CW, так как это может быть длинный список.

Суреш Венкат

4

Есть ли показатель «практически невозможно реализовать»? Есть ли теория, которая определяет это?

Ритвик Бозе

@Mechko, возможно, нижняя граница для размера самой маленькой машины Тьюринга, которая выводит описание машины Тьюринга, которая является реализацией алгоритма. :)

Раду GRIGore

@Radu GRIGore - это приемлемая метрика или она должна быть разработана? Я полагаю, что (на данный момент) есть простая, неподвижная строка, которая определяет «ме, не стоит» ...: D

Ритвик Бозе

4

Меня интересует предположение, что Копперсмит-Виноград целесообразно реализовать. Кто-нибудь когда-нибудь видел реализацию, записанную даже в псевдокоде высокого уровня, и кто-нибудь когда-нибудь оценивал константы?

Рафаэль

33

Шазель дала линейный алгоритм времени для триангуляции простого многоугольника . Скиена писал (стр.575, Руководство по разработке алгоритмов), что «достаточно безнадежно реализовать, что его можно больше рассматривать как доказательство существования»

Ярослав Булатов
источник

3

Имеет ли алгоритм разумные константы?

Jbapple

Это единственный известный линейный алгоритм времени для задачи?

Томас Ахле

2

@ThomasAhle Я считаю, что это единственный известный детерминистический линейный алгоритм времени. У Амато, Гудрича и Рамоса есть более простой случайный случай

Сашо Николов

Насколько мне известно, алгоритм триангуляции простого многоугольника Чазеля с линейным временем никогда не был реализован и, вероятно, никогда не будет реализован из-за его сложности, а также из-за высоких констант, поэтому он не сможет конкурировать с альтернативами на практике. Основное теоретическое достижение, хотя. Ральф Боланд

Ральф Боланд

Спрошу еще раз: есть ли у алгоритма разумные константы?

user1271772

29

Алгоритм Риш для вычисления элементарных первообразных. Согласно Wikipedia, ни один программный пакет, как известно, не реализует полный алгоритм из-за его сложности.

Марк Рейтблатт
источник

3

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

SCLV

Что такое эвристика? Можете ли вы дать ссылку, чтобы узнать больше об этом?

Зигимантус

22

Любой алгоритм, который использует результаты Робертсона-Сеймура, чтобы вывести алгоритм «polytime» для вещей, включающих графы, которые исключают фиксированное второстепенное, вызывает проблемы. Константа, скрытая в их результате, является «галактической».

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

3

Это тоже сложно реализовать или просто имеет огромную константу?

Лев Рейзин

5

Да, это не похоже на хороший пример. Если я правильно понимаю, вопрос заключается в алгоритмах, которые могут быть практичными (а следовательно, «малыми» константами), но слишком сложными для реализации. Конечно, весь вопрос открыт для разных толкований :-)

Арьябхата

5

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

Суреш Венкат

2

Например, мы даже не знаем список исключенных миноров для графов, встраиваемых в тор.

Деррик Столи

17

Проблема здесь кажется более глубокой: не существует эффективного способа создания списка несовершеннолетних, так что это на самом деле не дает алгоритма вообще. Большинство минор-замкнутых свойств дают бесконечный список исключенных миноров, если переводить логическое выражение напрямую. Теорема Робертсона-Сеймура (гипотеза Вагнера) говорит нам, что в этом бесконечном списке скрывается конечный список исключенных несовершеннолетних, но теорема абсолютно не помогает в их фактическом поиске. Поэтому Робертсон-Сеймур обычно приводит к чистому доказательству существования.

Андрас Саламон

16

$O(n)$ $O(\frac{\log^2 n}{B})$ $B$

Работа занимает 55 страниц, и в ее заключении отмечены некоторые улучшения констант, которые автор не описывает из-за нехватки места. Это заставляет меня подозревать, что, возможно, константы не столь галактичны, и что эта структура данных будет иметь «законную полезность», тем более, что она упоминалась много раз.

оборота jbapple
источник

12

Алгоритм унификации паттернов высших порядков линейного времени Qian никогда не был реализован из-за его сложности AFAIK.

Доминик Маллиган
источник

К счастью, для этого есть практические алгоритмы. В справочнике по автоматическим рассуждениям сказано, что это можно сделать за многочасовое время (прямо там, где цитируется алгоритм Цяня), так что это довольно круто.

Джейк

11

Алгоритм линейного времени, чтобы проверить, может ли граф быть встроен в фиксированную поверхность.

Кен-ичи Каварабаяши, Боян Мохар, Брюс А. Рид: Более простой алгоритм линейного времени для вложения графов в произвольную поверхность и род графов ограниченной ширины дерева. ФОКС 2008: 771-780.

Боян Мохар: Линейный алгоритм времени для вложения графов в произвольную поверхность. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

кто то
источник

1

Это вряд ли будет иметь практическое значение, даже если оно будет реализовано из-за большой экспоненциальной (sic) зависимости от рода.

Джеффс

8

Я не уверен, насколько это может быть полезно на практике (хотя я думаю о сворачивании и сравнении белков, а также о предсказании вторичной структуры РНК), но Вольфганг Хакен дал первый алгоритм за ~~полиномиальное время~~ для определения, является ли узел простая петля ( Theorie der Normalflächen. Acta Math. 105, 1961, pp. 245–375). Насколько я помню, он все еще слишком сложен, чтобы его можно было реализовать все эти десятилетия спустя.

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

Энтони Лабарре
источник

4

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

Джеффс

3

Разложение дерева ~~и, возможно, кучи Фибоначчи~~ .

Питер Бут
источник

14

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

Дэвид Эппштейн

1

Я написал пакет, чтобы найти декомпозицию дерева, и я не думаю, что сложно реализовать yaroslavvb.blogspot.com/2011/01/building-junction-trees.html

Ярослав Булатов

2

Мой код - это просто эвристическое разложение по дереву, не оптимальное, как подходы с ветвлением и связью и динамическое программирование ... Я предполагаю, что вы имели в виду "Алгоритм линейного времени ..." Бодлендера? Я не видел никаких реализаций этого

Ярослав Булатов

4

2^{O (k^{3})} O (n)

$2^{O(k^3)} O(n)$

3

Я думаю, что это лучшее усилие по реализации: hein.roehrig.name/dipl

Диего де Эстрада

1

Идеальная конструкция хэша ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) будет применяться к любому сценарию использования со статическими или редко меняющимися ключами (например, доменные имена верхнего уровня на маршрутизаторах, ключевые слова в компиляторах или имена функций в стандартных библиотеках) но в прошлый раз я не смог найти никаких реализаций.

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

$k$ $n$ $O(n \log n + k)$ $O((n+k) \log n)$

Кевин А. Вортман
источник

1

Я отказываюсь верить, что конструкция FKS слишком сложна для реализации. Это на самом деле довольно просто. Может быть, не практично, но, конечно, не слишком сложно для реализации.

Сашо Николов

Мощные алгоритмы, слишком сложные для реализации

Ответы: