Примеры к предыдущей лекции (Гранди)

Примеры к перебору и Iterative Deepening

1. Задачка: Про грузовики (рекурсия + меморизация состояний)
2. Задачка: Самый длинный путь в графе (отсечние по ответу)
3. Задачка: Гамильтонов путь в графе (то же, что и предыдущая)
4. Задачка: Чудо-сортировка (Iterative Deepening + отсечение по ответу, или решение Очередью)

Вероятностные алгоритмы

1. Las-Vegas (про самое часто встречающееся число, про подобные прямоугольники, про арифметическую прогрессию)
2. Monte-Karlo (считаем площадь, различие относительной и абсолютной погрешности)

Простые алгоритмы на графах

1. Дейкстра (простая, с кучей, с двух сторон)
2. Форд-Беллман (простой, с break, с очередью, оценка VE/2 в худшем)
3. Флойд (пути длины ровно k, и не менее чем k = возвеедение матрицы в степень)
4. Отрицательный цикл (Флойдом, Форд-Беллманом)
5. MST (Краскал, Прима)
6. Цикл min веса, Цикл min среднего веса

Коммивояжер (Salesman)

1. Док-во невозможности r-приближения при P != NP.
2. Метод Nearest
3. Метод локального спуска
4. Метод 2 MST
5. Метод 3/2 MST (Кристофилдс)

Про отжига, генетику, локальные оптимизации

1. Локальные оптимизации можно запускать из несольких начальных состояний
2. Not read Отжиг для Коммивояжера
3. Not read Генетика = обощение этих методов + можно скрещивать состояния