它确实是 NP 难,而且由于它具有高科技应用,因此即使在专利中也没有合理有效的近似策略,更不用说发表的论文了。
在有限的预算下,你能做的最好的事情就是从限制问题开始。假设所有矩形都完全相同,假设所有作为标准矩形的二进制细分的矩形也是允许的,因为您可以有效地预先打包它们以适应您的核心划分。对于额外的点,您还可以形成几个固定模式,用于粘合核心矩形以覆盖一些具有显着不同比例的较大形状。假设您可以更改标准矩形/单元格的尺寸,只要其余部分(预包装和粘合模式)保持不变 - 这为您提供了参数来根据您给出的矩形确定核心矩形的近似大小。
现在您可以使用纵横比来近似这种有限系统可以保证的错误。对于第一次迭代,假设使用简单的细分模式可以有 50% 的错误,然后更改模式以减少错误,但不会增加预打包的渐近复杂度。在一天结束时,您总是只是将给定的矩形分配给您预先计算且现在固定的网格和二进制细分 - 这意味着您根本不尝试进行布局或回溯 - 您总是对第一个近似值感到满意适合网格。
努力定义与您的架构很好地打包的矩形类 - 这再次保持整个过程颠倒 - 你永远不会试图真正适应你所得到的 - 你正在定义你必须得到什么才能很好地完成它 -然后您将其余部分视为错误,因为它是近似值。
然后你可以尝试做更多,但不多——任何滑入回溯或确定任意小错误,这是指数级的。
如果您在研究机构并且可以获得一些超级计算机时间 - 在那里运行一组带有病态混合的详尽搜索,以查看最佳包装的外观,并查看您是否可以导出更多细分模式和/或矩形集的类。
对于头 2 年或研究来说,这应该足够了 :-)