Алгоритмы для NP-трудных задач (2013). Лекция 10
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
10.11.13
Дата публикации:
10.11.13
Код для блога:
Алгоритмы для задачи выполнимости: метод расщепления
DPLL-алгоритмы, основные идеи метода расщепления, вектор и число расщепления. O∗(22n/3) для задачи 3-выполнимости одновыполнимой формулы через расщепление относительно случайной перестановки. Запоминание дизъюнктов: решение задачи выполнимости на формулах константной плотности за O∗((2-c)n). Комбинированные меры сложности, measure and conquer: O∗(22m/5.5) для задачи максимальной 2-выполнимости.
Страница лекции на сайте Computer Science Club
Другие лекции курса
12