Плиточный черепица с плитами фиксированного размера
Я изо всех сил пытаюсь найти удобное решение для следующей проблемы:
Suppose we have a wall of a given size and 4 types of tiles of sizes 4 x 2, 2 x 2, 2 x 1, 1 x 1. There are certain rectangular regions inside the perimeter of the wall which can not be tiled (i.e. holes). There is also a special type of tile which has a variable dimension A x B with A < 1. This is used to pad the tiling to the margin of the rectangle, if needed.
Найдите черепицу стены, которая соблюдает следующие ограничения:
- Плитки одинакового размера не могут быть размещены один под другим, с одинаковым выравниванием (т.е. плитки, появляющиеся в строке ниже, должны быть сдвинуты так, чтобы не было зазора, который выглядит как крест между соседними плитами того же размер)
- Используется минимальное количество плиток
- Плитки, которые превышают границы прямоугольника, будут обрезаны до края; изготовленная таким образом неполная плитка будет разбита на мелкие плитки; возможно, это связано с использованием специальной плитки, которая должна всегда располагаться рядом с краем прямоугольника или краем отверстия, где бы ни возникала ситуация.
Вот что я пробовал до сих пор:
- Я рассмотрел алгоритмы для решения этой проблемы с использованием плитки домино, но большинство из них, похоже, не заботятся о том, что процесс черепицы не может создавать промежутки, которые выглядят как крест, где встречаются плитки. Кроме того, для меня проблема кажется немного иной, поскольку существует больше типов плиток, и также кажется, что прямоугольник не нужно заполнять точно (возможно, чтобы небольшие пространства оставались рядом с полями, которые будут заполняться специальными плитами )
- Я попытался сгенерировать все возможные тилинги с использованием технологии ветвей и привязок с обрезкой узлового узла, так что будут добавлены только те состояния, в которых будут добавлены плитки, которые не нарушают ограничений, но это определенно не масштабируется.
- Я также изучал алгоритмы упаковки, но, насколько мне известно, это может привести к определенной черепице, где есть небольшие промежуточные пространства, которые могут оставаться внутри помещений стены.
Возможно, что я кое-что забыл или не имел достаточного понимания, изучая вышеупомянутые методы.
Когда все это будет сказано, есть ли у вас какие-либо намеки или предложения по способу подхода к этому, что дает результаты?
Это пример плитки, которая учитывает ограничения 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
