Алгоритм - перекрасить сетку цветного прямоугольника за наименьшее количество ходов

Я работаю над программой, которая должна решить "Вирусную игру". Короче говоря, мы получаем доску I x J, заполненную полями, окрашенными из n-элементного цветового пула. Начнем с того, что пометим поле [0,0] как «посещенное». Цель состоит в том, чтобы пометить все поля как посещенные за наименьшее количество шагов, каждый шаг: выбрать цвет из пула и раскрасить им каждое посещенное поле. Затем пометьте каждое поле в регионах, соседних с посещенными полями того же цвета, что и они, как посещенные.

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

Вот ссылка на игру для справки, если мое объяснение непонятно http://www.gry.pl/gra/virus_3


algorithm graph-coloring nearest-neighbor
person Marcin    schedule 13.12.2015    source источник
comment
Посмотрите мой ответ на эту проблему: заголовок stackoverflow.com/questions/32617961/ Это примерно та же игра (Flood-It), но с одним отличием: например. если угловой квадрат оранжевый, квадрат рядом с ним розовый, а квадрат рядом с ним снова оранжевый, то все три квадрата будут преобразованы, если щелкнуть розовый. В версии, на которую вы ссылаетесь, третий квадрат останется оранжевым.   -  person m69 ''snarky and unwelcoming''    schedule 14.12.2015
comment
Этот вопрос, отмеченный как дубликат, вероятно, является моей ошибкой; Извини за это; изначально я не понимал, что правила немного отличаются.   -  person m69 ''snarky and unwelcoming''    schedule 15.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Я совсем забыл об этой игре, в которую любил время от времени играть.

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

person 500 - Internal Server Error    schedule 13.12.2015
comment
Размышляя об этом подробнее, я полагаю, что могут потребоваться более продвинутые эвристики, например, вы пытаетесь сначала направиться к центру доски, и вы можете искать закрытые области, к которым можно получить доступ только после того, как определенные цвета были сыграны, а затем попробуйте открыть те открытые. - person 500 - Internal Server Error; 13.12.2015
comment
Я тоже об этом думал, но проблема в том, что решение, которое мы получаем, не обязательно будет лучшим, а только тем, которое работает (если только мы не превысим лимит ходов, когда лучшее решение уложится в этот лимит, в этом случае это неприемлемый ответ). Я думаю, что хорошей идеей было бы оценивать каждое состояние доски с некоторым счетом (пока не знаю, как это рассчитать) и пытаться улучшать его с каждым ходом. Некоторый возврат также может быть в порядке - person Marcin; 13.12.2015