0

我有一个问题，我被困住了，找不到任何开始的地方，所以我绝望地转向stackoverflow。

问题要我们找出它是 np-hard 还是多项式，如果它的 np-hard 证明 np-completeness，否则给出算法。

问题如下：

存在 n 个模块的乘积。有两家公司可以构建每个模块，但需要一些成本（c_ij，i：模块编号，j：公司编号）。如果模块 a 和 b 是由不同的公司构建的，它们也会产生额外的成本 (p_ab)。模块 a 和 b 不必连续，同样的额外费用也适用于 a 和 c。正如预期的那样，问题要我们找到将模块分配给公司的方法，以使总成本最小。

有任何想法吗 ？

4

1 回答 1

1

它可以简化为最小割问题，可以通过任何最大流算法找到。那么网络是什么？模块将是我们图的顶点，我们还添加了 2 个新顶点源和接收器。从源头开始，我们将边缘添加到容量为 Ci1 的每个模块 i。同样，从每个模块 i 中，我们将边缘添加到容量为 Ci2 的接收器。同样对于任何模块 i 和 j，我们添加具有容量 pij 的边（面向图，因此将有两条边 (ij) 和 (ji)）。很容易看出最小切割的价值是问题的解决方案（切割中的部分模块，源分配给第二家公司，其余模块分配给第一家公司）

于 2010-11-29T01:16:31.653 回答