考慮節點和邊的圖上的路徑查找算法

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的任何標準算法。