Ветвление и ограничение - эффективная эвристика для задач поиска, и в Википедии перечислен ряд сложных проблем, где использовались ветвление и привязка. Тем не менее, мне не удалось найти ссылки, позволяющие предположить, что это больше, чем просто «один метод» решения этих проблем.
Как ни странно, я слышал, что некоторые из лучших эвристик для SAT и целочисленного программирования происходят из ветвей и границ, поэтому мой вопрос:
Может кто-нибудь указать мне какие-либо ссылки, подробно описывающие эффективное использование ветвления и связанное с NP-трудными проблемами?
ds.algorithms
reference-request
optimization
heuristics
Суреш Венкат
источник
источник
Ответы:
Для TSP закажите эту книгу ... http://www.tsp.gatech.edu/book/index.html
Насколько я понимаю, нет единого инструмента, чтобы убить их всех. Можно утверждать, что любое рекурсивное решение, развертывающее обратную трассировку и некоторую функцию оценки, использует ветвление и привязку. Как таковая, большая часть решателей в NP трудных задачах использует некоторую форму ветвления и связи.
источник
Проблема разбиения по кликам может быть не самой популярной NP-трудной проблемой, но она была эффективно решена с использованием ветвления и ограничения, см. Эту статью: http://joc.journal.informs.org/content/6/2/141 .абстрактный
источник
Точные Экспоненциальные Алгоритмы - хорошая недавняя книга о таких алгоритмах. Алгоритм X для точной задачи покрытия также полезно знать.
источник