如何最佳地将向量分组为易于描述的组？

Question

我有一组长度为4的向量（表示为Nx4矩阵），其中向量中的每个元素都可以取-1、0或1。我想将向量分组为最小数量的组（因此也是最大的组），这样每个组都满足以下约束：对于组中向量的每列中表示的每个唯一元素组合，组中必须有一个向量。例如，仅包含向量[-1,1,0,1]和[-1,1,1]的组将满足约束，因为组的每列中有一个唯一值，第三列中有2个，因此每列中有两个唯一值的可能组合，这两个值都在组中表示。但是，分组[1,0，-1,0]和[1,0,0,1]不满足约束条件，因为第3列和第4列中的每个列都有2个唯一的值，创建了4种可能的组合，其中只有2种在组中表示。将[1,0,0,0]和[1,0，-1,1]添加到此组将满足约束条件。（请注意，任何单独作为一个组的向量都将始终满足约束。）

这些组“易于描述”，因为您可以只列出每列的唯一值，这将完全描述组，而不包括所有其他向量。

我的第一个方法是将集合作为一个整体，首先检查它是否已经满足约束。如果没有，请尝试一次删除一个向量，并检查其余向量是否满足约束。如果这些都不起作用，那么尝试删除2个向量的所有组合，然后是3个，依此类推。每次特定子集满足约束时，将这些向量放在一边，并对剩余的向量重复该过程，直到没有剩下的向量。虽然这保证了一个最佳分组（据我所知），但运行时间对于任何具有超过~25-30个向量的集合来说都太长了，因为您必须潜在地检查N选择k种可能的方法，以省略所有向量的子集k的值从1到N-1。

我最近意识到，如果你把可能向量的空间想象成一个3×3×3的超立方体，其中每个单位的超立方体代表一个向量，那么你可以把这看作是一个几何问题。满足约束的组是该空间中的超矩形（包括从-1到1的环绕），这可能比约束的原始措辞更容易考虑。在这个问题的框架中，我在寻找超矩形的最小数量，这样所有向量都包含在超矩形中，并且任何超矩形中都不存在空格。这种方法promise不会组合地分解运行时，但我还没有找到一种好的方法来搜索可能的超矩形。

有人有更快的算法来解决这个问题的想法吗？

Answer 1

首先，让我们谈谈你的第一种方法，它是一种全局贪婪算法。您可以选择迭代可以找到的最大集合。这是一种很好的启发式方法，但不能保证最佳分组。这是一个维度为3的6向量示例（例如，第4个是alwats 0）：

(0, 0, -1); (0, 0, 0); (0, 0, 1); (0, -1, -1); (0, 1, 1); (1, 0, 0)

下面是一些绿色节点超出计划（第6个）的表示。

您的算法将首先选择唯一可用的3组：（0,0，-1）；（0,0,0）；（0,0,1）；（红线）

让3个分离向量意味着总共4个集合。你显然可以用3组2个向量代替（1-4, 2-6, 3-5)。（黑线）

解决这个问题的一个重要问题是知道一个向量是否可以用于两个不同的集合。

如果没有，在我看来这显然是一个NP问题。贪婪算法是最合理的治疗方法。你可以通过构建一个以所有向量为节点，边的意思是“在同一个组中兼容”的图来节省时间，也就是说没有洞使得这种关联不可能。然后你寻找最大的派系。

如果是，我相信你可以用最小成本流算法最优地解决它。您必须列出所有可接受的集合，所有集合都由一个节点表示，该节点链接到具有1成本的源，并将多达81个向量节点倾倒到接收器。有大约V=10000可接受集与81向量呈现。有些算法让你在O（VElogVlogV）中解决这个问题，仍然比a更好！81.幸运的是，一些“洞”下降速度很快。