algorithm - 如何以最佳方式将向量分组到易于描述的组中？

Question

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

这些组“很容易描述”，因为您只需列出每一列的唯一值，这将完整描述该组，排除所有其他向量。

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

我最近意识到，如果您将可能向量的空间想象成一个 3 x 3 x 3 x 3 的超立方体，其中每个单位超立方体代表一个向量，那么您可以将其更多地视为一个几何问题。满足约束的组是该空间中的超矩形(包括从 -1 到 1 的环绕)，这可能比约束的原始措辞更容易考虑。在这个问题的框架中，我正在寻找最小数量的超矩形，使得所有向量都包含在超矩形中，并且任何超矩形中都不存在空白。这种方法有望不会以组合方式扩展运行时，但我还没有想出一种搜索可能的超矩形的好方法。

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

Answer 1

首先，让我们谈谈您的第一种方法，它是全局贪婪算法。你挑选出你可以迭代找到的最大集合。这是一个很好的启发式方法，但不能保证最佳分组。这是维度 3 中的 6 向量示例(例如，第 4 个始终为 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 成本的源并注入(inject)多达 81 个向量节点，将它们自己注入(inject)汇点。有大约 V=10000 个可接受的集合，其中包含 81 个向量。一些算法可以让你在 O(VElogVlogV) 中解决这个问题，仍然比 !81 好。幸运的是，一些“洞”会快速降低 V。