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

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

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

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

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

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

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

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

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

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

Я не уверен, но вполне уверен, что эту проблему можно решить жадно. Вы пытаетесь уменьшить количество цветных полей до 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) Жадный алгоритм подсчета соседних полей имеет смысл для двухцветной карты.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

After playing the game a few times, I noticed that a good strategy is to always go "deep", to go for the colour which goes farthest into the unflooded territory.

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

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

.