图形路径规划算法：考虑节点和边

Question

图形路径规划算法：考虑节点和边

algorithmpathgraph-algorithmpath-finding

4

我有一个无向图。暂且假设该图是完全的。每个节点都有一个与之关联的特定值。所有边都有正权重。我想找到任意两个给定节点之间的一条路径，使得路径节点的值之和最大，并且路径长度在给定的阈值内。解决方案应该是“全局”的，也就是说，获得的路径应该是所有可能路径中最优的。我尝试了线性规划方法，但无法正确地制定它。任何建议或不同的解决方法都将非常有帮助。

谢谢！

- arg

“线性规划”具体指什么？ - WeaselFox

1

@WeaselFox，维基百科上的线性规划。 - svick

1

只要路径长度在阈值范围内，你可以使用循环吗？ - harold

你知道关于图形大小有哪些限制吗？在计算时间和内存方面，你有任何限制吗？ - watbywbarif

1

两个非常重要的问题（它们可以确定问题是否可以有效地解决）。路径是否可以包含循环？如果是，如果一个节点在路径中出现两次，它会被计算两次吗？ - aelguindy

显示剩余4条评论

4个回答

1

如果您正在寻找一种适用于一般图的算法，那么您的问题是NP完全问题。假设路径长度阈值为n-1，并且每个顶点都有值“1”。如果您找到了解决方案，则可以判断给定的图是否具有哈密顿路径。实际上，如果您的最大化顶点大小路径具有值“n”，那么您就有了一个哈密顿路径。我认为您可以使用类似Held-Karp松弛算法来找到好的解决方案。

- Saeed Amiri

1

我认为，如果路径允许不简单，那么你的减少操作会失败。我意识到OP没有提到他们正在寻找什么样的路径，但我认为在你的答案中明确这一点会更好。 - aelguindy

@aelguindy，我确实是针对简单路径编写的，但我不知道“OP”的观点，但通常当我们在谈论图中的路径时，我们谈论的是简单路径（请参阅图论中的任何教科书，前几页都会说明这一点）。此外，我的缩减适用于一般图，但“OP”说他的图目前是完整的，因此我已经考虑到了所有方面，但我看到“OP”正在寻找一些线性规划，我想向他/她介绍一些相关的线性规划。 - Saeed Amiri

0

整数规划（这可能是个好主意，也可能不是）：

对于每个顶点v，如果访问了顶点v，则令x_v为1，否则为0。对于每条弧a，令y_a为弧a被使用的次数。令s为源点，t为汇点。目标是

最大化 ∑_v value(v) x_v。

约束条件为

∑_a value(a) y_a ≤ 阈值对于所有的v， ∑_a有头v y_a - ∑_a有尾v y_a = {-1 如果v = s; 1 如果v = t; 否则为0（流量守恒）}
对于所有的v ≠ x，x_v ≤ ∑_a有头v y_a (必须进入一个顶点才能访问)
对于所有的v，x_v ≤ 1（每个顶点最多访问一次）
对于所有不属于{s, t}的v，对于分离v和{s, t}的割S，x_v ≤ ∑_{a使得tail(a) ∉ S ∧ head(a) ∈ S} y_a （仅从不在孤立环上的顶点中受益）。

要解决这个问题，需要使用松弛值进行分支和界限。不幸的是，最后一组约束条件的数量呈指数级增长，因此在解决松弛的对偶问题时，你需要生成列。通常对于连通性问题而言，这意味着需要反复使用最小割算法来找到值得实施的割。祝你好运！

- zzzzzzzzzzzzzzzzzz

现在看起来很不错。我会分析一下，如果有疑问会告诉你。 - arg

0

如果您只是将节点的权重添加到其出边的权重中，那么您可以忽略节点权重。然后，您可以使用任何标准算法来解决最短路径问题。

- Hans-Peter Störr

但是这里的图是无向的，所以我必须将其变成有向图。其次，边权重是节点之间的实际距离，我的路径长度仅取决于这个距离。因此，如果我将节点权重添加到其出边（假设它是有向图），那么如何确保路径长度在阈值内？ - arg

我会考虑这种方法。让我看看能否重新构思问题。 - arg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aelguindy · Accepted Answer

这可能不是完美的，但如果阈值（T）足够小，有一个简单的算法可以在O(n^3 T^2)的时间复杂度内运行。它是Floyd-Warshall算法的一个小修改。

d = int array with size n x n x (T + 1)
initialize all d[i][j][k] to -infty
for i in nodes:
    d[i][i][0] = value[i]
for e:(u, v) in edges:
    d[u][v][w(e)] = value[u] + value[v]

for t in 1 .. T
    for k in nodes:
       for t' in 1..t-1:
           for i in nodes:
               for j in nodes:           
                  d[i][j][t] = max(d[i][j][t],
                                   d[i][k][t'] + d[k][j][t-t'] - value[k])

The result is the pair (i, j) with the maximum d[i][j][t] for all t in 0..T

编辑：这假设路径可以不简单，它们可以包含环。

编辑2：这还假设如果一个节点在路径中出现多次，则将被计算多次。显然这不是原帖作者想要的！