在遍歷邊上約束的最短路徑

在處理一個項目時，我偶然發現了一個I 未能解決的圖算法問題。問題如下：在遍歷邊上約束的最短路徑

你有一個導向，加權圖，並希望找到一個開始節點和在訪問指定的節點終端節點（很像 Find the shortest path in a graph which visits certain nodes）之間的最短路徑。然而，隨着節點和邊緣，這個圖表還有「項目」的概念，駐留在節點上，當你進入該節點時你「拾起」。現在還有一個額外的限制條件，如果您已經獲得必要的項目，則該邊緣只能穿過，對於該特定邊緣，邊緣只能獲得I。認爲它是一扇門的鑰匙;您需要先獲得鑰匙才能通過。

我只能想到以指數方式爆炸的蠻力方法。任何人都可以想到更好的東西，或者將我指向解決這個問題的地方？或者也許說服我，這是「硬」（從計算上講）？謝謝你的幫助！

來源

2013-10-04 maxnelso

有多少種不同的物品？ – templatetypedef

只是一種取決於遊戲（你可能已經猜到這是通過視頻遊戲遍歷），但我會說30-40的順序。 – maxnelso

是否有某種好的訂購項目？也就是說，這些項目是否大致遵循線性進展？ – templatetypedef

這個問題是NP-HARD最佳解決方案。哈密爾頓路徑問題有一個簡單的減少：

將獨特的項目放在原始圖形的每個頂點上。構建僅連接到目標頂點的sink頂點。讓這兩個頂點之間的邊緣需要所有的項目。

來源

2013-10-04 20:24:27 tskuzzy

這是如何工作的？你能發佈一個代碼示例嗎？ – Bytemain

tskuzzy正在構建一個圖表，您可以*訪問每個頂點從開始到結束。假設每條邊都具有相同的重量。如果一個圖有一個哈密爾頓循環，那麼這個循環就是最優解。如果最優解不是哈密頓週期，那麼該圖沒有一個。因此，如果你給我你的算法，我可以用它來解決任何圖的HC。 – DanielV

嗯，結果有點令人失望，但謝謝！ – maxnelso

您可以嘗試修改版本的保存算法。解決車輛路徑問題是一種啓發式方法。也許你可以反轉它，併爲所需的按鍵創建拾取功能。它用於交付和最短路徑問題。

來源

2013-10-04 20:02:39 Bytemain

在遍歷邊上約束的最短路徑

回答

相關問題