有一個城鎮網絡，由各種整數長度的道路相連。建議算法（圖 - 可能是NP-Complete）
一位旅行者希望在他的車上從一個小鎮旅行到另一個小鎮。但是，他不想盡量減少行駛距離，相反，他希望儘量減少旅程的汽油成本。汽油可以在任何城市購買，但每個城市以各種（整數）價格供應汽油（因此爲什麼最短路線不一定是最便宜的）。 1個汽油單位使他能駕駛1個單位的距離。 他的汽車只能在汽油箱中裝載如此多的汽油，他可以選擇在每個城市旅行時購買多少汽油。找到最低汽油成本。
有沒有人知道可以用來解決這個問題的有效算法？即使這種類型的問題的名稱將是有用的，所以我可以自己研究它！顯然這與最短路徑問題並不完全相同。任何其他技巧讚賞！
編輯 - 我的實際問題是，將有1000個城市<; < 10000道路;汽油箱容量將介於1到100之間。
我認爲問題是：汽油是否有可能使潛在的旅行商問題在計算上更可行？如果不是，則不存在有效的非近似算法。
當然，你可以找到有效的邊緣案例解決方案，並且可能會有更多的汽油邊緣案例，因爲汽油價格如此便宜，所以總是首先考慮這座城市。
我想你可以通過動態編程來解決這個問題。對於每個節點，您都會保存一組汽油成本元組以及使用該汽油的路徑長度，其中包含最佳解決方案。您每循環一次都會遍歷所有節點，並且如果有可以前往的節點（已經有解決方案），則可以通過解決方案循環遍歷所有節點。您選擇最低成本，但請注意：您必須考慮當前節點中的汽油成本。陣列中所有高於當前節點成本的成本可以在當前節點處購買。請注意，已經有解決方案的節點應該重新計算，因爲您可以從那裏訪問的節點可能會發生變化。您從最終節點開始，將解決方案設置爲空數組（或者一個成本和長度爲0的條目）。最終的解決方案是在開始時採取解決方案並總結每個成本*的長度。
我不太明白這是如何工作的，但明天當我不太累時，我會再看一次。 – 2012-08-17 23:11:57
我想試試這個：
定義精確停止標準是一個小小的挑戰，它可能是最好只是停止一旦發現一個新測試途徑的最低成本比大已經測試的路線的最低成本。
因此，使用2個算法，每個問題的一部分。
這也是一個有效的解決方案，但不幸的是，非常慢。 – 2012-08-17 17:19:45
一旦最低成本開始再次增加，我認爲你不能停止，最便宜的路線可能是最長的，最便宜的路線是最短的，例如...爲了確保最便宜你必須檢查每條路線：/ – 2012-08-17 22:45:04
我同意，這不是一個很好的答案。 – 2012-08-18 08:04:10
如果您願意增加圖形的大小，則可以直接使用Djikstra's algorithm來解決此問題。
假設您的汽油箱可容納0至9個汽油單位。
的想法是將每個鎮分成10個節點，與節點x用於表示與箱汽油的X單元處於鎮噸鎮噸。
然後，您可以在此擴展圖上構造零成本邊緣來表示不同城鎮之間的行駛（在此過程中使用汽油，因此如果距離爲3，您將從8級節點到5級節點），和更多的邊緣來代表每個城鎮用一個汽油單位填充油箱（費用取決於城鎮）。
然後將Djikstra應該給從開始到結束的最低成本路徑。
聰明 - 我喜歡這個！雖然如果你有一個大坦克，它確實使圖形更大！ – 2012-08-17 22:37:34
這可以使用遺傳算法適當地優化。遺傳算法在一些複雜的問題，戰勝人類： http://en.wikipedia.org/wiki/Genetic_algorithm
遺傳算法的要點是：
你也可以制定，作爲一個整數線性規劃（ILP）問題。優點是有很多現成的解決方案可以完成這項任務，複雜性不會像Peters解決方案的坦克大小那樣快速增長。
在這個特定問題的變量將是任何一個城市購買汽油的數量，在途中任何城市，並在汽車油箱量實際道路上拍攝的。 約束必須保證車上花費每條路上所需的燃料，並沒有比在任何城鎮燃料MAX單位小於0以上的道路構成了從A路徑B. 目標將是所購燃料的總成本。
整個事情看起來怪異（ILP配方經常這樣做），但並不意味着它不能在合理的時間來解決。
它看起來像揹包問題，我想。讓我們看看其他人說什麼。 – 2012-08-17 16:32:35
我可以建議您將標題更改爲「旅行推銷員變化」或其他內容。目前的標題有些不倫不類。 – Nicolas78 2012-08-17 16:32:37
這既不是一個揹包問題，也不是旅行推銷員的問題：他想從A到B，而不是到處都是。這是一個特定的圖形問題，它沒有名稱afaik。 – 2012-08-17 16:38:22