Алгоритм для заполнения непрямоугольного 2D-пространства тайлов меньшими 2D-формами на основе плиток

Question

Я пытаюсь выяснить, как мне поступить при написании алгоритма (на C #), который при задании:

• Набор, как правило, небольших фигур на основе плиток.Часто 2х2, но не всегда.Иногда фигуры могут быть 2x1 или непрямоугольными.

• Карта листов (двумерный массив), в которой определенные плитки помечены как «свободные», а некоторые плитки «зарезервированы».Свободные плитки обозначают область, в которой разрешено перемещаться фигурам на основе плиток, зарезервированные плитки не могут быть заняты фигурами.

Пример формы на основе плиток, отличной от 2x2s: http://img850.imageshack.us/img850/9057/awk.png

Пример «доступного пространства» в карте тайлов: http://img641.imageshack.us/img641/8263/spaceh.png

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

По сути, алгоритм должен размещать фигуры в доступном пространстве, смещенные к вершине.Решение, которое оно предлагает, не обязательно должно быть «идеальным», но оно должно всегда быть в состоянии найти решение, если оно существует.Также мне бы очень хотелось, чтобы в этом алгоритме не использовались псевдослучайные числа.Я хочу, чтобы он всегда находил одно и то же решение при одном и том же входе, даже если это решение не самое лучшее.

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

РЕДАКТИРОВАТЬ: о, и формы могут быть перевернуты как горизонтально, так и / или вертикально, но не повернуты.Забыл упомянуть об этом.

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

Answer 1

Кнут написал статью под названием «Танцующие ссылки», например, по номеру http://arxiv.org/pdf/cs.DS/0011047, об упрощенной версии поиска с возвратом.Он использует его, например, для того, чтобы покрыть плоскость многоугольниками.Я думаю, что это может быть использовано для решения вашей проблемы - за определенную плату.Я подозреваю, что если существует действительно общий метод для решения вашей проблемы, он также может быть применен к Кнуту, что делает маловероятным, что он будет найден.Конечно, ваши формы проще, чем у Кнута, поэтому, возможно, есть какой-то метод, специфичный для вашей задачи, который более эффективен.

Answer 2

Как подозревает templatetypedef, эта проблема сложна из-за сокращения планарного SAT 1-в-3.

Танцующие ссылки не подходят, если вы не хотите, чтобы все возможные решения и формы не повторялись. Предполагая, что вам нужно одно решение, в котором фигуры могут повторяться, и что экземпляры не слишком велики по сравнению с вашим образцом, я бы порекомендовал динамическое программирование. Чтобы разбить конкретное пространство на части, разделите его на три подпространства A, B, C так, чтобы A и C были непустыми и никакое размещение не могло перекрывать A и C одновременно. Постарайтесь свести к минимуму размер B. Для каждого подмножества S из B (все 2 ^{| B |} из них) попытайтесь рекурсивно покрыть объединение A S и отдельно объединение C (B минус S). Если найдены решения для одного и того же S, их можно объединить. В противном случае, нет решения. Обращайтесь с базовыми корпусами грубой силой.