どのように2つのポイントアルゴリズム間の最短経路をより速くするか？

Question

私はこのアルゴリズムを書いています。それは（少なくとも私の短いテストケースでは）機能しますが、大きな入力には時間がかかりすぎます。どうすれば速くすることができますか？私は緩くアルゴリズムを以下の午前

// 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

を、私は、関数の戻り値の型を変更したり、追加することはできません。新しい引数。

ありがとうございました！

Answer 1

私はそれを考え出しました - 膨大な量で時間を切ってください。 distanceSq関数が間違っています。代わりにJavaのPoint2D somepoint.distanceSq(otherpoint);メソッドを使用するのがベストです。

nが3のときの元々のブルートフォース（そのシナリオでは3または2に過ぎません）では、線形検索がより効果的で効果的です。

変数minとのチェックは、ブルートフォース状態の内側のforループでも間違っています。二乗距離の使用は問題ありませんが、minは二乗されません。これは元の距離を保持しています。つまり、minは、両方のチェックで平方根にする必要があります（外側のループで1回、チェックごとに内側で1回）。

ので、

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

は

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

同じ他のチェックのために行くであるべき。

皆様お返事ありがとうございます！

Answer 2

できることはいくつかあります。

最初に、「リマインダー」の点でのみ実行するように2番目の反復を変更することで、プログラムの実行に要する時間を非常に簡単に削減できます。これは、各値に対して(i,j)と(j,i)の両方を計算するのを避けるのに役立ちます。そのためには、単に変更：

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

へ

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

をこれはまだかかわらず、O(n^2)になります。

ポイントを反復し、それぞれをスマートデータ構造（おそらくkd-tree）に格納することで、O(nlogn)時間を達成できます。各挿入の前に、DSに既に格納されている最も近い点を見つけます（kd-treeはO(logn)の時刻にこれをサポートしています）。これは最小距離の候補です。

Answer 3

リンクアルゴリズムでは、1つの座標で配列を並べ替えると言われているので、ポイント200のRHS pが距離xだけ離れた「min」以上離れていれば、残りの201〜2000点をチェックする。