Shortest path crossing unique x points
Given a set of Y Points (locations) with Longitude and Latitude, what is the shortest path that crosses a Unique set of X points?
Just a algorithm problem I was having when designing a database. Not sure how to proceed or if there is an elegant solution to this problem. Please help! Thanks!
Edit: This is not the Travelling Salesmen Problem, it is not the shortest path visiting ALL the locations, but just any unique set that crosses X points.
For example, if we had 2000 locations, what's the shortest path that will visit any 10 locations?
The size of X will be very small compared to the overall set of Y.
I would put my data into an R* Tree then run a DBSCAN algorithm over it to break it down into clusters O(n * lg(n)). Once the points have been clustered you can then find the cluster that's closest in size to the number of points you want to find the shortest path between. Since you've broken everything down to just 10 points you have two options you can either: Solve the Traveling Salesman Problem for the points which is slow O(n!) and precise, or take the leftmost point and get the shortest path to the rightmost point using Dijkstra's algorithm which is much faster O(E + V * log(V)) but doesn't give you the optimal result.
EDIT!
As pointed out in the comments below using Dijkstra's algorithm here would result in O(n!+V * log(V)) since any path between two points is an edge. It would be faster to use the Held–Karp algorithm to solve the TSP which runs O(n^2 * 2^n)
链接地址: http://www.djcxy.com/p/63504.html下一篇: 穿过唯一x点的最短路径