Алгоритмы для NP-трудных задач (2013). Лекция 3
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
22.09.13
Дата публикации:
22.09.13
Код для блога:
Точные алгоритмы для задачи коммивояжёра и задачи о гамильтоновом цикле
Метод динамического программирования (время: O∗(2n), память: O∗(2n)).
Метод включений-исключений (время: O∗(2n), память: O∗(1)).
Матрица Татта и перманент, решение для двудольного графа за O∗(2n/2) времени и O∗(1) памяти.
Страница лекции на сайте Computer Science Club
Другие лекции курса
12