我有一个问题,我是坚持了,并不能找到任何地方下手,所以我无可救药地转向计算器。

这个问题要我们看看它是NP难或多项式,如果NP难证明NP完全性,否则给出的算法。

问题如下:

的产物中存在的n个模块。有两家公司可以建立各个模块,具有一定的成本(c_ij,我:模块号,J:公司号码)。如果模块A和B是由不同的公司建造,他们也有一个额外的费用,(p_ab)。模块A和B不必是连续的,同样的额外费用适用于A和C太。正如所料,这个问题希望我们找到模块公司的分配,使总成本最小。

任何想法?

有帮助吗?

解决方案

它可以降低到最小切割问题,其可以通过任何最大流算法找到。 那么什么是网络? 模块将是我们图形的vertecies,也是我们添加2个新的顶点源和宿。 从源我们添加边缘与容量α1各模块我。同样从每一个模块我我们添加边容量C 12至下沉。同样对于任何模块i和j我们有能力圣战添加边缘 (面向图的因而将有两个边缘(I J)和(j i))的。这是很容易看到min切削该值是这个问题的解决方案(在与源分配给第二公司切口的部分的模块和模块休息到第一公司)

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top