2

假设我们有两个集合：A=(a_1,a_2,...,a_m) 和 B=(b_1,b_2,...,a_n)（不一定大小相同）。函数 F 为从集合 A 到集合 B 的每个链接分配权重：F:A*B->R。因此，例如，F(a_1,b_1)=2 表示 a_1 和 b_1 之间链接的权重为 2。问题是将集合 A 的元素连接到集合 B 的元素，以最大化满足这些约束的链接权重：

  • 集合 A 的元素必须与集合 B 的一个元素完全匹配。
  • 集合 B 的元素允许有零个或多个匹配 (0,1,2...)，尽管 B 的元素存在对权重总和 C_i 的约束。也就是说，如果我们选择将 a_1 连接到 b_1，而a_2到b_1，权重之和F(a_1,b_1)+F(a_2,b_1)应该小于等于C_1。此约束适用于 B 的所有元素。

我已经搜索了一些想法，并研究了分配问题和匈牙利算法。另外一点是，这些都没有考虑到我的第二个约束。您对如何解决这个问题有任何想法吗？

谢谢

4

1 回答 1

4

这是NP难的。

取一个子集和实例 {x 1 , x 2 , ..., x n }，其中 x i > 0 和一个数字 k。创建一个二分图，其中左顶点为 {a 1 , ..., a n }，右顶点为 {b 1 ,b 2 }，并且：

F(a我, b 1 ) = x我

F(a i , b 2 ) = 0

C 1 = k

C 2 = 0

因此，您可以通过将 a i与 b 1连接来获取数字 x i，并通过与 b 2连接来保留它。显然，如果子集和实例有解，则权重 k 匹配。

于 2012-06-13T21:28:31.297 回答