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

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

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

ИЗМЕНИТЬ >

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

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) Жадный алгоритм подсчета соседних полей имеет смысл для 2-х цветных карт.