Боря программирует

Beam Search

В эвристических контестах есть два алгоритма, которые чаще всего используются. Simulated Annealing (отжиг), о котором я уже писал раньше. И beam search. Расскажу о нем на примере задачи из предыдущего поста.

Допустим мы ищем решение, которое поставит в каждую клетку ровно один штамп (всего получится 7х7=49 штампов). Допустим мы хотим перебрать все возможные такие решения. Переберем все 20 вариантов, какой штамп поставить в клетку (1, 1) и положим получившиеся поля в массив. Потом для каждого такого поля переберем 20 вариантов, какой штамп поставить в клетку (1, 2) и сложим получившиеся варианты в новый массив.

В этом массиве будет уже 400 различных полей, которые можно получить за два хода. Можно было бы так продолжать дальше, но размер этого массива будет расти экспоненциально. Поэтому давайте на каждом шаге оставлять только X лучших полей из массива. Как определять хорошесть полей? Когда мы поставили штампы в клетки (1, 1) и (1, 2), то мы знаем, что значения в этих клетках никогда не поменяются, поэтому можно максимизировать сумму значений в них.

Допустим мы хотим улучшить решение и ставить в каждую клетку от 0 до 2 штампов (но при этом по условию нельзя использовать суммарно больше 81). Как оставлять X лучших решений, если они используют разное количество штампов? Вместо одного вектора на Х элементов, можно сохранить X/81 лучших для каждого количества использованных штампов.

На практике чем больше Х, тем лучше скор вы получите. Поэтому очень важно сделать решение как можно более эффективным.

Например, как выбрать Х лучших полей для следующей итерации? Можно сложить все варианты в вектор, отсортировать, а потом оставить Х лучших. Но гораздо более эффективно добавлять новые элементы в PriorityQueue, которая хранит не больше Х элементов. Тогда для большинства вариантов можно сразу увидеть, что они хуже чем текущий Х-й вариант в PriorityQueue и не добавлять его в новый слой.

Другая важная перформанс оптимизация — хранить в PriorityQueue объекты размера О(1) байт, а не весь стейт целиком. Например, если к полю 9х9 мы применяем штамп размера 3х3, но в итоге пытаемся найти лучшие стейты только исходя из значений в конкретной клетке, то нет смысла копировать весь стейт из 81 интов и применять 9 сложений. Достаточно посчитать значение в конретной клетке и запомнить как восставновить весь стейт целиком.

С аккуратной реализацией этого алгоритма можно было легко попасть в топ-10 AHC 032. Если добавить оптимизацию для правого нижнего прямоугольника 4х3 из предыдущего поста, можно было получить топ-1 скор.

www.tgoop.com/bminaiev_blog/63

2.7K viewsApr 9 at 17:15

Beam Search

В эвристических контестах есть два алгоритма, которые чаще всего используются. Simulated Annealing (отжиг), о котором я уже писал раньше. И beam search. Расскажу о нем на примере задачи из предыдущего поста.

Допустим мы ищем решение, которое поставит в каждую клетку ровно один штамп (всего получится 7х7=49 штампов). Допустим мы хотим перебрать все возможные такие решения. Переберем все 20 вариантов, какой штамп поставить в клетку (1, 1) и положим получившиеся поля в массив. Потом для каждого такого поля переберем 20 вариантов, какой штамп поставить в клетку (1, 2) и сложим получившиеся варианты в новый массив.

В этом массиве будет уже 400 различных полей, которые можно получить за два хода. Можно было бы так продолжать дальше, но размер этого массива будет расти экспоненциально. Поэтому давайте на каждом шаге оставлять только X лучших полей из массива. Как определять хорошесть полей? Когда мы поставили штампы в клетки (1, 1) и (1, 2), то мы знаем, что значения в этих клетках никогда не поменяются, поэтому можно максимизировать сумму значений в них.

Допустим мы хотим улучшить решение и ставить в каждую клетку от 0 до 2 штампов (но при этом по условию нельзя использовать суммарно больше 81). Как оставлять X лучших решений, если они используют разное количество штампов? Вместо одного вектора на Х элементов, можно сохранить X/81 лучших для каждого количества использованных штампов.

На практике чем больше Х, тем лучше скор вы получите. Поэтому очень важно сделать решение как можно более эффективным.

Например, как выбрать Х лучших полей для следующей итерации? Можно сложить все варианты в вектор, отсортировать, а потом оставить Х лучших. Но гораздо более эффективно добавлять новые элементы в PriorityQueue, которая хранит не больше Х элементов. Тогда для большинства вариантов можно сразу увидеть, что они хуже чем текущий Х-й вариант в PriorityQueue и не добавлять его в новый слой.

Другая важная перформанс оптимизация — хранить в PriorityQueue объекты размера О(1) байт, а не весь стейт целиком. Например, если к полю 9х9 мы применяем штамп размера 3х3, но в итоге пытаемся найти лучшие стейты только исходя из значений в конкретной клетке, то нет смысла копировать весь стейт из 81 интов и применять 9 сложений. Достаточно посчитать значение в конретной клетке и запомнить как восставновить весь стейт целиком.

С аккуратной реализацией этого алгоритма можно было легко попасть в топ-10 AHC 032. Если добавить оптимизацию для правого нижнего прямоугольника 4х3 из предыдущего поста, можно было получить топ-1 скор.

BY Боря программирует