Я пытаюсь составить список алгоритмов / задач, которые являются «исключительно полезными», например, при решении задач, которые «кажутся» очень экспоненциальными по своей природе, но имеют какой-то особенно умный алгоритм, который в конечном итоге решает их. Примеры того, что я имею в виду:
- Линейное программирование (Симплексный алгоритм имеет экспоненциальное время; поиск решения за полиномиальное время занимал много времени!)
- В более общем смысле, полуопределенное программирование
- Тестирование первичности
- 2-SAT и HORNSAT
- Вычислительные детерминанты (если это не кажется сложным, рассмотрим постоянный)
- Нахождение идеального соответствия
- Разнообразие сложных теоретико-групповых задач, которые можно решить с помощью классификации конечных простых групп
- Множество сложных задач, связанных с графами, которые могут быть решены с помощью сложных характеристик Запрещенных Незначительных (встраиваемость на произвольной поверхности; ограничение ширины дерева и ширины ветви; приводимые графы Дельта-Вая)
- Вычисление экспонент в ограниченной группе (т.е. вычисление inшагов, что достигается путем многократного возведения в квадрат)
- Вычисления, основанные на алгоритме LLL. (Как частный случай: евклидов алгоритм. Как более общий случай: алгоритмы PSLQ или HJLS.)
- Проблемы с ограничениями без терминов Тейлора (?). Я признаю, что не до конца понимаю это, но, похоже, он включает в себя случаи 2-SAT / HORNSAT, описанные выше, и любую линейную алгебру над конечными полями. Смотрите здесь для более длинного поста
- Задачи, вычисляемые с помощью голографических сокращений .
В качестве почетного упоминания я бы также упомянул об изоморфизме графа, потому что он все еще очень прост ( ) и эквивалентен многим другим проблемам изоморфизма:
- Диграфы / мультиграфы / гиперграфы (своего рода «более сложная» проблема)
- Конечные автоматы / CFG
Очевидно, что в этом есть ряд трудностей, но все они оставляют, по крайней мере, у некоторых людей чувство «удивления» в том смысле, что проблема может показаться сложной, но может быть решаемой. LP может показаться относительно простым, но потребовалось много времени, чтобы найти реальное решение. Повторное возведение в квадрат или решение 2-SAT - это то, что магистрант мог бы придумать самостоятельно, но если бы вы только узнали о проблемах NP-Complete, не увидев HORNSAT, это может звучать как естественный кандидат на NP-завершенность. Решение CFSG или наличие полиномиального способа проверки на восстанавливаемость по Дельта-Уаю - это немалые подвиги.
Я надеюсь в этом есть смысл; здесь явно много субъективных признаков, но мне любопытно услышать, что другие люди находят эффективными решениями «очевидно трудных» проблем.
источник
Ответы:
Для меня одним из наиболее эффективных алгоритмов является алгоритм Blossom V, который находит идеальное соответствие с максимальным весом в общем графике:
https://en.m.wikipedia.org/wiki/Blossom_algorithm
источник
Для меня все классические и более современные более эффективные алгоритмы проверки или нахождения минимального остовного дерева (MST) связного гранично-взвешенного графа являются хорошими кандидатами. Многие из этих алгоритмов перечислены в википедии .
На первый взгляд, эта проблема выглядит как проблема коммивояжера, одна из немногих самых известных проблем NP-hard. Самое удивительное, что существуют линейные алгоритмы для проверки MST и множество почти линейных алгоритмов для поиска MST! Фактически, одна из самых известных открытых проблем в алгоритмах - есть ли детерминированный линейный алгоритм для нахождения MST в общих графах. Оказывается, существуют богатые математические и графические структуры и свойства, а также множество практических приложений, связанных с MST, что делает его одной из наиболее приятных и расширяемых тем в курсе информатики. Для немного устаревшего, но очень хорошо написанного всестороннего введения, пожалуйста, проверьте учебник Джейсона Эйснера .
источник