algorithm - 如何将大小相等的正方形网格减少为最少的矩形集？

Question

如果我有一个由大小相等的正方形组成的任意大小的网格(它们之间没有间距)，我需要知道一种有效的方法将它们减少为最小数量的矩形，例如，如果每个星号代表一个正方形，那么这可以简化为一个大矩形:

*****
*****
*****

虽然这可以减少为两个矩形:

  ***             ***
*****   =>  **(1) ***(2)
*****       **    ***
  ***             ***

一个明显的解决方案是收集每一行中相邻的方 block ，然后收集相同的相邻行。对于我的第二个示例，这将找到三个矩形，这不是最优的。

  *** (1)

***** (2)
*****

  *** (3)

我想知道是否有更成功、更高效的算法来做到这一点。

Answer 1

我有一种直觉，这个问题可能很复杂......例如考虑

   *
   ***
****
   ***
   *

最优解为4

   B
   BCC
AAAB
   BDD
   B

但我没有找到一种简单的方法来通过局部推理来预见 A 应该在最后一个方格之前停止。最优解中A、C、D是非极大矩形，只有B是极大矩形。事情会变得更加复杂，例如:

   *
   ***
****
   ***
   *
 *****
  * *
  * *

最优解在哪里

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

其中只有 E 是最大的。另外看起来实际上很容易构建任意大的问题，在最佳解决方案中，除了一个矩形外，所有矩形都是非最大的。当然，这并不意味着 IMO 不存在简单的解决方案......就像我说的那样，这是一种直觉，但 IMO 如果需要绝对最小值，则 IMO 任何使用最大矩形推理的求解器都会出现问题。

对于一个有点相似但又不同的问题(我正在搜索一个最小覆盖与非必要不相交的圆盘)我使用了一种缓慢的贪婪方法总是将包含的圆盘添加到解决方案中并覆盖大多数尚未覆盖的圆盘广场。对于您的问题，我可能会看到它是如何工作的，每次都添加最大的包含矩形...正如上面的示例所示，但这通常不是最佳解决方案。