gpt4 book ai didi

algorithm - 图 - 在具有正节点和负边的图形中移动的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:56:13 25 4
gpt4 key购买 nike

我有一个图表,节点中有一些正值,边缘中有一些负值。
我必须在图中精确地移动 x 次,从源节点到目标节点,目标是最大化总和:

  • 当我停留在一个节点中进行移动时
  • 通过边时的减法

所以,如果我在同一个节点停留移动,总和会增加,所以如果我在值为 10 的节点停留 4 次,我总共获得 40。下图是一个示例。

enter image description here

在这种情况下最好的解决办法是:

Move1 -> (源节点+3) 3

移动 2 -> (3-20+15) -2

Move3 -> (stay +15) 13

...(保持相同的节点)...

Move19 -> (stay +15) 253

Move20 -> (目的节点253-5+3) 251

什么是解决问题的有效方法?我可以实现伪代码之类的东西,只是为了了解如何解决它。

非常感谢。

最佳答案

这可以通过 Bellman-Ford algorithm 的变体来解决。 ,具有 O(|E|*n) 时间复杂度,其中 |E| 是边数,n 是步数:

为简单起见,假设您在每个节点中也有一个自循环,权重为 0,这表示“停留操作”。所以你有:

for all u in V:
(u,u) in E
w(u,u) = 0

现在,使用 Dynamic Programming 应用递归公式:

D[v][0] = 0          if v is the source
-infinity otherwise
D[v][i] = max { D[u][i-1] + w(u,v) + cost(v) | where (u,v) is an edge }

解决方案是D[target][n]

这基本上是 Bellman-Ford 算法(使用 max 而不是 min),但是你在 n 迭代之后而不是在 之后停止>|V|.

关于algorithm - 图 - 在具有正节点和负边的图形中移动的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44007817/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com