1

起初我遇到了来自不同领域的问题，但现在它被简化并转换为图表。

图是

  • 双向
  • 全连接
  • 每个顶点都有正成本
  • 每条边都有负成本
  • 开始和结束顶点相同

我只需要遍历那些最大化总效用成本的节点。

这听起来像任何众所周知的图形问题吗？

例子：

V = {A, B, C}

vertex points = {0, 6, 5}

edge cost = {[A,B]=-8, [A,C]=-2, [B,C]=-10}

所以解决方案：只访问顶点C并返回。总共会给1分。

如果顶点被访问，它的点变为0。

4

2 回答 2

3

这就是所谓的领奖旅行商问题。

于 2013-04-24T16:08:34.423 回答
1

我认为这对于一般图来说应该是 NP-hard，因为它可以重新表述为最长路径问题。为了看看如何，我们改变了边和顶点的成本。

让c(e)是边的成本e，让e = {u,v}和分别c(u), c(v)是顶点u和的成本v。将每条边的新成本设置为c_new(e) = c(e) + 1/2*(c(u)+c(v))。这背后的直觉是，在从顶点到自身的循环中，您使用与通过的每个顶点相关的 2 条边，因此您只能计算每条边的顶点成本的一半；将其视为在到达时支付一半成本，在离开顶点时支付另一半。

更改边的成本后，您可以忽略顶点成本，因为它们现在将被考虑在边的成本中。您的问题现在变成了找到一条使其边缘权重之和最大化的简单路径，这就是称为最长路径问题的 NP-hard 问题。

于 2013-04-23T16:50:03.323 回答