Блог

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

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

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

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

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

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

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

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

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

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

 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