比方說，我有這個圖如何找到與加權節點圖的最佳路徑和頂點
我想找到儘可能短但路徑st得分（節點的總和） - 換句話說，一條路徑不能長於某個定義的常數，但給我最好的點數。我想在同一個節點上啓動和停止，並且不想過去已經訪問過的節點。
是否有任何算法可以幫助我解決這個問題，或者您有什麼想法如何解決它？
哦，它的不是作業，我只是想創建一個特殊的路徑查找器。
編輯
到目前爲止，我已經能夠建立一個工作算法可以在幾秒鐘一些路徑。但是我沒有得到我想要的分數 - 我只獲得了所需分數的大約85％。如果我更改算法的參數，那麼時間將在幾小時內和更多...
我不認爲這是可以解決比蠻力時間更好。你可以計算出全部路徑達到一定的約束長度。但是，對於任意大的圖表來說，這將非常緩慢。如果你正在尋找一個可靠的猜測，我會從一個貪婪算法開始，選擇每個長度值最高的步驟，直到達到極限。然後，您可以在提前填充的情況下（例如，如果您已經過了5次，但是您的限制爲6，並且您的當前節點沒有連接的長度路徑）添加事物，例如反向，以瞭解它是如何工作的。
我認爲你是對的。這似乎是一個NP問題。我不知道如何將有效的算法與路徑搜索相結合。具有啓發式和分支界限的蠻力仍然沒用 - 時間非常長，因爲我有大約80個節點。 – user219882 2012-03-18 20:37:42
我不知道這是否會實際工作，但這些都是我最初的想法：
也許用最大生成樹嘗試（普里姆的或Kruskal的）。由於您不想重複頂點，因此您的路徑必須最終成爲cycle圖表。走生成樹（也許某種貪婪算法？），一旦你點擊一片葉子，回到開始頂點（因爲原始圖是完整的圖）。如果沒有負邊權重，這隻會起作用（可能）。
現在只是想一想 - 這是深夜，我會在早上仔細觀察。 :)
該圖是否定向？否則：找到最小權重邊緣'（u，v）'，使得'u'是你的源，'（u，v），（v，u）'是最短路徑。你沒有提到兩次使用同一條邊的問題。 – amit 2012-03-17 18:14:12
它沒有指示。當然，我不能兩次使用相同的邊緣 - 這將打破我無法瀏覽已經訪問過的節點的情況。 – user219882 2012-03-17 18:16:16
如您所說，如果它也是目標節點，則必須訪問源兩次。路徑將是：'v - > ... - > v'，並且'v'必須被訪問兩次。 – amit 2012-03-17 18:16:55