День 12. Перебор.

  1. Рекурсия → динамика + profit
    1. Ищем макс клику
    2. Добавляем отсечение запоминанием (мемоизацию). Состояние − множество вершин, один long long.
    3. Доказываем, что время работы стало O(2n/2)
    4. Продолжаем оптимизировать: вершина степени 0, 1, n-1, n-2, min, max

  2. Оптимизации
    1. Отсечение по времени
    2. Предподсчёт всех маленьких задач (в задаче про клику в каждый момент времени остался некоторый граф, за 2n(n-1)/2 можно предподсчитать все мелкие графы)
    3. Отсечение по ответу: оценить максимальную клику, как current + (maxDegree+1)
    4. Проблема спаривания оптимизаций: отсечение по ответу + запоминание
    5. Iterative deepening (собственно оптимизация; объяснение, факта, что время работы всего лишь удвоилось)
    6. Жадность, перебор и промежуточное состояние, iterative deepening по k.
    7. Принципиально другой подход: вместо обхода dfs-ом дерева состояний, из начального жадно идём в глубь в случайную сторону много раз.
    8. Meet-In-The-Middle
    9. A*

  3. Примеры
    1. Гамильтонов путь, начинающийся в 1 (самый длинный путь)
    2. Минимальное контролирующее множество
    3. Решение задачи про машинки (двигаем их, пока все не смогут выехать с автостоянки)

  4. Игра на большом дереве: добавляем random, получаем profit