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

Question

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

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

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

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

一个明显的解决方案是收集每行中的相邻方块,然后收集相同的相邻行.对于我的第二个例子,这将找到三个矩形,这不是最佳的.

  *** (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 最大。看起来，实际上很容易构建任意大的问题，其中在最佳解决方案中，除了一个矩形之外的所有矩形都不是最大的。当然，这并不意味着在我看来不存在简单的解决方案......就像我说的那样，这是一种直觉，但在我看来，如果需要绝对最小值，任何用最大矩形进行推理的解算器都会遇到问题。

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