如何将这个分治代码转换为将一个点与一个点列表进行比较?

Question

我在网站http://rosettacode.org/wiki/Closest-pair_problem上找到了这段代码，我采用了c#版本的分而治之的方法来找到最近的点对，但我想做的是适应它的使用，只找到最近的点到一个特定的点。我在谷歌上搜索了很多，并在这个网站上搜索了一些例子，但没有一个像这样。我不完全确定要改变什么，以便它只根据一个点检查列表，而不是检查列表以找到最接近的两个点。我想让我的程序运行得越快越好，因为它可能要在数千个点的列表中搜索，以找到最接近我当前坐标的点。

public class Segment
{
    public Segment(PointF p1, PointF p2)
    {
        P1 = p1;
        P2 = p2;
    }
    public readonly PointF P1;
    public readonly PointF P2;
    public float Length()
    {
        return (float)Math.Sqrt(LengthSquared());
    }
    public float LengthSquared()
    {
        return (P1.X - P2.X) * (P1.X - P2.X)
            + (P1.Y - P2.Y) * (P1.Y - P2.Y);
    }
}
    public static Segment Closest_BruteForce(List<PointF> points)
    {
        int n = points.Count;
        var result = Enumerable.Range(0, n - 1)
            .SelectMany(i => Enumerable.Range(i + 1, n - (i + 1))
                .Select(j => new Segment(points[i], points[j])))
                .OrderBy(seg => seg.LengthSquared())
                .First();
        return result;
    }
    public static Segment MyClosestDivide(List<PointF> points)
    {
        return MyClosestRec(points.OrderBy(p => p.X).ToList());
    }
    private static Segment MyClosestRec(List<PointF> pointsByX)
    {
        int count = pointsByX.Count;
        if (count <= 4)
            return Closest_BruteForce(pointsByX);
        // left and right lists sorted by X, as order retained from full list
        var leftByX = pointsByX.Take(count / 2).ToList();
        var leftResult = MyClosestRec(leftByX);
        var rightByX = pointsByX.Skip(count / 2).ToList();
        var rightResult = MyClosestRec(rightByX);
        var result = rightResult.Length() < leftResult.Length() ? rightResult : leftResult;
        // There may be a shorter distance that crosses the divider
        // Thus, extract all the points within result.Length either side
        var midX = leftByX.Last().X;
        var bandWidth = result.Length();
        var inBandByX = pointsByX.Where(p => Math.Abs(midX - p.X) <= bandWidth);
        // Sort by Y, so we can efficiently check for closer pairs
        var inBandByY = inBandByX.OrderBy(p => p.Y).ToArray();
        int iLast = inBandByY.Length - 1;
        for (int i = 0; i < iLast; i++)
        {
            var pLower = inBandByY[i];
            for (int j = i + 1; j <= iLast; j++)
            {
                var pUpper = inBandByY[j];
                // Comparing each point to successivly increasing Y values
                // Thus, can terminate as soon as deltaY is greater than best result
                if ((pUpper.Y - pLower.Y) >= result.Length())
                    break;
                Segment segment = new Segment(pLower, pUpper);
                if (segment.Length() < result.Length())
                    result = segment;// new Segment(pLower, pUpper);
            }
        }
        return result;
    }

我在我的程序中使用了这段代码来查看速度的实际差异，并且分治法很容易获胜。

        var randomizer = new Random(10);
        var points = Enumerable.Range(0, 10000).Select(i => new PointF((float)randomizer.NextDouble(), (float)randomizer.NextDouble())).ToList();
        Stopwatch sw = Stopwatch.StartNew();
        var r1 = Closest_BruteForce(points);
        sw.Stop();
        //Debugger.Log(1, "", string.Format("Time used (Brute force) (float): {0} ms", sw.Elapsed.TotalMilliseconds));
        richTextBox.AppendText(string.Format("Time used (Brute force) (float): {0} ms", sw.Elapsed.TotalMilliseconds));
        Stopwatch sw2 = Stopwatch.StartNew();
        var result2 = MyClosestDivide(points);
        sw2.Stop();
        //Debugger.Log(1, "", string.Format("Time used (Divide & Conquer): {0} ms", sw2.Elapsed.TotalMilliseconds));
        richTextBox.AppendText(string.Format("Time used (Divide & Conquer): {0} ms", sw2.Elapsed.TotalMilliseconds));
        //Assert.Equal(r1.Length(), result2.Length());

Answer 1

您可以将这些点存储在更好的数据结构中，以利用它们的位置。就像四叉树。

你正在尝试使用的分治算法并不真正适用于这个问题。

Answer 2

完全不要使用这种算法，只需逐个遍历列表，比较与参考点的距离，最后返回最接近的点。这是O(n)

你可能可以添加一些额外的加速，但这应该是足够好的。

如果你需要的话，我可以写一些示例代码。

Answer 3

你把两个不同的问题混淆了。分治法解决最接近对问题比暴力破解更快的唯一原因是，它避免了将每个点与其他点进行比较，所以它得到的是O(n log n)而不是O(n * n)，但是找到离一个点最近的点只需O(n)。你如何在n个点的列表中找到最近的点，同时检查少于n个点?你想做的事情根本没有意义。

我不明白为什么你的分而治之比你的蛮力更省时;也许linq实现运行得较慢。但我认为你会发现两件事:1)即使从绝对意义上讲，你执行分而治之的1分方法比执行暴力破解的1分方法运行的时间更短，它们仍然具有相同的O(n)。2)如果你只是尝试一个简单的foreach循环并记录最小距离的平方，你会得到比分治法更好的绝对时间——而且，它仍然是O(n)。

Answer 4

public static float LengthSquared(PointF P1, PointF P2)
{
    return (P1.X - P2.X) * (P1.X - P2.X)
        + (P1.Y - P2.Y) * (P1.Y - P2.Y);
}

如果，如你的问题所述，你想比较一个(已知的)点和一个点列表来找到最近的点，那么使用这个代码。

public static Segment Closest_BruteForce(PointF P1, List<PointF> points)
{
    PointF closest = null;
    float minDist = float.MaxValue;
    foreach(PointF P2 in points) 
    {
       if(P1 != P2) 
       {
           float temp = LengthSquared(P1, P2);
           if(temp < minDist) 
           {
               minDist = temp;
               closest = P2;
           }
       }
    }
    return new Segment(P1, closest);
}

然而，如果如你的例子所示，你想从一个点列表中找到最近的2个点，试试下面的方法。

public static Segment Closest_BruteForce(List<PointF> points)
{
    PointF closest1;
    PointF closest2;
    float minDist = float.MaxValue;
    for(int x=0; x<points.Count; x++)
    {
        PointF P1 = points[x];
        for(int y = x + 1; y<points.Count; y++)
        {
            PointF P2 = points[y];
            float temp = LengthSquared(P1, P2);
            if(temp < minDist) 
            {
               minDist = temp;
               closest1 = P1;
               closest2 = P2;
            }
        }
    }
    return new Segment(closest1, closest2);
}

注意上面的代码是在浏览器中编写的，可能有一些语法错误。

---

编辑奇怪……这是一个可以接受的答案吗?