Как оптимально решить головоломку с заливкой?

Question

Мне нравится играть в головоломку Flood-It, в которую можно играть онлайн по адресу:

https://www.lemoda.net/javascript/flood-it/game.html

Он также доступен в виде гаджета iGoogle. Цель состоит в том, чтобы заполнить всю доску наименьшим количеством последовательных заливок.

Я пытаюсь написать программу, которая может оптимально решить эту головоломку. Как лучше всего подойти к этой проблеме? В идеале я хочу использовать алгоритм A *, но я понятия не имею, какой должна быть функция, оценивающая количество оставшихся шагов. Я написал программу, которая проводила поиск грубой силы глубиной 4, чтобы максимизировать заполненную область. Он работал достаточно хорошо и побеждал меня при решении головоломки, но я не совсем удовлетворен этим алгоритмом.

Есть предложения? Заранее спасибо.

Answer 1

В качестве эвристики вы могли бы построить график, где каждый узел представляет собой набор смежных квадратов одного цвета, и каждый узел связан с теми, к которым он прикасается. (Каждое ребро взвешено как 1). Затем вы можете использовать алгоритм поиска пути, чтобы вычислить «расстояние» от верхнего левого угла до всех других узлов. Затем, просматривая результаты заливки с использованием каждого из 5 других цветов, определите, какой из них минимизирует расстояние до «самого дальнего» узла, поскольку это, вероятно, будет вашим узким местом.

Добавьте результат этого вычисления к числу выполненных к настоящему времени заливок и используйте его в качестве эвристики A *.

Answer 2

Пройдя несколько раз в игре, я заметил, что хорошей стратегией является всегда идти "вглубь", чтобы выбрать цвет, который идет дальше всего на незагрязненную территорию.

Answer 3

Наивным «жадным» алгоритмом является выбор следующего шага, который максимизирует общий периметр основного региона.

(Несколько умных друзей подумали об этом на днях и решили, что оптимиум может быть NP-сложным (например, вы должны использовать его грубо) - я не знаю, верны ли они (не было рядом) услышать рассуждения и сам не продумал их).)

Обратите внимание, что для вычислений шагов я предполагаю, что алгоритм поиска объединения - ваш друг, он делает вычисление «одного шага» очень быстрым (см., Например, этот пост ).

Answer 4

A * - это просто приоритетный поиск графа. Каждый узел является игровым состоянием, вы ранжируете узлы на основе некоторой эвристики и всегда расширяете узел с наименьшей ожидаемой конечной стоимостью. Пока ваша эвристика не недооценивает затраты, первое найденное решение гарантированно будет оптимальным.

Пройдя несколько раз в играх, я обнаружил, что, пытаясь сверлить в противоположный угол, все углы, как правило, приводят к победе. Таким образом, хорошая начальная оценка стоимости будет (стоимость пока) + достаточное количество заливок, чтобы достичь противоположного угла [примечание: не минимальное, просто достаточное. Просто жадно заполняйте угол, чтобы вычислить эвристику].

Answer 5

Ответ Smashery может быть слегка изменен. Для оценки общего количества ходов, если на максимальном расстоянии имеется «k» цветов, добавьте «k-1» к оценке количества ходов.

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

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

Answer 6

Я работал над этим, и после того, как я получил работу своего решателя, я взглянул на подходы, которые использовали другие.

Большинство решателей есть эвристические и не гарантируют оптимальность. Эвристика смотрит на количество квадратов и распределение оставленных цветов, или на расстояние до «самого дальнего» квадрата. Комбинация хорошей эвристики с ограниченной DFS (или BFS с упреждением) приводит к решениям, которые достаточно быстры для стандартной сетки 14x14.

Я выбрал немного другой подход, потому что меня интересовал поиск доказуемо оптимального пути, а не просто «хорошего». Я заметил, что пространство поиска на самом деле растет намного медленнее, чем фактор ветвления дерева поиска, потому что там довольно много повторяющихся позиций. (При стратегии глубокой разработки важно поддерживать историю, чтобы избежать лишней работы.) Эффективный коэффициент ветвления кажется ближе к 3, чем к 5.

Стратегия поиска, которую я выбрал, состоит в том, чтобы выполнить BFS до глубины «средней точки», где число состояний станет недостижимым, где лучше всего работать где-то между 11 и 13 ходами. Затем я проверяю каждое состояние на глубине средней точки и выполняю новую BFS, начиная с нее в качестве корня. Оба этих поиска BFS могут быть сокращены путем устранения состояний, найденных на предыдущих глубинах, а последний поиск может быть ограничен глубиной наиболее известного решения. (Эвристика, примененная к порядку поддеревьев, рассматриваемых на втором этапе, вероятно, также поможет некоторым.)

Другой метод сокращения, который оказался ключом к быстрому решению, - это просто проверка, осталось ли больше N цветов, если вы находитесь на N или менее шагах от текущего лучшего решения.

Как только мы узнаем, какое состояние средней точки находится на пути к оптимальному решению, программа может выполнить DFS, используя это состояние средней точки в качестве цели (и обрезая любой путь, который выбирает квадрат не в средней точке). Или это может быть выполнимо просто создать пути в шагах BFS за счет некоторой дополнительной памяти.

Мой решатель не суперскоростной, но он может найти гарантированное оптимальное решение всего за пару минут. (См. http://markgritter.livejournal.com/673948.html, или код в http://pastebin.com/ZcrS286b.)

Answer 7

Вот идея реализации графа для поддержки Эвристики Smashery .

Представляет каждую группу смежных квадратов одного цвета в непересекающемся множестве и список смежных групп квадратов. Заливка заливки объединяет набор со всеми смежными наборами и объединяет списки смежности. Эта неявная структура графа позволит вам найти расстояние от верхнего левого угла до самого дальнего узла.

Answer 8

Я не уверен, но я вполне уверен, что это можно решить с жадностью. Вы пытаетесь уменьшить количество цветовых полей до 1, поэтому сокращение большего количества цветовых полей не должно быть менее эффективным, чем уменьшение меньшего количества ранее.

1) Определить коллекцию существующих групп одного цвета.

2) Для каждой коллекции подсчитайте количество соседних коллекций по цвету. Масса этой коллекции - наибольшее количество соседних коллекций с одним цветом.

3) Возьмите коллекцию с наибольшим количеством соседей одного цвета и заполните ее этим цветом. Объедините коллекции и обновите сортировку для всех коллекций, затронутых объединением (все новые соседи объединенной коллекции).

В целом, я думаю, что на самом деле это должно вычисляться за время O (n log n), где n - это количество пикселей, а log (n) - только при сохранении отсортированного списка весов.

Я не уверен, нужен ли тай-брейк для случаев, когда несколько полей имеют одинаковый вес. Возможно, тай-брейк подходит к цвету, который характерен для большинства групп на карте.

В любом случае, обратите внимание, что цель игры состоит в том, чтобы уменьшить количество отдельных цветовых полей, а не максимизировать периметр, поскольку различные цветовые схемы могут иногда делать большее поле неоптимальным выбором. Рассмотрим поле:

3 3 3 3 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

Цвет 1 имеет самый большой периметр по любым показателям, но цвет 2 является оптимальным выбором.

EDIT>

Поцарапайте это. Пример:

3 1 3 1 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

Аннулирует мой собственный жадный алгоритм. Но я не уверен, что это простой обход графа, так как изменение цвета, разделяемого двумя соседями, посещает 2 узлов, а не 1.

Устранение цвета, вероятно, должно играть определенную роль в эвристике.

1) Никогда не правильно заполнять цветом, которого еще нет на графике.

2) Если есть одно поле цвета с уникальным цветом, для него потребуется как минимум одна заливка. Он не может быть связан с другими заполнениями. Я думаю, это означает, что заполнять его безопасно раньше, чем позже.

3) Жадный алгоритм подсчета соседних полей имеет смысл для двухцветной карты.

Answer 9

Наивной эвристикой может быть использование оставшегося количества цветов (минус 1) - это допустимо, потому что потребуется всего столько кликов, чтобы убрать доску.

Answer 10

Я думаю, вы могли бы рассмотреть количество квадратов, которые соответствуют или не соответствуют текущему цвету. Таким образом, эвристическим показателем «расстояния» будет количество квадратов на доске, которые не совпадают с выбранным вами цветом, а не количество шагов.