考虑节点和边的图上的路径查找算法

Question

我有一个无向图。现在，假设图形是完整的。每个节点都有一个与之相关的特定值。所有边缘都具有正面权重。 我想找到任意2个给定节点之间的路径，以便与路径节点相关的值的总和最大，同时路径长度在给定阈值内。 解决方案应该是“全局的”，这意味着获得的路径应该在所有可能的路径中最优。我尝试了一种线性编程方法，但无法正确表达它。 任何建议或不同的解决方法将有很大的帮助。

谢谢！

Answer 1

这可能并不完美，但如果阈值（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 

编辑：此假设路径被允许是并不简单，它们可以含有周期。

EDIT2：这也假定如果节点在路径中出现多次，它将被计数多次。这显然不是OP想要的！

Answer 2

如果您在寻找普通图的算法，您的问题是NP-Complete，假设路径长度阈值为n-1，并且每个顶点的值为1，如果您找到问题的解决方案，则可以说给定的图有哈密尔顿路径。事实上，如果您的最大化顶点大小路径的值为n，那么您有一个哈密尔顿路径。我想你可以使用Held-Karp放松之类的东西来寻找好的解决方案。

Answer 3

整数程序（这可能是一个好主意，或者也许不是）：

对于每一个顶点v，令x _v是1，如果顶点v被访问，否则为0。对于每个弧a，令y _a是弧a被使用的次数。让我们成为源头，成为目的地。目标是

最大化∑ _v值（V）× _v。

约束是

∑ _一个值（）Y _一个 ≤阈 ＆的forall; V，∑ _{一个具有头部S}ý_一个 - ∑ _{一个具有尾v}ÿ _a = {-1如果v = s; 1如果v = t;否则为0（节约流量）
＆forall的; v ≠ X，X _v ≤ ∑ _{一个已头部S}ý_一个（必须输入一个顶点参观）
＆的forall; V，X _v ≤ 1 （访问每个顶点最多一次）
＆forall的; v ∉ {S，T}，＆forall的;切口s表示从{S，T}分离顶点v，X _v ≤ ∑ _{一个，使得尾的（a）∉ S ∧头（a）中∈小号}ý_一个（从没有对分离的环的顶点仅受益）。

来解决，做分支限界与松弛值。不幸的是，最后一组约束的数量是指数级的，所以当你解决宽松的双重约束时，你需要生成列。通常，对于连接问题，这意味着反复使用最小切割算法来找到值得执行的切割。祝你好运！

Answer 4

如果你只需要添加一个节点的重量，它的出边的权重，你可以对结点的权忘记。然后，您可以使用shortest path problem的任何标准算法。