0

我目前有一个正方形和一系列以下大小的矩形：(225,300)、(225,450)、(450,225)、(300,225)

我需要设计一个算法来确定这个正方形中所有可能的块组合而不重叠，总是填充整个盒子并假设每个块有无限数量。目前是否有任何算法可以有效地处理这个问题？

4

2 回答 2

3

在文献中，有效地=多项式。

请注意，即使您知道可以完全填充正方形 - 找到所有可能的方法也是指数级的，因为其中有指数级。

看看 6K * 6K 板。填充它的一种方法是将其减少到所有大小为 6*6 的 K^2 子方格，对于每个子方格，您可以使用 (6,3) 或 (3,6) 来创建它 - 导致2^(K^2)可能的填充方式广场。（我们仍然没有涵盖所有可能的方法）。

因此，生成所有解决方案不能多项式（=有效）完成。
我会寻求一些回溯/详尽的搜索解决方案来检查所有可能的 placemenets 以获得所需的结果。

原始答案，忽略特定问题中的一些问题，并面临更普遍的变化（给出的板是矩形，而不是正方形，瓷砖不是固定尺寸）：

但是，确定是否有任何可能的方法可以完全填充方形矩形1的问题是NP-Hard ，在这个线程中讨论了它的一个私有案例（给定一个“板”和一个可能的大小为 nxm 的矩形），并且被证明是 NP-Hard，因此对于这个问题没有已知的多项式解。

由于确定是否存在任何可能的平铺是 NP-Hard 的，因此也不能多项式地找到所有平铺（或什至其中之一）（除非P=NP，但大多数人认为不太可能）。

(1) 原始答案写成正方形，但假定为矩形。对于正方形，可能更容易找到一个答案，并且减少不成立。

于 2012-12-25T13:18:28.553 回答
1

如果只用四种矩形来填充正方形，我们就可以解决这个问题。

输入： N
输出：确定维度为 N 的正方形是否可以用矩形 (3,4)、(3,6)、(6,3) 和 (4,3) 填充。

答案是真的当且仅当

  1. N 为正整数
  2. N mod 6 == 0

以下是我的解释。

  1. N 应该是整数，因为我们无法通过整数相加得到分数。
  2. 如果 N mod 6 == 1，那么这个正方形的面积 mod 6 == 1。
    如果 N mod 6 == 2，那么这个正方形的面积 mod 6 == 4。
    如果 N mod 6 == 3，那么这个正方形的面积 mod 6 == 3。
    如果 N mod 6 == 4，那么这个正方形的面积 mod 6 == 4。
    如果 N mod 6 == 5，那么这个正方形的面积 mod 6 == 1。
    由于每个给定矩形的面积都是 6 的倍数。不可能用这些矩形填充这些正方形。
  3. 如果 N mod 6 == 0，那么我们可以用 (3,6) 或 (6,3) 填充这个正方形。
于 2012-12-25T15:58:43.340 回答