平鋪矩形具有固定尺寸的瓷磚

Question

我們一直在努力以發現以下問題方便的解決方案：

假設我們有一個給定尺寸的壁和4種尺寸的瓦片的4×2,2×2 ，2 x 1，1 x 1。牆壁周邊有一些矩形區域，不能平鋪（即孔）。還有一種特殊類型的瓦片，其具有可變尺寸A×B和A < 1.如果需要，這用於將平鋪塊填充到矩形的邊緣。

查找，尊重以下約束壁的平鋪：

相同尺寸的

1. 瓷磚不能放置一個在另一個之下，具有相同的取向（出現在一個行即瓷磚下面要被移位，使得不存在間隙，它看起來像大小相同的鄰接瓦）
2. 瓦片的最小數目被用來
3. 瓷磚超出矩形的邊界將被修剪到邊界之間的交叉;這樣產生的不完整的瓷磚將以較小的瓷磚破碎;這可能可能涉及使用特殊的瓷磚應該始終坐在旁邊的矩形的邊緣或孔的邊緣，無論形勢可能出現

這是我到目前爲止已經試過：

1. 我已經研究了使用多米諾骨牌瓷磚解決此問題的算法，但大多數似乎並不在意平鋪過程不能產生間隙，看起來像瓷磚交叉的十字。此外，對我來說，問題似乎有點不同，因爲有更多類型的瓷磚，並且它似乎也不需要精確填充矩形（小空間可能會保留在邊緣附近，而使用特殊瓷磚填充）
2. 我試圖使用狀態節點修剪使用分支和綁定技術來生成所有可能的平鋪，以便僅添加那些不打破約束的平鋪添加的狀態將被探索，但這絕對不是可伸縮的。
3. 我也研究過包裝算法，但就我所知，這可能會導致某些平鋪，其中有可留在牆內的小的未處理空間。

我可能有可能忽略了某些事情，或者在探索上述技術時沒有足夠的洞察力。

所有這些都說了，你們有任何提示或建議的方式來處理這產生的結果？

This is an example of a tiling which respects constraints 1 and 3, but is not optimal

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