連接一組頂點到最佳加權圖

這基本上與道路可能的最小量的連接n個目標的問題。連接一組頂點到最佳加權圖

的輸入是一組頂點（A，B，...，N）

兩個頂點之間的邊的權重很容易計算（例子中的兩個頂點之間的距離笛卡爾）

我想要一個給定一組頂點在歐幾里德空間中的算法，返回一組邊，這些邊將構成一個連通圖並且其邊的總權重儘可能小。

在曲線圖的語言，這是一個連通圖的最小生成樹。

用蠻力我會：

定義的所有頂點之間的所有可能的邊緣 - 說你有n個頂點，那麼你有N（N-1）完全圖
可能的邊緣可以打開或關閉（2個狀態）
通過所有可能的邊緣開啓/關閉組合：2 ^（n（n-1）/ 2）！
忽略所有那些不連接圖
從剩餘組合，發現其的邊緣的權重之和最小的所有

我明白這一個是一個NP-Hard問題。但是，對於我的應用來說，我會最多有11個頂點。我希望能夠在典型的現代智能手機上解決這個問題，或者至少在小型服務器上解決這個問題。

作爲第二個變型中，我想以獲得相同的目標，與每個頂點被連接到最多一個其他頂點的限制。基本上可以從任何點開始獲取單個曲線，並在任何其他點完成，只要連接圖即可。沒有必要回到你開始的地方。 在圖形語言中，這是開放的歐幾里德旅行推銷員問題。

一些僞算法將是非常有益的。

來源

2013-09-27 Patrick

什麼是開放euklidian茶匙？你的意思是最小的哈密爾頓路徑嗎？（http://en.wikipedia.org/wiki/Hamiltonian_path） – Bytemain

@Phpdna開放的含義不是一個循環。歐幾里德在2d空間中的含義。請參閱http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP – Patrick

是的，我知道。我給你看了一個求解器。但這不是最小的哈密爾頓路徑嗎？ Minium是路徑的長度。 – Bytemain

確定的第一個問題，你必須建立一個Minimum Spanning Tree。有幾種算法可以這樣做，Prim和Kruskal。但在第一個鏈接到治療完整的圖表，它是你的情況。

對於第二個問題，它變得更復雜一點。問題變成了開放Traveling Salesman Problem（oTSP）。閱讀以前的鏈接可能集中在歐幾里德和不對稱。

問候

來源

2013-09-27 09:09:24 luiso1979

是的，第一部分絕對是MST。實際上它是歐幾里得MST（http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree）。第二部分是歐幾里得oTSP，正如您正確識別它。 – Patrick

梅比你可以嘗試greedy算法：

1. Create a list sortedList that stores each pair of nodes i and j and is sorted by the 
    weight w(i,j). 
2. Create a HashSet connectedNodes that is empty at the beginning 
3. while (connectedNodes.size() < n) 
    element := first element of sortedList 
    if (connectedNodes.isEmpty()) 
     connectedNodes.put(element.nodeI); 
     connectedNodes.put(element.nodeJ); 
     delete element from sortedList 
    else 
     for(element in sortedList) //start again with the first 
     if(connectedNodes.get(element.nodeI) || connectedNodes.get(element.nodeJ)) 
      if(!(connectedNodes.get(element.nodeI) && connectedNodes.get(element.nodeJ))) 
       //so it does not include already both nodes 
       connectedNodes.put(element.nodeI); 
       connectedNodes.put(element.nodeJ); 
       delete element from sortedList 
       break; 
      else 
       continue;

所以我解釋第3步一點點：

直到所有節點都連接到一個其他你加，只要節點。確定圖形已連接，因爲只需添加一個節點（如果他已連接到connectedNodes列表中的其他節點）。

所以這個算法很貪婪是什麼意思，它不能確定，解決方案是最優的。但它是一個相當不錯的近似值，因爲它總是佔用最短邊緣（因爲sortedList按邊的權重排序）。

喲不會得到duplicates在connectedNodes，因爲它是一個HashSet，這也使運行速度更快。

總的來說，運行時的開始時應該是O（n^2），在O（n^3）的下面應該是O（n^2），因爲在最壞的情況下，你會在整個列表中運行的n^2和你做n次，因爲你在每一步添加一個元素。

但更可能的是，你發現一個元素比O（n^2）快得多，我認爲在大多數情況下它是O（n）。

來源

2013-09-27 09:13:03

如果我沒有弄錯這個解決方案是[Prim的算法]（http://en.wikipedia.org/wiki/Prim%27s_algorithm），請始終提供必要的參考文獻 – luiso1979

我不確定..突然想到我該怎麼做。也許我有這個在我的頭上：D –

您可以使用optimap tsp解算器fron gebweb或線性程序解算器解決travelsalesman問題和hamilton路徑問題。但第一個問題似乎要求最小生成樹，也許問題標籤是錯誤的？

來源

2013-09-27 09:47:21 Bytemain

謝謝。你是對的。我更新了問題和標籤 – Patrick

對於第一個問題，有一個O(n^2 * 2^n)時間算法。基本上，您可以使用dynamic programming來減少搜索空間。假設所有頂點的集合爲V，所以狀態空間由V的所有子集組成，目標函數是連接頂點的邊的權重的最小和S。對於每個州S，您可以列舉所有邊緣(u, v)其中u是S而v是V - S，並更新f(S + {v})。在檢查了所有可能的狀態之後，最佳答案是f(V)。

下面是示例代碼來說明的想法，但它是落後的方式實施。

const int n = 11; 
int weight[n][n]; 
int f[1 << n]; 
for (int state = 0; state < (1 << n); ++state) 
{ 
    int res = INF; 
    for (int i = 0; i < n; ++i) 
    { 
     if ((state & (1 << i)) == 0) continue; 
     for (int j = 0; j < n; ++j) 
     { 
      if (j == i || (state & (1 << j)) == 0) continue; 
      if (res > f[state - (1 << j)] + weight[i][j]) 
      { 
       res = f[state - (1 << j)] + weight[i][j]; 
      } 
     } 
    } 
    f[state] = res; 
} 
printf("%d\n", f[(1 << n) - 1]);

對於第二個問題，抱歉我不太瞭解它。也許你應該提供一些例子？

來源

2013-09-27 10:01:40 fuch

感謝您的這一點。第二個問題是「開放式旅行推銷員問題」。我更新了這個問題。 – Patrick

連接一組頂點到最佳加權圖

回答

相關問題