如何使兩點之間的最短路徑算法更快？

我寫了這個算法。它起作用（至少在我的簡短測試用例中），但在較大的輸入上花費太長時間。我怎樣才能讓它更快？如何使兩點之間的最短路徑算法更快？

// Returns an array of length 2 with the two closest points to each other from the 
// original array of points "arr" 
private static Point2D[] getClosestPair(Point2D[] arr) 
{ 

    int n = arr.length; 

    float min = 1.0f; 
    float dist = 0.0f; 
    Point2D[] ret = new Point2D[2]; 

    // If array only has 2 points, return array 
    if (n == 2) return arr; 

    // Algorithm says to brute force at 3 or lower array items 
    if (n <= 3) 
    { 
     for (int i = 0; i < arr.length; i++) 
     { 
      for (int j = 0; j < arr.length; j++) 
      {     
       // If points are identical but the point is not looking 
       // at itself, return because shortest distance is 0 then 
       if (i != j && arr[i].equals(arr[j])) 
       { 
        ret[0] = arr[i]; 
        ret[1] = arr[j]; 
        return ret;     
       } 
       // If points are not the same and current min is larger than 
       // current stored distance 
       else if (i != j && dist < min) 
       { 
        dist = distanceSq(arr[i], arr[j]); 
        ret[0] = arr[i]; 
        ret[1] = arr[j]; 
        min = dist; 
       }   
      } 
     } 

     return ret; 
    } 

    int halfN = n/2; 

    // Left hand side 
    Point2D[] LHS = Arrays.copyOfRange(arr, 0, halfN); 
    // Right hand side 
    Point2D[] RHS = Arrays.copyOfRange(arr, halfN, n); 

    // Result of left recursion 
    Point2D[] LRes = getClosestPair(LHS); 
    // Result of right recursion 
    Point2D[] RRes = getClosestPair(RHS); 

    float LDist = distanceSq(LRes[0], LRes[1]); 
    float RDist = distanceSq(RRes[0], RRes[1]); 

    // Calculate minimum of both recursive results 
    if (LDist > RDist) 
    { 
     min = RDist; 
     ret[0] = RRes[0]; 
     ret[1] = RRes[1]; 
    } 
    else 
    { 
     min = LDist; 
     ret[0] = LRes[0]; 
     ret[1] = LRes[1];  
    } 


    for (Point2D q : LHS) 
    { 
     // If q is close to the median line 
     if ((halfN - q.getX()) < min) 
     { 
      for (Point2D p : RHS) 
      { 
       // If p is close to q 
       if ((p.getX() - q.getX()) < min) 
       {    
        dist = distanceSq(q, p);   
        if (!q.equals(p) && dist < min) 
        { 
         min = dist; 
         ret[0] = q; 
         ret[1] = p; 
        } 

       } 

      } 
     } 
    } 

    return ret; 
} 

private static float distanceSq(Point2D p1, Point2D p2) 
{ 
    return (float)Math.pow((p1.getX() - p2.getX()) + (p1.getY() - p2.getY()), 2); 
}

我鬆散以下算法這裏解釋：http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

，並用僞不同的資源在這裏：

http://i.imgur.com/XYDTfBl.png

我不能改變函數的返回類型，或添加任何新的論點。

感謝您的幫助！

來源

2016-03-11 KingDan

我想通了 - 削減了大量的時間。 distanceSq功能是錯誤的。最好使用Java的Point2D somepoint.distanceSq(otherpoint);方法。

至於n爲3的原始蠻力（在這種情況下它只會是3或2），線性搜索更好，更有效。

在蠻力條件之後，針對min變量的檢查在內部for循環中也是錯誤的。使用平方距離很好，但min未平方。它保留了原始距離，這意味着min必須在兩次檢查（一次在外部循環中，一次在每次檢查的內部）中平方根。

所以，

if ((p.getX() - q.getX()) < min)

應該

if ((p.getX() - q.getX()) < Math.sqrt(min))

同去的其他檢查。

感謝您的回答！

來源

2016-03-21 22:52:55 KingDan

你可以做幾件事。

首先，通過將第二次迭代更改爲僅在「提醒」點上運行，您可以非常簡單地減少程序運行所需的時間。這有助於避免爲每個值計算(i,j)和(j,i)。要做到這一點，只需更改：

for (int j = 0; j < arr.length; j++)

到

for (int j = i+1; j < arr.length; j++)

這仍將是O(n^2)雖然。

您可以通過迭代點並將每個點存儲在智能數據結構（kd-tree最有可能）中來實現O(nlogn)時間。在每次插入之前，找到已存儲在DS中的最近點（kd-tree在O(logn)時間內支持此點），並且它是最小距離的候選對象。

來源

2016-03-11 07:22:28 amit

我的TA說應該有多少次執行的基本操作減少了如下行： 'if（（p.getX（） - q.getX（）） KingDan

幾毫秒？現在幾點，你想要得到什麼。就像我說的，爲了獲得真正的漸進式改進 - 您應該使用k-d樹。 – amit

有2秒的上限。顯然它應該能夠在那個時間通過一個10萬的測試用例。 – KingDan

我相信鏈接算法提到按一個座標對數組進行排序，以便在點1到2000給定LHS q，如果點200處的RHS p距離距離只有它的x距離大於'min'距離，則可以避免檢查剩餘的201到2000點。

來源

2016-03-11 07:30:18 softwarenewbie7331

如何使兩點之間的最短路徑算法更快？

回答

相關問題