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

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

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

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

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

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

  *** (1)

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

  *** (3)

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

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

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

最优解是4

   B
   BCC
AAAB
   BDD
   B

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

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

最优解是

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

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

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