2016-03-11 6 views
6

私はこのアルゴリズムを書いています。それは(少なくとも私の短いテストケースでは)機能しますが、大きな入力には時間がかかりすぎます。どうすれば速くすることができますか?私は緩くアルゴリズムを以下の午前どのように2つのポイントアルゴリズム間の最短経路をより速くするか?

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

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

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

答えて

0

私はそれを考え出しました - 膨大な量で時間を切ってください。 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)) 

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

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

3

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

最初に、「リマインダー」の点でのみ実行するように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)の時刻にこれをサポートしています)。これは最小距離の候補です。

+0

私のTAは、その実行に減少した回数持つべき基本的な動作は次の行であることを言う: '場合 - 私はすでにきた((p.getX()q.getX())<分)' 'min = 0'で初期のexitを追加してあなたの提案を実装しましたが、せいぜい数ミリ秒しか削っていません。その他のアイデアは? – KingDan

+0

何ミリ秒?今は何時頃、何を得ようとしていますか?私が言ったように、真の漸近的な改善を得るためには、k-dツリーを使うべきです。 – amit

+0

2秒のキャップがあります。明らかに、その時間の下で100 000のテストケースを通過することができるはずです。 – KingDan

0

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

関連する問題