Я ищу список задач оптимизации NP-hard, где активно изучаются практические эвристики для их решения и существуют общие критерии, которые люди пытаются побить.
Примеры включают в себя: восстановление филогенетического дерева (эвристика, например, здесь ), коммивояжер (не очень активный, но LKH довольно хорошо известен)
Более конкретно, я ищу области исследований, где люди действительно заботятся о конечной стоимости (например, TSP или филогения, упомянутые выше). Например, поиск дерева решений - это не то, что я ищу, так как очень мало людей заботятся о получающейся в результате высоте дерева.
heuristics
usamec
источник
источник
Ответы:
MaxSAT - люди на самом деле заботятся об этом, потому что решатели SAT настолько хорошо развиты, что зачастую лучшим решением для вашей любимой задачи оптимизации NP на практике является сокращение ее до MaxSAT, а затем применение одного из известных решателей. Проверьте конкурс SAT для тестов и т. Д.
Искатели кликов используются в вычислительной биологии и комбинаторике, а эвристические алгоритмы, как я помню, потрясающе хороши.
Обширные части исследования операций посвящены алгоритмам, в том числе эвристическим, для решения случаев целочисленного или смешанно-целочисленного линейного программирования.
источник
Исследование операций имеет множество комбинаторных проблем оптимизации, где разработка эвристики для минимизации (или максимизации) результирующих затрат является очень активной областью.
Например, проблема маршрутизации транспортного средства, проблема маршрутизации с использованием дугового разряда, проблемы минимального остовного дерева и варианты этих проблем.
источник