在单位正方形上的均匀点上找到连通距离的算法

Question

情况

假设我们在单位正方形[0,1]x [0,1]上给定n个点和一个正实数r。我们定义图G(点1，点2，...，点n，r)为顶点{1、2、...、n}的图，如果且仅当相应点之间的距离小于或等于r时，则连接两个给定的顶点。 （您可以将这些点视为发射器，只要它们在范围内r内就可以相互通信。）

给定单位正方形[0,1]x [0,1]上的n个点，我们将连通距离定义为G（点1，点2，...，点n，r）连接所需的最小r。

问题1）找到一种算法，确定是否连接了G(点1，点2，...，点n，r)

问题2）找到一种算法，查找任何给定点的连通距离n

我的部分解决方案

我有一个算法（算法1）可解决问题1。我还没有实现它，但我相信它有效。 （大致上，这个想法是从顶点1开始，并通过边尝试到达所有其他顶点。我认为它会与这个有些类似。）

问题2仍未解决。我也有一个算法。然而，我认为它的时间效率不高。我将尝试解释其工作原理：

您必须首先确信连通距离r_min必然是给定点之间的距离，例如p和q。因此，r_min可能的值最多为*n*（n-1）/ 2。

因此，首先，我的算法将测量所有*n*（n-1）/ 2个距离并按升序存储它们（例如在C中的数组中）。然后，它将使用算法1测试每个存储的值（按升序）以查看图形是否在该范围内连接。做好工作的第一个值是答案，r_min。

我的问题是：对于问题2是否有更好（时间上）的算法？

备注: 这些点将会随机生成（大概有10000个），所以算法应该能够快速解决这种类型的问题。此外，我将使用C语言来实现它。（如果这有任何不同之处。）

- Detached Laconian

Answer 1

这是一个需要花费O(n2)时间和O(n)空间的算法。

它基于这样一种观察：如果将点分为两个集合，则连通距离不能小于从分区中每个集合中最近的一对点的距离。换句话说，如果我们通过始终添加最接近的点来建立连接的图，则我们添加的最大距离将是连通距离。

步骤如下：

1. 创建两个集合A和B。将一个随机点放入A中，其余所有点都放入B中。

2. 初始化r（连通距离）为0。

3. 使用A中的点到B中每个点的距离初始化地图M。

4. 当仍有B中的点时：

- 选取B中距离M[b]最小的点b。 - 如果M[b]大于r，则将r设置为M[b]。 - 将b从B中移除并将其添加到A中。 - 对于M中的每个点p： - - 如果p是b，则将其从M中删除。 - - 否则，如果从b到p的距离小于M[p]，则将M[p]设置为该距离。

5. 当所有点都在A中时，r将是连通距离。

while循环的每次迭代都需要O(|B|)时间，首先要在M中找到最小值，然后要更新M中的值。由于每次迭代都将一个点从B移动到A中，所以确切地说有n次迭代，因此总执行时间为O(n²)。

上述算法是对先前算法的改进，该算法使用了一个（未指定的）解决两色最近点对（BCP）问题的解决方案，在每个循环中重新计算与A最近的邻居。由于有一个O(n log n)的BCP解决方案，这意味着原问题的解决方案是O(n² log n)。然而，维护和更新最近点列表实际上要简单得多，只需要O(n)。感谢@LajosArpad提出的问题引发了这一思路。

- rici

---

看起来是一个很棒的算法！然而，我不熟悉双色最近点对问题，这似乎比我的教练期望我做的更复杂。等我有更多经验时，我会确保去看一下这个。谢谢！ - Detached Laconian

我不完全理解你的想法。你能具体说明一下如何获得足够大以连接网络的最小距离吗？你使用B'将元素从B迁移到A，但是这个算法如何解决问题？你需要测试有效性吗？如果需要，那么测试频率是多少？每当找到更小的r距离时就进行测试吗？ - Lajos Arpad

@LajosArpad：A中的所有点都是相连的。因此，当所有点都在A中时，它们都已连接。还要注意，如果您将所有点分成两个集合的分区，则连接距离必须至少为连接两个集合的最近点对。 - rici

@rici：我认为最好将您增强版的算法放在答案顶部（甚至替换以前的版本）-这样更简单，更高效。 - maxim1000

@rici，非常感谢您的编辑，我理解并喜欢您的想法。 - Lajos Arpad

Answer 2

我认为你的想法相当不错，但是我有一个改进建议。

实际上，你基于测量结果构建了一个数组，并对其进行了排序。非常好。至少对于不太多的点来说是这样。

n(n-1)/2的数量是你配对要求的逻辑结果。因此，对于10000个元素，你将有49995000个元素。你需要显著提高速度！而且，这么多元素会占用大量的存储空间。

如何实现更快的速度呢？

首先，不要构建数组。你已经有了一个数组。其次，你可以通过遍历轻松解决问题。假设你有一个函数，该函数确定给定距离是否足以连接所有节点，让我们称这个函数为“valid”。这还不够，因为你需要找到最小可能值。因此，如果在执行算法之前没有更多关于节点的信息，那么我的建议是这个解决方案：

lowerBound <- 0
upperBound <- infinite
i <- 0
while i < numberOfElements do
    j <- i + 1
    while j < numberOfElements do
        distance <- d(elements[i], elements[j])
        if distance < upperBound and distance > lowerBound then
            if valid(distance) then
                upperBound <- distance
            else
                lowerBound <- distance
            end if
        end if
        j <- j + 1
    end while
    i <- i + 1
end while

遍历所有元素后，upperBound的值将保存仍连接网络的最小距离。由于距离过多且您已在单个循环中解决了问题，因此未存储所有距离。希望我的回答对您有所帮助。

- Lajos Arpad

---

我非常喜欢你在回答中提供的想法（+1），但我认为这还不足以使问题在计算上可行 - 在我看来，valid 至少是 O(n^2)，再加上你的 O(n^2) 迭代，那就是 O(n^4)，即约 10^16 次操作... 或者你有没有考虑过任何我所忽略的 valid 的聪明记忆化技巧？ - us2012

有上界和下界。这些变量用于缩小问题的空间。如果下界或上界接近解决方案，则不会计算有效值。随机数据很可能是输入，因此在循环的第一次迭代中，相对较大的无效距离和相对较小的有效距离是可能的。当算法找到第一个相对较小的有效距离和相对较大的无效距离时，需要计算有效值的迭代将极为罕见。 - Lajos Arpad

这个算法很简单，利用了生成的点的随机性。我认为它会非常有效地完成工作。谢谢！ - Detached Laconian

Answer 3

如果某个距离可以连接图形，则任何更大的距离也可以连接它。要找到最小连接距离，只需对所有距离进行排序并使用二分查找即可。

时间复杂度为O(n^2 * log n)，空间复杂度为O(n^2)。

- maxim1000

---

假设他/她使用快速排序（复杂度为n * log（n）），那么您的算法必须对距离进行排序，这将是一个巨大的数组。如果n是节点数，则排序的输入为n *（n-1）/ 2。因此，您的算法的复杂度为（n （n-1）/ 2） log（n *（n-1）/ 2）。因此，您的算法的缺点是：1.由于元素数量为n *（n-1）/ 2，如果输入为n，则存在隐藏的复杂度，2.您必须存储所有这些距离。那将使用大量的内存和时间。 - Lajos Arpad

@LajosArpad：同意，我已经在我的答案中添加了时间和空间复杂度。 - maxim1000

在这种情况下，时间复杂度本质上是 n^2 * log(n^2) = 2 * n^2 * log(n)。你的描述是正确的，我只是在证明你的陈述以澄清事情。最后，我们达成了共识，我点赞你的答案。 - Lajos Arpad

Answer 4

你可以从一些小距离d开始，然后检查连通性。如果图形是连通的，那么你就完成了，否则，增加d的小距离，然后再次检查连通性。

你还需要一个聪明的算法来避免在N很大的情况下出现O(N^2)。

- Fernando