如何使两点之间的最短路径算法更快？

Question

如何使两点之间的最短路径算法更快？

6

我写了这个算法。在我的短测试用例中它可以工作，但是对于更大的输入太慢了。我该如何让它更快？

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

我无法更改函数的返回类型或添加任何新的参数。

感谢您的帮助！

- Dan

3个回答

0

我找到了解决方法 - 大大缩短了时间。 distanceSq 函数是错误的。最好使用 Java 的 Point2D somepoint.distanceSq(otherpoint); 方法。

至于当 n 为 3 时的原始蛮力算法（在这种情况下它只会是 3 或 2），线性搜索更好、更有效。

在蛮力条件之后，内部 for 循环中对 min 变量的检查也是错误的。使用平方距离是可以的，但是 min 不是平方的。它保留了原始距离，这意味着在两个检查中都必须对 min 进行平方根运算（一次在外循环中，一次在内循环中的每个检查中）。

所以，

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

应该是

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

其他检查也是一样的。

谢谢大家的回答！

- Dan

0

我相信链接的算法提到了通过一坐标对数组进行排序，使得在给定LHS q为点1到2000时，如果RHS p在点200处与'min'距离以上只有它的x距离，那么你可以避免检查剩余的201到2000个点。

- softwarenewbie7331

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

你可以做几件事情。

首先，你可以通过修改第二个迭代，仅在“余数”点上运行，从而非常简单地缩短程序运行时间。这有助于避免为每个值计算(i,j)和(j,i)。要这样做，只需更改：

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

to

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

这仍然是O(n^2)的时间复杂度。您可以通过迭代点并将每个点存储在智能数据结构（最可能是kd-tree）中来实现O(nlogn)的时间复杂度。在每次插入之前，在DS中找到已经存储的最近点（kd-tree可以在O(logn)的时间内支持此操作），它是最小距离的候选者。