Перебор (СПБГУ МатМех, март 2013, спецкурс 344-й группы)

1. Графы и динамика
1. Динамика на ацикличном графе (на примере задачи "самый длинный путь в ацикличном графе")
2. Дейкстра с кучей (задача поиска кратчайшего пути)
3. Почему нельзя также найти самый длинный простой путь? Отрицательные ребра, отрицательные циклы.
4. Поиск гамильтонова пути рекурсивным перебором.
5. Поиск гамильтонова пути рекурсивной динамикой.
2. Простейшие читы в полном переборе
1. Предподсчет (количество простых путей из точки (0,0) длины N)
2. Отсечение по времени (к задаче гамильтонова пути)
3. Запоминание (задачи: гамильтонов путь, максимальный путь, про котят). Получаем ленивую динамику.
3. Общая задача на языке графов
1. Найти какой-нибудь путь из s в t.
2. Найти кратчайший путь из s в t.
3. Найти количество путей из s в t.
4. Граф, возможно, содержит циклы
5. Если граф ацикличен, мы знаем решение всех трех задач за O(E)
6. Если цикличен, то за O(E), O(ElogV) и O(E) (проверить на наличие цикла, если есть, ответ -- бексонечность)
7. Нас интересуют решения за o(E) (т.к. граф огромен)
4. Отсечения для задачи о гамильтоновом пути
1. Запоминание
2. Идти в вершину минимальной степени
3. Начинать из случайно вершины несколько раз
4. Отсечение "если конец точно не достижим, выйти"
5. Пример1: задача обхода конем шахматной доски
6. Пример2: гамильтонов путь в произвольном графе
5. Решение перебором задачи поиска кратчайшего или максимального пути (на примере задачи про зеркала)
1. Базовое решение: полный перебор
2. Добавили запоминание: maxF[state] = D(s, state) = "расстояние от начала до state". Теперь в глубину мы идем только если функция улучшается.
3. Другой способ: maxF[state] = D(state, t) = "расстояние от state до конца". Теперь, если мы зашли в состояние, где уже были, ответ уже известен.
4. Отсечение по ответу: пусть есть оценка F(state) ≥ D(state, t), тогда если D(s, state) + F(state) ≤ best, можно сразу выйти.
5. Отсечение по ответу работает лучше, если ответ посчитан более точно. Как посчитать ответ наиболее точно?
1. Перебирать ребра из текущего состояния в правильном порядке. Чтобы среди первых был ответ близкий к оптимуму.
2. Iterative Deepening. Перебираем ответ внешним циклом for.
6. Делаем дерево перебора более равномерным
1. У нас уже есть сортировка ребер в каждой вершине.
2. Если из каждой вершины перебирать только одно (лучшее) ребро, мы получим жадность.
3. Если перебирать все ребра, то дерево перебора будет похоже на "куст"
4. Будем перебирать лучшие k ребер.
5. Как выбрать k? while (not TimeLimit) k++;
6. Алгоритм A*
1. Задача: есть две вершины -- s и t, нужно найти кратчайший путь от s до t.
2. Dijkstra на плоскости: куча по ключу D(s, v) + distance(v, t)
3. Картинка, показывающая, что до некоторых вершин мы вообще не дойдем (идем почти по прямой)
4. Переписываем перебор, как Dijkstra по величине D(s, v) + F(state)