algorithm - 穿过唯一 x 点的最短路径

Question

给定一组具有经度和纬度的 Y 点(位置)，穿过一组唯一的 X 点的最短路径是什么？

只是我在设计数据库时遇到的一个算法问题。不确定如何继续或是否有解决此问题的优雅方法。请帮忙!谢谢!

编辑:这不是旅行商问题，它不是访问所有位置的最短路径，而是任何穿过 X 点的唯一集合。

例如，如果我们有 2000 个位置，那么访问任意 10 个位置的最短路径是什么？

与 Y 的整体集合相比，X 的大小将非常小。

Answer 1

我会将我的数据放入 R* Tree然后运行 ​​DBSCAN将其分解为 O(n * lg(n)) 簇的算法。对这些点进行聚类后，您就可以找到大小最接近您想要找到最短路径的点数的聚类。由于您已将所有内容分解为 10 个点，因此您有两个选择: 解决 Traveling Salesman Problem对于慢速 O(n!) 和精确的点，或者取最左边的点并使用 Dijkstra's algorithm 获得到最右边点的最短路径这要快得多 O(E + V * log(V)) 但不会给你最佳结果。

编辑!

正如下面的评论中所指出的，在这里使用 Dijkstra 算法会导致 O(n!+V * log(V))，因为两点之间的任何路径都是边。使用Held–Karp算法求解运行O(n^2 * 2^n)的TSP会更快