穿过唯一x点的最短路径
给定一组具有经度和纬度的Y点（位置），穿过唯一一组X点的最短路径是什么？
仅仅是我在设计数据库时遇到的算法问题。 不知道如何继续，或者是否有一个优雅的解决方案来解决这个问题。 请帮忙！ 谢谢！
编辑：这不是旅游推销员问题，它不是访问所有位置的最短路径，而是任何穿过X点的唯一集合。
例如，如果我们有2000个地点，那么访问任何10个地点的最短路径是什么？
与Y的整体相比，X的大小将非常小。
我会把我的数据放到一个R *树中，然后在它上面运行一个DBSCAN算法将它分解成集群O（n * lg（n））。 一旦点被聚集后，您就可以找到距离想要找到最短路径的点的数量最接近的聚类。 既然你已经把所有东西都分解成了10个点，你可以有两种选择：解决旅行推销员问题，找出缓慢的O（n！）和精确的点，或者走最左边的点，得到最短的路径使用Dijkstra算法的最右点O（E + V * log（V））快得多，但不能给出最佳结果。
编辑！
正如在下面使用Dijkstra算法的评论中指出的那样，由于两点之间的任何路径都是边，所以将导致O（n！+ V * log（V））。 使用Held-Karp算法解决运行O（n ^ 2 * 2 ^ n）的TSP会更快，
链接地址: http://www.djcxy.com/p/63503.html上一篇: Shortest path crossing unique x points
下一篇: no crossing paths