w******t
发帖数: 241 | 1 如果在一个边长为D的正方形区域内，随机分布了k个点，那么MSP大概多少？function
（k，D）怎么表示？另外计算MSP有没有什么比较快的实现算法（不是greedy类型的）
？ |
l******e
发帖数: 470 | 2 MST
O(D\sqrt{k})
Prim algorithm or kruskal algo |
v********e
发帖数: 1058 | 3 Prim和Kruskal都是greedy algorithm吧
【在 l******e 的大作中提到】
: MST
: O(D\sqrt{k})
: Prim algorithm or kruskal algo
|
K****n
发帖数: 5970 | 4 但是它们都可以被证明, 是greedy又有什么关系? |
c****r
发帖数: 185 | 5 用归纳法。第k个点与其余k-1个点的最短距离大概是 D/sqrt(k)。
所以
MSP_k = MSP_{k-1} + D/sqrt(k)
= ...
= D * (1 + 1/sqrt(2) + ... 1/sqrt(k)) |
c****r
发帖数: 185 | 6 这两个算法只能在图上使用。原文定义在一个平面上。
可以用kd-tree来算MST：
每次插入一个点，然后做nearest neighbor query。
插入和查询需要O(log(k)) time，总共 O(1+log(2)+..+log(k))
【在 v********e 的大作中提到】
: Prim和Kruskal都是greedy algorithm吧
|
h*******e
发帖数: 225 | 7 Construct the Delaunay triangulation of the n points, the result is a
graph with O(n) edges. Then you can run Prim or Kruskal on it and get the
Euclidean MST.
【在 c****r 的大作中提到】
: 这两个算法只能在图上使用。原文定义在一个平面上。
: 可以用kd-tree来算MST：
: 每次插入一个点，然后做nearest neighbor query。
: 插入和查询需要O(log(k)) time，总共 O(1+log(2)+..+log(k))
|
