Уважаемые гуру, привет!
Есть популярная игрушка, для которой "популярного" названия я не знаю — видел её как "Color Cubes", "Brick Breaker", "Cube Crasher". Вот онлайновый пример.
Судь такая — прямоугольное поле, скажем, 20*30 заполняется квадратами 4 или 5 цветов. За каждый ход можно снимать группы квадратов одного цвета. Группой считаются соседствующие (по стороне) квадраты, т.е.:
1 2 1 1 1 2 2 1 3 3 3 2 2 1 1
Здесь есть одна группа цвета 2 из 5 квадратов и 3 группы цвета 1, из 4, 2 и 1 квадрата.
За снятые группы начисляются очки — причём обычно гораздо выгоднее снимать большие группы — впрочем прогрессия варьируется обычно вместе с правилами, например она может расти как N^2 или 2^N-1.
В некоторых вариантах снимать группы из 1 кубика нельзя, в некоторых даже из 2. В некоторых за это штраф и т.п.
Заинтересовал вопрос — есть ли алгоритмическое решение которое позволяет для заданной начальной ситуации определить последовательность ходов, ведущей к максимально возможному результату (или сам максимальный результат)?
Или же с ростом размеров поля только эвристические решения возможны, неоптимальные?
Допускаю что это может зависеть от варианта правил, в частности от прогрессии очков.
В общем, подскажите если кто-то встречался, пожалуйста!
На Белорусской республиканской олимпиаде 2006 года была такая задача. К сожалению найти архив сейчас не могу, но, насколько я помню, лучшее решение жюри было рекурсивное удаление самых маленьких кучек, цвета с минимальным количеством оставшихся кубиков.
Спасибо, интересно!
А не сможете ли, пожалуйста, припомнить — нужно ли было просто максимальное количество "насчитать" чтоб задачу сдать — или посылки разных участников сравнивались в смысле "чья программа больше очков набирает"?
Кажется было около 20 тестов различных и несколько эвристических решений жюри. Для каждого теста был вычислен какой-то максимальный балл. Решения участников оценивались исходя из этого балла, и, если я ничего не путаю, на некоторых тестах участники набрали даже больше чем жюри. Прогрессия в той задаче была квадратичная.
Огромная благодарность!
Фактически это как раз вся инфа которая нужна, всё что хотел узнать!
В приведенном примере оптимальность достигается минимальным количеством ходов, как я понял. Если удалять по многу, то и бонус лучше, хотя это зависит от конкретного бонуса, конечно. Думаю, может так быть, что оптимальное решение оставляет несколько кубиков лежать.
Наверняка решается и брутфорсом (так чтобы дожить можно было). Сейчас потыкал немного, выходит в среднем 20-25 ходов, если постараться — меньше. Худший случай это когда перебор будет удалять сверху вниз по три штуки, это N * M/3 ходов. В этом же худшем случае на первом ходу будет N*M/3 групп, которые можно попробовать удалить. На каждом шагу так или иначе придется пару тройку раз пройти по всей таблице, т.е. выполнить нечто O(NM) (выбрать группы для удаления, посчитать очки, которые за это можно получить, сгенерировать таблицу "после хода"). Ну и обновлять ответ, если нашелся лучше чем текущий.
Итого если совсем грубо брать верхнюю границу и вообще убрать все константы, полученные из всяких сумм рядов, будет, наверное, O(N*M*(NM/3)^(NM)). Это, конечно, не очень круто, однако если поставить максимальную глубину обхода 40-50 (вряд ли за ней какое то оптимальное решение, когда решаешь хорошо, удалять приходится по многу, тот же худший случай вместо NM/3 оптимально решается гораздо быстрее, насколько зависит от кол-ва цветов) и вспомнить, что реальная доска весьма далека от худшего случая, то во всяком случае если надо, то попытаться написать стоит, вполне возможно что на маленькой доске (как в примере) допилится до работающего за секунду в большинстве случаев. A*, к сожалению, не катит — придется хранить кучу таблиц.
Если это нужно использовать для какой то игры (вывести подсказку как лучше сходить и т.д.) доску можно соответствующим образом перемешать, чтобы уж точно не тормозило при поиске.
Нет, это поиски материала для мини-соревнования постороннего. Конечно правильно подготовленные доски и в этом случае актуальны :)
За анализ спасибо — примерно те же соображения у меня витали, хотя без таких подробностей — ну мне как раз желательно чтобы с точным и оптимальным решением всё было сложно :D
Думаю, что задача NP полная. Так как для Н = 1 уже нужно использовать ДП от границ и дополнительных параметров.
В общем случае задача точно NP-трудна, вроде бы MAX-SAT к ней легко сводится:
-- запретим удаления одиночных;
-- сделаем для инстанса MAX-SAT табличку с n = количество переменных * C1, m = количество клауз * C2 (C1 и C2 потом подгоним);
-- для каждой переменной будет одноцветная строка; между строками и столбцами будут "прослойки" из разноцветных клеток (переменная-строка проходит через прослойку);
-- идея в том, что удаление переменной == merge, если переменная входит в клаузу с отрицанием; иначе, merge если и только если она не удалена. Можно сделать например следующим образом.
Для отрицания:
Без отрицания:
Все '.' разноцветные, x — цвет клаузы, y — цвет переменной. Во второй конструкции надо ещё избавиться от разрыва переменной, это делается добавлением дополнительных строк в конец и связыванием переменных через них с помощью отдельных столбцов.
-- В итоге надо подогнать размеры столбцов-клауз так, чтобы стоимость полностью собранной клаузы перевесила всё остальное. С экспоненциальными стоимостями это просто.
Конструкция громоздкая и только для общего случая, но частные случаи наверняка тоже NP-трудны (по крайней мере, если можно запретить удалять одиночные клетки). Впрочем, разнообразные эвристические брутфорсы должны здесь очень хорошо работать.