我怎样才能减少大小相等的正方形格子降到最低设置矩形？ [英] How can I reduce a grid of equal sized squares to a minimum set of rectangles?

问题描述

如果我有一个大小相等的正方形任意大小的网格（它们之间没有空格），我需要知道一个有效的方式，以减少这些成的最小的一些长方形的，例如，如果每个星号再presents一个正方形，那么这可能会减少到一个大的矩形：

If I have an arbitrary sized grid of equal sized squares (with no spacing between them), I need to know an efficient way to reduce these into a minimum number of rectangles, for example if each asterisk represents a square, then this could be reduced to one big rectangle:

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

虽然这可减少到两个矩形

While this could be reduced to two rectangles:

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

这是显而易见的解决方案是收集相邻方块每一行中，然后收集它们是相同的相邻行。对于我的第二个例子，这会发现三个矩形，这不是很理想。

An obvious solution is to collect adjacent squares in each row, then collect adjacent rows which are identical. For my second example this would find three rectangles, which is not optimal.

  *** (1)

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

  *** (3)

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

I am wondering if there's a more successful and efficient algorithm to do this.

推荐答案

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

I've a gut feeling that this problem can be complex... for example consider

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

最佳的解决方案是4

The optimal solution is 4

   B
   BCC
AAAB
   BDD
   B

但我没有找到一个简单的方法由当地推理A应最后方之前停止预见。在最佳的解决方案A，C和D是非最大矩形和只有B是最大的。情况可能会变得更加复杂，例如有：

but i don't find an easy way to foresee by local reasoning that A should stop before last square. In the optimal solution A, C, and D are non-maximal rectangles and only B is maximal. Things can get even more complex for example with:

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

其中最佳的解决方案是

where the optimal solution is

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

其中只有E是最大的。也期待它实际上是很容易建立任意大的问题，其中最优解所有，但一个矩形的非最大。 当然，这并不意味着IMO没有简单的解决方案存在......就像我说这是一个直觉，但海事组织与最大的矩形的原因是怎么回事，如果需要的绝对最低有问题的任何解决者。

where only E is maximal. Also looks it's actually easy to build arbitrarily large problems where in the optimal solution all but one rectangles are non-maximal. Of course this doesn't mean IMO that no easy solution exists... like I said it's a gut feeling, but IMO any solver that reasons with maximal rectangles is going to have problems if the absolute minimum is needed.

有关几分相似，但也有不同的问题（我正在寻找非必要不相交盘最小覆盖）我用一个缓慢的贪婪办法总是增加了解决方案，是遏制，覆盖大部分还未覆盖的光盘广场。 对于你的问题我可能会看到它是如何工作的，每次增加的最大包含的矩形......这正如上面的例子中然而，这不会是一般的最佳解决方案。

For a somewhat similar but also different problem (I was searching a minimal covering with non-necessarily-disjoint discs) I used a slow greedy approach always adding to the solution the disc that was contained and covering most not-yet-covered squares. For your problem I'd probably see how it works adding the largest contained rectangle every time... that as the examples above show however this is not going to be in general an optimal solution.

这篇关于我怎样才能减少大小相等的正方形格子降到最低设置矩形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！