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

Question

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

只是我在设计数据库时遇到的算法问题。不知道如何继续，或者是否有一个优雅的解决方案来解决这个问题。请帮忙！谢谢！

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

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

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

Answer 1

我会将我的数据放入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 会更快