algorithm - 带约束的二部图中的最大权重匹配

Question

假设我们有两个集合: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 的所有元素。

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

谢谢

Answer 1

它是 NP 难的。

取子集和实例 {x₁, x₂, ..., x_n}，其中 x _i> 0 和一个数字 k。创建一个二部图，其中左顶点是 {a₁, ..., a_n}，右顶点是 {b₁,b< sub>2}，以及:

F(a_i, b₁) = x_i

F(a_i, b₂) = 0

C₁ = k

C₂ = 0

所以你可以通过连接 a_i 和 b₁ 来得到数字 x_i，并通过连接 b _{来离开它2 。显然存在一个权重 k 匹配当且仅当子集和实例有解。}