经典MST问题
在最小生成树(mst)问题的经典公式中,我们给出了顶点集v和边集e。尽管有
可能边给定v个顶点,边的数目通常比m小得多。
我的问题:边集是隐含的,而不是给定的
在我的例子中,我有一组v顶点,其中每个顶点是二维平面上的一个坐标(x,y)。我一点边也没有,也就是说,集合e是空的实际上,我知道所有M条边及其距离:它是每个可能的顶点对之间的距离因此,已知边的大小是最大的,即,E=m。
我的难题是:如果v的大小非常大(例如10000),那么m的值增长得非常快。尝试使用v=10000和e=m=50000000的mst算法可能会导致严重的算法效率问题。
在运行MST算法之前,是否有一种方法从最大边集E中删除/修剪/删除边缘,减少寻找“满意”(即,不一定是最优的)MST所需的时间?
可能的启发式
有一种可能性:
给定顶点集v,计算边界矩形
将矩形分割成r个较小的矩形
例如,将矩形垂直和水平分为四(4)个范围,生成十六(16)个较小的矩形
对于每个子矩形,从子矩形中的所有顶点计算MST。
连接生成的mst以生成一个大型mst。
有谁能提出一个有效的算法来产生一个满意的MST只给出一组顶点吗?
最佳答案
听起来你想计算一个Euclidean minimum spanning tree。
维基百科包含了更有效的o(nlogn)算法,基于以下关键思想:
在平面中寻找emst的一个更好的方法是注意到它是n个点的每个delaunay三角剖分的一个子图,一组大大减少的边: