4

情况

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

给定单位正方形 [0, 1]x[0, 1] 上的n个点，我们将连接距离定义为连接G(point 1, point 2, ..., point n , r )的最小可能r .

问题 1) 找到一个算法来确定G (point 1, point 2, ..., point 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 中实现这一点。（如果这有什么不同的话。）

4

4 回答 4

3

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

它基于以下观察：如果将点分成两组，则连接距离不能小于分区中每组最近的一对点的距离。换句话说，如果我们总是通过添加最近的点来构建连通图，那么我们添加的最大距离将是连通距离。

  • 创建两个集合，A和B。将一个随机点放入A并将所有剩余点放入B。

  • r将（连接距离）初始化为 0。

  • 用到点 in的M每个点的距离初始化地图。BA

  • 虽然仍有点B：

    • 选择距离最小的点b。BM[b]

    • 如果M[b]大于r，设置r为M[b]

    • b从 中删除B并将其添加到A.

    • p对于中的每个点M：

      • 如果p是b，请将其从M.

      • b否则，如果到的距离p小于M[p]，则设置M[p]为该距离。

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

循环的每一次迭代都while需要时间，首先在（其大小等于 的大小）O(|B|)中找到最小值；其次，更新中的值。由于在每次迭代中都会将一个点从 移动到，因此会有精确的迭代，因此总执行时间为。MBMBAnO(n2)

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

于 2013-03-16T03:57:48.613 回答
2

我认为您的想法相当不错，但是，我对您有一些改进。

实际上，您根据测量建立了一个数组，然后对数组进行了排序。非常好。至少没有太多的分数。

n(n-1)/2 的数量是您的配对要求的逻辑结果。因此，对于 10000 个元素，您将拥有 49995000 个元素。您将需要显着提高速度！此外，这么多元素会占用大量内存。

你怎样才能达到更快的速度？

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

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 的值将保持仍然连接网络的最小距离。你没有存储所有的距离，因为它们太多了，你已经在一个周期内解决了你的问题。我希望你觉得我的回答有帮助。

于 2013-03-16T00:58:56.697 回答
2

如果某个距离使图形连接起来，那么任何更大的距离也会使其连接起来。要找到最小连接距离，只需对所有距离进行排序并使用二分搜索。

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

于 2013-03-16T06:02:22.153 回答
0

您可以从一些小的距离d开始，然后检查连接性。如果图表已连接，则完成，如果没有，则将d增加一小段距离，然后再次检查连接性。

如果N很大，您还需要一个聪明的算法来避免 O(N^2) 。

于 2013-04-08T18:09:54.967 回答