我有一个二进制矩阵 n*m（0 和 1）。问题是用元素全为 1 的非重叠框覆盖所有 1。
例子：
1111
0110
0110
框可以用每个坐标中的坐标和长度来表示(x,y,lx,ly)。此示例包含 2 个框{ (0,0,1,4), (1,1,2,2) }。
我正在寻找如何用最少的盒子找到封面。
谢谢
问问题
889 次
2 回答
1
我的问题领域是计算化学，我们在那里解决巨大的多变量问题。这里有两种通用的全局优化算法，它们也已成功应用于包含数万个原子的系统：
a) 遗传算法
http://en.wikipedia.org/wiki/Genetic_algorithm
b) 模拟退火
http://www.gnu.org/software/gsl/
ftp://ftp.alumni.caltech.edu/pub/ingber
http://www.taygeta.com/annealing/simanneal.html
http: //www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PARSA/
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx
这两种算法都有很好的公共领域实现和很好理解的最优性。
于 2011-05-20T06:01:44.900 回答
0
这个问题称为直线多面体的划分。在评论中发布的类似问题 biziclop有一个很好的答案。
算法的思想是将问题简化为二分图的最大匹配（顶点是可能的切割。）
3D
我最初的问题是 3D 中的相同主题。该版本显示为NP-complete：-/
经过一些研究，我根据 Anuj Jain 的论文中描述的启发式实现了解决方案：
于 2014-08-23T09:32:12.823 回答