Как сделать кратчайший путь между двумя точками алгоритма быстрее?

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 должен быть квадратным корнем в обеих проверках (один раз во внешнем цикле, один раз во внутреннем для каждой проверки).

Так,

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

Должно быть

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

То же самое относится и к другим чеком.

Спасибо за ваши ответы всем!

Answer 2

Есть несколько вещей, которые вы можете сделать.

Во-первых, вы можете просто сократить время, которое программа выполняет для запуска, изменив вторую итерацию, чтобы работать только в точках «напоминания». Это поможет вам избежать вычисления как (i,j), так и (j,i) для каждого значения. Чтобы сделать это, просто изменить:

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

в

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

Это все равно будет O(n^2) хотя.

Вы можете достичь O(nlogn) времени, повторяя точки и сохраняя их в интеллектуальной структуре данных (скорее всего, kd-tree). Перед каждой вставкой найдите ближайшую точку, уже сохраненную в DS (kd-дерево поддерживает это в O(logn) времени), и это ваш кандидат на минимальное расстояние.

Answer 3

Я считаю, что связанный алгоритм упоминает сортировку массива по одной координате так, чтобы данный LHS q в пунктах 1-2000, если RHS p в точке 200 больше, чем «мин» расстояние с только его расстоянием x, вы можете избежать проверяя оставшиеся 201 до 2000 пунктов.