我正在尝试找到解决以下问题的算法。
假设我有许多对象 A、B、C、...
我有这些对象的有效组合列表。每个组合的长度为 2 或 4。
例如。AF、CE、CEGH、ADFG、……等等。
对于两个对象的组合，例如。AF，组合的长度为2。对于四个对象的组合，例如CEGH，组合的长度。
我只能选择不重叠的组合，即我不能选择 AF 和 ADFG，因为它们都需要对象“A”和“F”。我可以选择 AF 和 CEGH 的组合，因为它们不需要公共对象。如果我的解决方案仅包含 AF 和 CEGH 两个组合，那么我的目标是组合长度的总和，即 2 + 4 = 6。
给定一个对象列表及其有效组合，我如何选择不相互重叠的最有效组合，以便最大化组合长度的总和？我不想将其表述为 IP，因为我正在处理具有 180 个对象和 1000 万个有效组合的问题实例，并且使用 CPLEX 解决 IP 的速度非常慢。寻找其他优雅的方法来解决它。我可以将其转换为网络吗？并使用最大流算法解决它？还是动态程序？不知道如何解决这个问题。
我第一次尝试证明这个问题是 NP-hard 是错误的，因为它没有考虑到只允许大小为 2 或 4 的组合这一事实。然而，使用Jim D. 的减少3 维匹配(3DM) 的建议，我们可以证明该问题仍然是 NP-hard。
我将展示你的问题的自然决策问题形式（“给定一组对象 O，以及一组来自 O 的 2 个或 4 个对象的组合 C，以及一个整数 m，是否存在 C 的子集 D这样 D 中的所有集合都是成对不相交的，并且 D 中所有集合的并集大小至少为 m？") 是 NP 难的。显然，优化问题（即您的原始问题，我们在其中寻找使上述 m 最大化的实际组合子集）至少与这个问题一样困难。（要看到优化问题并不比决策问题“难”很多，请注意，您可以首先使用对 m 进行二分搜索找到解决方案存在的最大 m 值，其中您在每个步骤中解决决策问题，然后，一旦找到这个最大的 m 值，
给定一个 3DM 的实例 (X, Y, Z, T, k)，其中 X、Y 和 Z 是彼此成对不相交的集合，T 是 X*Y*Z 的子集（即，一组有序的三元组分别具有来自 X、Y 和 Z 的第一、第二和第三分量）并且 k 是整数，我们的任务是确定是否存在 T 的任何子集 U 使得 |U| >= k 并且 U 中的所有三元组都是成对不相交的（即，要回答“T 中是否至少有 k 个不重叠的三元组？”）。要将任何此类 3DM 实例转换为您的问题的实例，我们需要做的就是从 T 中的每个三元组创建一个新的 4 组合，通过向每个三元组添加一个不同的虚拟值。问题的构造实例中的对象集将由 X、Y、Z 和 |T| 的并集组成。我们创建的虚拟值。最后，将 m 设置为 k。
假设原始 3DM 实例的答案是“是”，即 T 中至少有 k 个不重叠的三元组。那么这种解决方案中的 k 个三元组中的每一个都对应于输入 C 中的一个 4 组合。问题，并且这 4 个组合中没有两个重叠，因为通过构造，它们的第 4 个元素都是不同的，并且通过假设。因此，在您的问题实例中至少有 m = k 不重叠的 4 组合，因此该问题的解决方案也必须是“是”。
在另一个方向上，假设您的问题的构造实例的解决方案是“是”，即在 C 中至少有 m 个不重叠的 4 组合。我们可以简单地取 4 个中每个的前 3 个元素-组合（丢弃第四个）以在 T 中生成一组 k = m 非重叠三元组，因此原始 3DM 实例的答案也必须是“是”。
我们已经证明，对一个问题的肯定回答意味着对另一个问题的肯定回答，因此对一个问题的否定回答意味着对另一个问题的否定回答。因此问题是等价的。您的问题实例可以清楚地在多项式时间和空间中构建。因此，您的问题是 NP 难的。