Семинар 9. Meet-in-the-middle, ДП по подмножествам

Метод Meet-in-the-middle (MitM). Общая идея, важные элементы: ход назад, слияние решений.

Решение пятнашек с <=20 ходов. Двунаправленный BFS.

Задача о рюкзаке. Тривиальный перебор за O(2^N). Перебор с двух сторон, деление предметов на две половины. Слияние за O(K log K): удаление заведомо неоптимальных вариантов, поиск самого большого предмета, которых входит (бин. поиск). Общая сложность O(sqrt(2)^N N).

Дискретное логарифмирование (в цикл. группе G). Основной пример: мультипликативная группа вычетов. Тривиальное решение за O(|G|). Алгоритм Giant-step baby-step: разложение индекса на две части, слияние. Время работы O(sqrt(|G|)).

Задача коммивояжера. Решение перебором за O(N!). Динамическое программирование вперёд, важная информация, состояния. Решение за O(2^N N^2). Детали реализации: подмножество = битовая маска, побитовые операции.