algorithm - 拼图 : for boolean matrix find permutation of rows and colums that allows decomposistion into minimal set of covering rectangles

Question

假设我知道一种算法，它将一个 bool 矩阵划分为一组最小的不相交的矩形，这些矩形覆盖所有“1”(“真”)。任务是找到矩阵的行和列的排列，这样通过根据排列打乱列和行而构建的矩阵可以划分为最小的矩形集。

为了说明，可以这样想这个问题:

Suppose I have a set of objects and a set of properties. Each object can have any number of (distinct) properties. The task is to summarize (report) this mapping using the least amount of sentences. Each sentence has a form "<list of objects> have properties <list of properties>".

我知道我可以通过应用排列并在每次尝试时运行算法来暴力破解解决方案。但是时间复杂度呈指数级增长，使得这种方法对于大于 15×15 的矩阵不实用。

我知道我可以在运行算法之前通过删除重复的行和列来简化矩阵。

这个问题感觉像是 NP-hard，可能没有快速(时间多项式)的解决方案。如果是这样，我有兴趣了解一些近似的解决方案。

Answer 1

给定完整的输入集(特征)和所需的真值表(哪些行具有哪些特征)，这与简化逻辑电路同构。你可以用经典的 bool 代数来解决这个问题。该过程称为 logic optimization .

我上学的时候，我们画了Karnaugh maps在黑板上绘制彩色边界以形成我们的矩形。但是，听起来好像您的东西比板上的一个要大；试试 QM algorithm以及针对许多应用程序“足够好”的解决方案所引用的启发式方法。