Мне только что разрешили изображение ... На изображении ниже из моей игры показаны затемненные блоки, которые были признаны частью формы "Т". Как можно видеть, код затемнил блоки красными пятнами и не увидел «Т» формы с зелеными контурами.
Мой код перебирает x / y, помечает блоки как используемые, поворачивает форму, повторяет, меняет цвет, повторяет.
Я начал пытаться исправить эту проверку с большим трепетом. Текущая идея состоит в том, чтобы:
- цикл по сетке и запишите все вхождения шаблона (НЕ отмечая блоки как используемые), и поместите их в массив
- снова пройдитесь по сетке, на этот раз отметив, какие блоки заняты какими шаблонами и, следовательно, какие заняты несколькими шаблонами.
- снова проходя по сетке, на этот раз отмечая, какие шаблоны препятствуют, какие шаблоны
Это очень хорошо ... Что мне теперь делать?
Я думаю, что мне придется
- Попробуйте различные комбинации противоречивых форм, начиная с тех, которые сначала мешают большинству других моделей. Как мне подойти к этому?
- используйте рациональное, которое говорит, что у меня есть 3 конфликтующие фигуры, занимающие 8 блоков, и фигуры по 4 блока в каждой, поэтому я могу иметь максимум две фигуры.
(Я также намереваюсь включить другие формы, и, вероятно, будет взвешивание баллов, которое необходимо учитывать при прохождении конфликтующих фигур, но это может быть другой день)
Я не думаю, что это проблема упаковки мусорного ведра, но я не уверен, что искать. Надеюсь, что это имеет смысл, спасибо за вашу помощь
РЕДАКТИРОВАТЬ Несмотря на ясность вопроса, все, кажется, поняли, да,
Я хочу найти максимальные "Т" формы в каждом цвете
(потому что если бы я дал вам очки на двоих, а вы заработали три, вы бы немного рассердились)
Ответы:
Давайте посмотрим, правильно ли я понял, блоки, помеченные красным цветом, были синего цвета, а алгоритм нашел форму Т и пометил их красным, верно? Ваша цель состоит в том, чтобы найти как можно больше Т-образных фигур с одинаковыми цветными блоками, надеюсь, пока это правильно. В настоящее время вы выделяете их, как только найдете, и это снижает полезность алгоритма (поскольку вы можете упустить оптимальное решение). Вы планируете искать все фигуры, а затем выбирать, какие из них использовать, а какие не использовать. Я правильно до сих пор? Потому что вы хотите максимизировать количество блоков, которые содержатся внутри формы Т, когда алгоритм будет выполнен.
Если я прав, то, на мой взгляд, оптимальным решением для вашей ситуации является следующее.
Мы будем использовать целочисленное линейное программирование.
Я полагаю, что использовал этот в прошлом:
http://sourceforge.net/projects/lpsolve/
http://lpsolve.sourceforge.net/5.5/Java/README.html
(Вы можете заставить его работать со многими языками, я использовал его с PHP, Java и C)
Что мы сделаем, это зарегистрируем каждую возможную Т-образную форму на доске и затем используем ILP, чтобы максимизировать количество покрываемых блоков. ILP экспоненциально сложен. Учитывая размер вашей доски, это не будет проблемой. Я задал гораздо более сложные вопросы мин / макс на графиках с помощью ILP, и на их заполнение ушли всего лишь доли секунды, а с сотнями вершин - до 30-90 секунд (в вашем случае он падает на доли секунды).
Что я бы порекомендовал сделать:
0 <= Bi <= 1
). Поскольку значения являются целыми числами, это оставляет 0 или 1.Bi + Bj <= 1
)Это ценные знания, я часто использовал линейные решатели для рабочих проектов.
ILP - это в основном способ решения задач выбора, когда вы хотите достичь максимума или минимума для некоторой линейной функции.
Вы можете прочитать больше здесь, используя Integer Linear Programming и Linear Programming - это то же самое для программиста, что Integer намного сложнее для компьютера, что может привести к длительной работе. Не в вашем случае, это очень просто и должно занять менее миллисекунд в худшем случае.
Я думаю, вы могли бы прочитать больше здесь:
http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns
Это хорошо объясняет:
http://fisher.osu.edu/~croxton_4/tutorial/
Это в основном решение проблем, как принимать решения, которые максимизируют желаемый результат. Это предполагает, что функция, которая оценивает результат, является линейной, что в вашем конкретном текущем случае является. Функция, которая оценивает результат в этом случае, суммирует блоки для всех Т-образных форм, которые вы решили затемнить.
Математически, как установить переменные: в нашем текущем случае логические значения (затемнил ли я Т-образную фигуру с индексом i или нет) до оптимальных значений, чтобы максимизировать желаемый результат: затемнение максимально возможного количества блоков без затемнения пересекающихся Т-форм. Если требуемый результат можно рассчитать с помощью линейной функции, когда у вас установлены все переменные, он будет решать ее. В нашем случае мы проверяем, какие Т-формы мы затемнили, и суммируем блоки, которые они покрывают.
Я знаю, что это не тривиально, поэтому, если вы решите совершить прыжок, не стесняйтесь комментировать, и я уточню.
источник
Как только у вас есть список всех (возможно перекрывающихся) Т-форм, встречающихся в вашей сетке, у вас остается проблема упаковки с максимальным набором .
В общем, это NP-полная проблема. Однако ваша сетка достаточно мала (и, как правило, разбивается на еще более мелкие независимые подзадачи), так что вполне возможно получить точные решения.
Приложение: Вот базовый алгоритм поиска в обратном направлении, который может помочь:
Здесь,
{X, Y, Z}
обозначает множество , содержащее элементыX
,Y
иZ
(с{}
быть пустое множество), и|Q|
обозначает размер набораQ
.В рекурсивной функции набор
A
содержит фигуры, доступные для оставшегося решения,S
содержит фигуры в текущем решении-кандидате иM
является максимальным решением на данный момент (которое вы можете сохранить как глобальную переменную, а не возвращать его обратно в цепочка вызовов). Важная оптимизация находится в строке, отмеченной значком// upper bound
, который удаляет ветви дерева поиска, которые не могут вернуть лучшее решение, чемM
.( На самом деле, так как мы знаем , что каждый Т-образный содержит ровно четыре сайты, гораздо лучше , верхняя граница может быть получена путем замены
|B|
с числом различных сайтов , охватываемых форм вB
, разделенных на четыре и закругленные вниз (и аналогично для|A|
на линия, помеченная знаком// shortcut
). Однако приведенный выше алгоритм работает для произвольных наборов фигур.)Возможная дополнительная оптимизация, которую я не реализовал выше, заключалась бы в проверке в начале рекурсивной функции,
A
делит ли она на несколько независимых подмножеств, в том смысле, что никакие фигуры в разных подмножествах не перекрываются, и, если это так, примените алгоритм для каждого из подмножеств в отдельности. (В любом случае, вы определенно захотите сделать это хотя бы один раз на верхнем уровне, прежде чем вызывать рекурсивный алгоритм.)A
Также может помочь правильная сортировка фигур перед их зацикливанием, например, в возрастающем порядке по количеству перекрывающихся фигур. ,источник