邊緣預算最大簡單路徑

這是一個自我制定的問題的一部分，因此我還沒有能夠「谷歌」它，我自己的嘗試到現在爲止一直徒勞無功。邊緣預算最大簡單路徑

您將得到的曲線圖G（V，E）每個節點的V具有利潤無線，每個邊緣的ë具有CI的成本。我們現在給出預算C，需要找到的是單條路徑，使成本總和小於C其中wi是最大的。這裏的路徑具有正常的定義，即路徑不會包含重複的頂點（簡單路徑）。

很顯然，哈密爾頓路徑是一個特例（設置成本= | N-1 |和每個邊的成本= 1），因此這是一個NP難題，所以我在尋找近似值解決方案和啓發式。

數學

給定的圖G（V，E）

CI> = 0對於每個邊緣Ë

無線> = 0爲每個頂點v

找到imple路徑P使得

薩姆CI在所有的邊緣ê在P < = Ç

最大化薩姆在P

無線所有 v

來源

2012-07-08 Manyu

哈密頓路徑爲什麼是特例？你的問題沒有說明路徑最多隻能訪問一次頂點。 – Venge 2012-07-08 06:00:35

我想你想指定ci> = 0，一旦你訪問它或者你只能訪問一個頂點，頂點的利潤就會變爲零。 – VSOverFlow 2012-07-08 06:16:04

@Patrick：對於所有邊的成本= 0，所有頂點的成本= 1 - 如果此問題有長度| V |的解，則存在哈密爾頓路徑。 – amit 2012-07-08 07:26:10

一個簡單的啓發式思想是一個隨機的變化hill climbing和greedy algorithm。

定義增加重量和降低成本的價值函數。例如：現在

value(u,v) = w(v)/[c(u,v) + epsilon] 
(+ epsilon for the case of c(u,v) = 0)

，這個想法是：
從頂點u，繼續到頂點v概率：

P(v|u) = value(u,v)/sum(u,x) [ for all feasible moves (u,x) ]

重複操作，直至無法繼續。

此解決方案將爲您提供一種解決方案 - 很快，但它可能不是最佳狀態。然而 - 它是隨機的 - 你可以隨時重新運行它，而你有時間。
這會給你一個anytime這個問題的算法，這意味着 - 你有更多的時間 - 你的解決方案越好。

一些優化：

你可以嘗試學習宏來加速各自的搜索，這將導致每個時間量更多的搜索，而且很可能 - 更好的解決方案。
通常，第一搜索不是隨機的，並且是純粹貪心，繼max{value(u,v)}

來源

2012-07-08 08:48:59 amit

這被稱爲選擇性TSP問題，或與利潤旅行推銷員。 Google學術搜索應該能夠給你一些參考。 Metaheuristics，如遺傳編程或禁忌搜索經常使用。如果你想以最佳方式解決問題，線性編程技術可能會工作（不幸的是，你沒有說明你正在處理的實例的大小）。如果路徑的長度很小（比如15個頂點），那麼color-coding也可能工作。

來源

2012-07-08 19:28:37

我正在查看的粗略大小大約是50個節點，並且是一個幾乎完整的圖，但成本函數通常意味着路徑中不會有超過15個節點 – Manyu 2012-07-09 16:12:41

邊緣預算最大簡單路徑

回答

相關問題