День 12. Перебор.
- Рекурсия → динамика + profit
- Ищем макс клику
- Добавляем отсечение запоминанием (мемоизацию). Состояние − множество вершин, один long long.
- Доказываем, что время работы стало O(2n/2)
- Продолжаем оптимизировать: вершина степени 0, 1, n-1, n-2, min, max
- Оптимизации
- Отсечение по времени
- Предподсчёт всех маленьких задач (в задаче про клику в каждый момент времени остался некоторый граф, за 2n(n-1)/2 можно предподсчитать все мелкие графы)
- Отсечение по ответу: оценить максимальную клику, как current + (maxDegree+1)
- Проблема спаривания оптимизаций: отсечение по ответу + запоминание
- Iterative deepening (собственно оптимизация; объяснение, факта, что время работы всего лишь удвоилось)
- Жадность, перебор и промежуточное состояние, iterative deepening по k.
- Принципиально другой подход: вместо обхода dfs-ом дерева состояний, из начального жадно идём в глубь в случайную сторону много раз.
- Meet-In-The-Middle
- A*
- Примеры
- Гамильтонов путь, начинающийся в 1 (самый длинный путь)
- Минимальное контролирующее множество
- Решение задачи про машинки (двигаем их, пока все не смогут выехать с автостоянки)
- Игра на большом дереве: добавляем random, получаем profit