Элемент 2D-сортировки
Сегодня у меня нет готовой идеи, поэтому давайте обсудим недоделанную.
В игре The Farmer Was Replaced есть подигра, в которой вы сажаете кактусы. Довольно сложное описание правил игры сводится к довольно простой идее: чтобы сбор кактусов был эффективным, необходимо отсортировать 2D-матрицу высот кактусов. Т.е. кактусы становятся больше, когда вы двигаетесь вверх или вправо.
И, конечно, есть ограничения. Вы можете перемещать агента (дрона), и он может менять местами под собой кактус с соседними кактусами. Это предотвращает обмены на большие расстояния, типичные для традиционных алгоритмов сортировки, таких как быстрая сортировка или сортировка слиянием, и дает временную сложность O(n³) для n, длины стороны квадратного поля.
В игре есть глобальная таблица лидеров и первое место составляет 17 секунд на поле 8х8. Моя лучшая попытка на данный момент — 24,3 с. Это 2D-модификация сортировки вставкой, которую я публиковал здесь некоторое время назад.
И сегодня я попробую подход, изображенный на картинке. C — текущая позиция дрона. Остальные буквы - это соседи. Идея, которую я хочу проверить:
- напишите небольшую оптимальную процедуру, которая сортирует крест по порядку
- сканируем поле, применяем алгоритм к каждой ячейке
- запустить сортировку вставкой
Моя интуиция подсказывает, что эта «кросс-локальная оптимизация» может дешево переместить кактусы далеко как в горизонтальном, так и в вертикальном направлении, и она должна снять часть нагрузки с сортировки вставкой.