4

几个月前有一个关于“ 1:n 匹配问题”的好问题，似乎没有多时间算法。

我想添加约束以使用多项式算法找到 1:n 匹配问题的最大匹配。我想说：“对于顶点 A1，如果顶点尚未取自另一个 A 顶点，请选择 {B1,B2,B5} 或 {B2,B3}”，即我不会允许所有可能的组合。

如果我们为每个选择引入辅助顶点 H 并用树替换边 => 我们会遇到类似于普通二分匹配的问题，则可以表达这一点。A 或 B 的每个顶点在匹配中只能有一条边。H 中的顶点到或来自顶点的边要么全部在匹配中，要么在匹配中都不存在。想象一下下面的三部图：

替代文字

现在定义 h_ij="tree rooted that contains H_ij" 来轻松表达匹配：

  • 然后在示例中 M={h12,h22} 将是一个“最大”匹配，尽管并非涉及 B 的所有顶点
  • 集合 {h12,h23} 不匹配，因为 B3 将被选择两次。

那么这个问题可以在多项式时间内解决吗？如果是，是否有加权 (w(h_ij)) 变体的多时间解决方案？如果不是，您能否为像我这样的“简单人”争论甚至证明它，或者建议其他约束来解决 1:n 匹配问题？

例如，该图是否可以转换为通用图，然后可以通过通用图的加权匹配来解决？或者分支甚至匹配的森林在这里有帮助吗？

PS：不是作业;-)

4

1 回答 1

3

最大值和最大值之间存在差异。我假设您的意思是以下文章的最大值。

您似乎没有非常清楚地定义您的问题，但是如果我正确理解了您的意图，您的问题似乎是 NP 完整的（并且“等效于” Set Packing）。

我们可以假设所有 A_i 允许的集合大小相同 (k) 以找到 [1:k] 匹配，因为可以忽略任何其他集合大小。要找到最大 k，我们只需运行 [1:k] 的算法，因为 k = 1,2,3.. 等。

所以你的问题是（我认为......）：

给定 m 个集合族F_i = {S_1i, .., S_n(i)i}（|F_i| = F_i 的大小 = n(i)，不必与 |F_j| 相同），每个大小为 k 的集合，你必须从每个族（比如 S_i）中找到一个集合，使得

  • 对于任何 i neq j，S_i 和 S_j 都是不相交的。
  • S_i 的数量是最大的。

我们可以分两步证明 k=3 的 NP-Complete：

  1. NP-Complete 问题Set Packing可以减少它。这表明它是NP-Hard。
  2. 您的问题出在 NP 中，可以归结为 Set Packing。这和 1) 意味着您的问题是 NP 完全的。它还可以帮助您利用任何已经存在的用于集合打包的近似/随机算法。

设置包装是问题：

给定 n 个集合 S_1, S_2, ..., S_n，找出其中最大的成对不相交集合数。

即使 |S_1|，这个问题仍然是 NP-Complete = |S_2| = ... = |S_n| = 3，称为 3-Set 打包问题。

我们将使用它来证明您的问题是 NP-Hard，通过提供从 3-Set 打包到您的问题的简单减少。

给定 S_1, S_2, .., S_n 只是形成家庭

F_i = {S_i}。

现在如果你的问题有一个多项式时间解，那么我们得到一组集合 {S_1, S_2, ..., S_r} 使得

  • S_i 和 S_j 不相交
  • S_i 的数量最大。

这种简单的减少为我们提供了 3 组包装问题的解决方案，因此您的问题是 NP-Hard。

为了看到这个问题在 NP 中，我们将其简化为 Set-Packing，如下所示：

给定 F_i = {S_1i, S_2i, ..., S_ni}

我们考虑集合 T_ji = S_ji U {i}（即我们将族的 id 添加到集合本身）并通过 Set-Packing 算法运行它们。我将留给您看看为什么 Set-Packing 的解决方案可以解决您的问题。

对于一个最大的解决方案，你所需要的只是一个贪心算法。继续拾取套装，直到你不能再拾取为止。这将是多项式时间。

于 2010-03-02T00:27:32.167 回答