需要找到最小距離，並進行路線

和點是如何連接：

文件點是如何連接的是輸出我有。預期的輸出應該是1<->216 , 23<->157 115<->157，然後是115<->216。訂單並不重要，但這些點應該這樣連接

讓我問你一個問題。我有以下代碼：

for (int i = 0; i < values.size()-1;i++) 
    { 
     int result = 0; 
     double Min2 = DBL_MAX; 
     int x = 0; 
     for (int j = i+1; j < values.size(); j++) 
     { 


      /*if (visited[j] == false)*/ 

      { 
       distance = sqrt(pow((values[i].x2 - values[j].x2), 2) + pow((values[i].y2 - values[j].y2), 2)); 

       if (distance < Min2 && distance != 0) 
       { 

        Min2 = distance; 

        x = j; 
       } 

      } 

     }

如果你看一下圖的左邊第一個節點1然後進入216，然後115，然後157，然後23我除了216-115而是右側連接它連接216-157。爲什麼忽略或最小距離無濟於事。我試圖使用標誌（如果訪問與否）相同的結果。所有節點都能正常工作，只是這個節點不想正確連接。

來源

2016-04-08 Misha Ostapchuk

你在問題中描述的內容（節點順序：1-> 216-> 115-> 157-> 23）根本不匹配圖像中「連接點的方式」。 – user463035818

...「如何連接點」是您的代碼的輸出？ – user463035818

第一張圖是點的圖形，第二張圖是它們如何連接的點。從1-216或從216-1連接點並不重要。主要是所有點都應該連接，並且所有點都正確連接，除了115-157之外，因爲代碼連接157-216 什麼說1-> 216-> 115-> 157-> 23這是圖表如何表示。我將這些點添加到矢量中，它可以先是1然後是23，但是我無法對它們進行排序，因爲它應該是這樣。這個想法只是我需要連接他們的權利和代碼連接，我有更多的積分，他們是正確的 –

代碼的邏輯似乎有點奇怪......

for (int i = 0; i < values.size()-1;i++) { 
    int result = 0; 
    double Min2 = DBL_MAX; 
    int x = 0; 
    for (int j = i+1; j < values.size(); j++) {

迭代直到size()-1好像你假設的關係「最近的鄰居」是可交換的，但事實並非如此。考慮下面這個例子：

a b       c

一個具有B中最接近的節點和（偶然）也2b具有作爲最接近的節點，但是C有B中最接近的節點，這方面你會錯過。

此外，從i+1開始的第二個循環看起來很奇怪，因爲它假定向量中的點已經是有序的（如果是這種情況，那麼搜索最近的節點又有什麼意義？）。

如果你已經知道，這些節點是沿着路線的話，我會做這樣的：

1）與路由中的第一個節點n0開始（它是一個比較複雜一點，如果你不知道這個節點）

2）找到最近的節點n0稱之爲n1

3）繼續查找最近的節點到尚未連接到路由節點間ni，稱之爲ni+1

4）重複3）直到你到達路線的盡頭。

我有一個印象，你不明白這些步驟和你的代碼之間的區別。我不喜歡放棄，所以我會盡量在一個不太準的方式再解釋一遍：

int currentNode = startNode;  // as mentioned before, if you dont know 
           // this its a bit more involved 
std::vector<int> route; 
route.push_back(currentNode);  
while (currentNode != endNode) { // also knowing the last node of the route helps... 
    double minDistance = std::numeric_limits<double>::max(); 
    int nextNode = -1; 
    for (int i=0;i<nodes.size();i++) { 
     if (std::find(route.begin(), route.end(), i) == route.end()){ 
      double distance = getDistance(currentNode,i); 
      if (distance < minDistance) { 
       minDistance = distance; 
       nextNode = i; 
      } 
     } 
    } 
    route.push_back(nextNode); 
    currentNode = nextNode; 
}

你外環不應該通過迭代的所有節點，如果你真的想找到只有一個途徑。你還必須記住已經在路由中的節點（如果每個節點只出現一次，而你不想要一個閉環）。

來源

2016-04-08 19:44:12 user463035818

是的，你是對的，我做到了，但結果如下。 1-> 216 23-> 157 115-> 157 157-> 115然後115-> 216 我沒有使用該方法，因爲它創建了兩次相同的路線 –

這就是爲什麼我想使用訪問過的標誌但它給出了與之前一樣的輸出 –

@MishaOstapchuk你做了什麼？（並請停止垃圾郵件序列的數字） – user463035818

for (int i = 0; i < values.size();i++) 
    { 
     int result = 0; 
     double Min2 = DBL_MAX; 
     int x = 0; 

     for (int j =0; j < values.size(); j++) 
     { 


      /*if (visited[j] == false)*/ 

      { 
       distance = sqrt(pow((values[i].x2 - values[j].x2), 2) + pow((values[i].y2 - values[j].y2), 2)); 

       if (distance < Min2 && distance != 0) 
       { 

        Min2 = distance; 

        x = j; 
       } 

      } 

     } 
     /*visited[i] = true;*/

來源

2016-04-08 20:44:29

需要找到最小距離，並進行路線

回答

相關問題