Поиск фигур в 2D Array, затем оптимизация

11

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

Найдены нужные шаблоны, но еще не оптимизированы

Мой код перебирает x / y, помечает блоки как используемые, поворачивает форму, повторяет, меняет цвет, повторяет.

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

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

Это очень хорошо ... Что мне теперь делать?

Я думаю, что мне придется

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

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

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

РЕДАКТИРОВАТЬ Несмотря на ясность вопроса, все, кажется, поняли, да,

Я хочу найти максимальные "Т" формы в каждом цвете

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

ассемблер
источник
Жадный алгоритм может разбивать доску на наборы соединенных блоков. Затем для каждой коллекции вы можете попробовать заполнить фигурами и дать оценку заливки в зависимости от количества оставшихся блоков, которые не будут затемнены. Вид заставляет меня думать о en.wikipedia.org/wiki/Knapsack_problem .
Джонатан Коннелл
2
Я думаю, что-то не хватает в вопросе. Вы хотите создать алгоритм, который находит как можно больше «Т» -образных групп?
Маркус фон Броади
Если я вас понимаю, вы идете правильным путем. Вы не очень ясны, и я хотел бы, чтобы вы уточнили.
AturSams

Ответы:

3

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

Если я прав, то, на мой взгляд, оптимальным решением для вашей ситуации является следующее.

Мы будем использовать целочисленное линейное программирование.

Я полагаю, что использовал этот в прошлом:

http://sourceforge.net/projects/lpsolve/

http://lpsolve.sourceforge.net/5.5/Java/README.html

(Вы можете заставить его работать со многими языками, я использовал его с PHP, Java и C)

Что мы сделаем, это зарегистрируем каждую возможную Т-образную форму на доске и затем используем ILP, чтобы максимизировать количество покрываемых блоков. ILP экспоненциально сложен. Учитывая размер вашей доски, это не будет проблемой. Я задал гораздо более сложные вопросы мин / макс на графиках с помощью ILP, и на их заполнение ушли всего лишь доли секунды, а с сотнями вершин - до 30-90 секунд (в вашем случае он падает на доли секунды).

Что я бы порекомендовал сделать:

  1. Найти все возможные формы линий
  2. Найти все пересечения между формами линий одного цвета
  3. Найти все возможные формы Т, ища все пересечения.
  4. Определите логическую переменную в линейной задаче для каждой формы T ( 0 <= Bi <= 1). Поскольку значения являются целыми числами, это оставляет 0 или 1.
  5. Сделайте условия для каждой пары Т форм, которые пересекаются ( Bi + Bj <= 1)
  6. Целевой функцией будет (сумма блоков в «Т» форме (i) * Bi)
  7. Запустите решатель и затемните Т-образные формы, где соответствующие логические значения решателя (где 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 или нет) до оптимальных значений, чтобы максимизировать желаемый результат: затемнение максимально возможного количества блоков без затемнения пересекающихся Т-форм. Если требуемый результат можно рассчитать с помощью линейной функции, когда у вас установлены все переменные, он будет решать ее. В нашем случае мы проверяем, какие Т-формы мы затемнили, и суммируем блоки, которые они покрывают.

введите описание изображения здесь

Я знаю, что это не тривиально, поэтому, если вы решите совершить прыжок, не стесняйтесь комментировать, и я уточню.

AturSams
источник
Спасибо Артур за вашу помощь. Может потребоваться несколько чтений, чтобы переварить. И да, вы правильно поняли проблему. Мне было бы очень интересно, если бы вы уточнили (нет, нет, это не тривиально), но это должно помочь мне добраться туда, куда я иду!
Ассемблер
Какой язык вы используете для реализации?
AturSams
ActionScript 3! всем любимый!
Ассемблер
тоже самое. Я напишу реализацию в as3 и загрузю ее в github для загрузки с комментариями, работая шаг за шагом - я могу сделать это позже сегодня
AturSams
У вас есть какие-то конкретные области 1-7, где вы хотели бы, чтобы я добавил больше комментариев или уточнил? Кстати, хорошие новости для нас, любителей AS3, Adobe выпустила FlasCC, которая поддерживает C ++, чтобы мы могли с легкостью использовать существующие линейные решатели. :)
AturSams
4

Как только у вас есть список всех (возможно перекрывающихся) Т-форм, встречающихся в вашей сетке, у вас остается проблема упаковки с максимальным набором .

В общем, это NP-полная проблема. Однако ваша сетка достаточно мала (и, как правило, разбивается на еще более мелкие независимые подзадачи), так что вполне возможно получить точные решения.


Приложение: Вот базовый алгоритм поиска в обратном направлении, который может помочь:

function max_packing_recursive ( set A, set S, set M ):
    if |M| < |S| then let M = S;
    for each shape X in A do:
        remove X from A;
        let B = A;
        remove all shapes that intersect with X from B;
        if |M| < |B| + |S| + 1 then:        // upper bound
            let M = max_packing_recursive( B, S + {X}, M );
        end if
        if |M| >= |A| + |S| then return M;  // shortcut
    end for
    return M;
end function

function max_packing( set A ):
    return max_packing_recursive( A, {}, {} );
end function

Здесь, {X, Y, Z}обозначает множество , содержащее элементы X, Yи Z{}быть пустое множество), и |Q|обозначает размер набора Q.

В рекурсивной функции набор Aсодержит фигуры, доступные для оставшегося решения, Sсодержит фигуры в текущем решении-кандидате и Mявляется максимальным решением на данный момент (которое вы можете сохранить как глобальную переменную, а не возвращать его обратно в цепочка вызовов). Важная оптимизация находится в строке, отмеченной значком // upper bound, который удаляет ветви дерева поиска, которые не могут вернуть лучшее решение, чем M.

( На самом деле, так как мы знаем , что каждый Т-образный содержит ровно четыре сайты, гораздо лучше , верхняя граница может быть получена путем замены |B|с числом различных сайтов , охватываемых форм в B, разделенных на четыре и закругленные вниз (и аналогично для |A|на линия, помеченная знаком // shortcut). Однако приведенный выше алгоритм работает для произвольных наборов фигур.)

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

Илмари Каронен
источник
Да, я думаю, что он мог бы использовать ILP, чтобы решить ее относительно безболезненно из-за масштабов проблемы. 2 ^ 20 ~ = 1 000 000, так как T-образных форм может быть только столько, он должен использовать линейный решатель для этого. , Это явно экспоненциально сложно (по крайней мере, пока кому-то не удастся доказать, что p = np). Размер позволяет избежать эвристики в этом относительно простом случае.
AturSams
Илмари, большое спасибо. Этот ответ тоже займет несколько раз, чтобы понять. Бит произвольной формы вполне может быть полезен в будущих итерациях.
Ассемблер