Прямоугольная плитка с плитками фиксированного размера

Question

Я изо всех сил пытался найти удобное решение для следующей проблемы:

Предположим, у нас есть стена данного размера и 4 типа плиток размером 4 x 2, 2 x 2, 2 x 1, 1 x 1. Внутри периметра стены есть определенные прямоугольные области, которые не могут быть плиточный (т.е. отверстия). Существует также особый тип плитки, который имеет переменный размер A x B с A <1. Он используется для заполнения плитки до края прямоугольника, если это необходимо. </p>

Найдите плитку стены, которая учитывает следующие ограничения:

1. Плитки одинакового размера не могут быть размещены одна под другой с одинаковым выравниванием (т. Е. Плитки, появляющиеся в ряду ниже, должны быть смещены таким образом, чтобы не было зазора, который выглядит как крест между соседними плитками одного размер)
2. используется минимальное количество плиток
3. Плитки, которые выходят за границы прямоугольника, будут обрезаны до полей; полученная таким образом неполная плитка будет разбита на более мелкие плитки; Это может включать использование специальной плитки, которая всегда должна располагаться рядом с полем прямоугольника или краем отверстия, где бы ни возникала ситуация

Вот что я пробовал до сих пор:

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

Вполне возможно, что я что-то упустил, или мне не хватило проницательности при изучении вышеперечисленных методов.

С учетом всего вышесказанного, ребята, есть ли у вас какие-либо советы или предложения о том, как приблизиться к этому, что дает результаты?

Это пример тайлинга, который учитывает ограничения 1 и 3, но не является оптимальным

Answer 1

Вам нужна оптимальная плитка, или вы готовы согласиться на "довольно хорошо"?Найти оптимальное решение, скорее всего, чрезвычайно сложно.Интуитивно я бы предложил следующую эвристику:

1. Pretend there are no holes in the wall, tile with large tiles.

2. Remove all tiles which intersect with holes.

3. current_size = largest

4. For each empty space: tile as much as possible with current_size

5. current_size = the size just below current_size

6. return to 4