通過走最大重量的路徑走過圖的複雜性

Question

我有一張圖，我想穿過圖（通過所有頂點不是必需的），總是以較大的重量採取路徑。我不能兩次經過同一個頂點，如果沒有更多的動作，我會停下來。什麼是複雜性？我假設它是「n」（其中n是頂點數），但我不確定。

Answer 1

如果你不能通過兩次相同的頂點，你的邊界遍歷的上界是n。 很容易想到這樣的例子，它將是一個緊的界限（例如連接的單個頂點鏈）。

但是，請記住，複雜性是給定的算法，而不是一個普通的任務，你沒有描述你的算法或你的圖是如何組織的，所以這個問題沒有任何意義。如果例如圖是一個團，也許爲每個遍歷選擇最高權重邊本身需要n個計算步驟（如果邊保留在保存在每個頂點的未排序列表中），使得樸素算法O（ n^2）在這種情況下。其他表示可能具有不同的複雜性，但需要不同的算法。

編輯

如果你問關於尋找具有最大總重量（這可能需要一些遍歷挑不具有最高權重的邊緣），比路徑問題是NP難。如果它有一個多項式算法，那麼你可以取一個不加權的圖並找出最長的路徑（一個已知的NP難題，就像jimifiki指出的那樣），然後用該算法求解。

Answer 2

從Longest Path Problem

這個問題被稱爲最長路徑問題，是NP完全問題。