假设我知道一种算法，该算法将布尔矩阵划分为最小的一组隔离矩形，这些矩形涵盖了所有"一个"(" trues"(。任务是找到矩阵的行和列的排列，以便通过根据排列构建的列和行构建的矩阵可以将其划分为最小的矩形集。
。用于插图，可以这样考虑问题：
假设我有一组对象和一组属性。每个对象都可以具有任何数量的(不同(属性。任务是用最少的句子总结(报告(此映射。每个句子都有一个形式的"
<list of objects> have properties <list of properties>"。
我知道我可以通过应用排列并在每次尝试上运行算法来实现解决方案。但是时间复杂性逐渐爆炸，使得这种方法对于大于15×15的矩阵非实用性。
我知道我可以通过删除重复的行和列来运行算法之前简化矩阵。
这个问题感觉就像是np-hard，并且可能没有快速的(及时(解决方案。如果是这样，我有兴趣了解一些近似解决方案。
这是减少逻辑电路的同构，给定完整的输入(功能(和所需的真实表(行具有哪个功能(。您可以通过经典布尔代数解决问题。该过程称为逻辑优化。
当我上学时，我们在董事会上绘制了Karnaugh地图，并绘制了彩色边界以形成我们的矩形。但是，听起来好像您的董事会要处理的东西大。尝试QM算法和引用的启发式方法，以获取许多应用程序的"足够好"解决方案。
到目前为止我的解决方案：
首先，让我们确认，对于与列交换行(具有对象的功能(，问题是对称的。
让我们表示二进制矩阵的问题，其中行是对象，列是特征，矩阵中的列表示匹配对(对象，功能(。
到目前为止，我的想法是按顺序运行两个步骤，直到矩阵中没有1个步骤：
- 启发式地找到了我可以运行2D最大矩形的行和列的良好的脱落置换
- 找到最大矩形，将其保存到答案列表中，零属于它。
最大矩形问题
它可以简单地是网络上最大矩形问题的任何实现>
取消平息行(和列(
解开行的行与解开列无关，并且两个任务都可以单独运行(同时(。让我们假设我正在寻找列的脱落置换。
另外，值得注意的是，如果我们将矩阵取消展示的矩阵应产生相同的结果，如果我们将矩阵交换为零。
- 构建列的距离矩阵。两列之间的距离定义为以数值表示的两个列之间的曼哈顿距离(即0-对象与特征之间没有关系，1-存在( (
- 使用距离矩阵运行分层聚类。复杂性是o(n^2(，因为我认为单个联系应该足够好。
- 从层次聚类返回的对象的顺序是脱落的置换。
该算法在我的用例中效果足够好。R中的实现可以在https://github.com/adamryczkowski/rectpartitions