我有一组点和距离函数适用于每对点.我希望将所有点连接在一起,并保持最小总距离.你知道我可以使用的现有算法吗？
每个点都可以链接到几个点,所以这不是通常的"推销员行程"问题:)
谢谢 !
正如其他人所说,最小生成树(MST)将允许您形成连接所有点的最小距离子图.
您首先需要为您的数据集构建一个图表.要有效地形成无向图,您可以计算点集的Delaunay三角剖分.从三角测量到图形的转换是相当文字的 - 三角测量中的任何边缘也是图中的边缘,由三角测量边缘的长度加权.
MST(Prim's/Kruskal O(E*log(V)))和Delaunay三角测量(Divide and Conquer O(V*log(V)))阶段都有高效的算法,因此可以实现高效的整体方法.
希望这可以帮助.
| 归档时间： |
|
| 查看次数： |
7753 次 |
| 最近记录： |