將無向圖導入最小成本路徑聯合

我必須創建一個加權無向圖的解決方案，通過所有節點並以最小總成本創建。有幾條路徑，沒有定義的起始節點，最終會在一個相交節點處相遇。路徑的數量和包含在路徑中的節點的數量不是預先確定的。節點可以多次傳遞。將無向圖導入最小成本路徑聯合

我正在處理什麼樣的問題，可能的算法作爲解決方案？我想它應該是最小生成樹的一個變體（意思是使用交點節點作爲路徑的起點而不是終點）

2012-12-14 DelicateBehemoth

嗯，我沒有得到你。目前還不清楚這個問題究竟給了什麼。 – dreamzor

給出的是一個節點圖。要求是所有的節點都需要通過，這樣通過的總成本是最小的。通過從圖的「外圍」的任意節點開始路徑，全部到達圖中心的某個（給定）節點。節點可以被訪問不止一次，所以路徑可以去訪問一個節點，然後返回到先前通過的時間（如果滿足最小成本條件）。 – DelicateBehemoth

另一種解決方案是從另一方面開始 - 而不是從起始節點到達中央節點，從中央節點開始並將路由傳播到「外圍」節點。因此，爲什麼我提到生成樹，但分支應該是路由。 – DelicateBehemoth

它被稱爲最小成本哈密頓電路問題。

Here你可以閱讀更多關於它的信息。

來源

2012-12-14 14:57:52 dreamzor

謝謝你的回答，但結構不是電路。它應該有一個星形，在預定的一個節點上會合，具有未知數量的哈密爾頓路徑 – DelicateBehemoth

這是一棵您正在尋找的問題，並且問題是最小生成樹 - MST：構建跨越圖中所有節點的樹並且樹上邊緣的成本儘可能低。這是一個多項式問題。 Prim和Kruskal每個都有解決方案的衆所周知的算法。查看http://en.wikipedia.org/wiki/Kruskal的Kruskal算法的s_algorithm。

注意：當樹應該跨越給定的適當的節點子集而不是圖中的所有節點時，問題是NP完全的。這次它被稱爲斯坦納最小樹問題。

來源

2012-12-15 10:08:35 ashley

謝謝你的迴應，但實際上它應該是MST的變體，它給出了一個有多條路徑的樹它們只是從中心節點到外圍節點的一個分支/路徑，沿途通過節點，而不是跨越多個分支。 – DelicateBehemoth

也許你應該更清楚地闡述你的問題。它仍然看起來像MST或最短路徑樹。 – ashley

就像我說的那樣，它是MST的一種變體，不同之處在於它是在無向圖上引導路徑（它從一個「外圍」節點開始，並訪問一個序列中的節點以便到達一個GIVEN節點）節點/邊緣被訪問更多次的可能性。 – DelicateBehemoth

將無向圖導入最小成本路徑聯合

回答

相關問題