algorithm - 如何找到最小数量的分割

Question

假设您有一个 Canvas ，并且在这个 Canvas 中已经有一些对象。你怎么能找到用正方形覆盖“未覆盖”区域的最小方法，而不是相互重叠，完全填满 Canvas 。

在我的例子中，“ Canvas ”是一个 html-div 容器，对象是嵌套的 div-容器。可能看起来像这样:http://www.encodechain.com/demo/200908_optimize.png左边是“开始”，右边是可能的第一个“步骤”……

我知道有一个算法，但目前我不记得这个名字了。

Answer 1

我能找到的最好的是这篇论文:Tiling a rectangle with the fewest squares .这篇论文读起来很有趣，尽管有时它会通过谈论“普遍常数”来深入研究理论领域。我不确定“一个大小为 m×n 的矩形是否可以用 k 个正方形平铺”这个问题是否是 NP 完全的。正如在另一个回复中指出的那样，您的问题类似于 NP 完全的包装问题。而且，当然，您的问题是本文中解决的问题的概括，因为您正在处理非矩形区域。您可以先将区域分成最少数量的矩形，这本身就是另一个有趣的问题。最后，即使您可以高效地做到这一点，我也不确定以最佳方式平铺这些矩形是否会导致整体最佳平铺。

正如作者指出的那样，贪心算法是一个很好的起点:只要放下最大的正方形，直到该区域填满。