2

This question has been asked a few times in similar ways, but none of the existing answers that I found is of practical help for me.

Problem: I have a fixed starting point, a fixed destination point, and many destination points in between. Starting at the desired starting point, I want to calculate the shortest possible route that travels along all destination points and ends at the a given destination point.

For the particular problem I have to solve, I need a very fast solution. I was thinking of Floyd-Warshall algorithm would fit, to my understanding my problem is related to the all-pairs shortest-path problem.

However, I do not know how these would scale with the data I have (hundreds of intermediate destinations per route are possible, to be calculated on a smartphone).

I'm also thinking if this can be translated into a classical TSP problem (and back again), so I could use i.e. the Concorde TSP library which is said to have excellent performance.

So: Can you recommend me a definitive best solution to my problem, and also some C++ code to give me a start?

benjist
  • 2,740
  • 3
  • 31
  • 58
  • 1
    Finding fast enough approximate solutions for a specific NP-hard problem is more an art form than an exact science. One has to weigh trade-offs between speed and accuracy and utilize improvements specific to the problem's details. In such situation I would be thrilled to get a hint on how to find an applicable idea, and you are asking for C++ code. :) – Michael Nov 26 '13 at 00:09
  • There is no way to give you even a hint on the subject, because the solution is based on the data you have. But from what you're saying it **IS** a TSP problem. So if you have an library, why not just use it and see? – Paweł Stawarz Nov 26 '13 at 00:13
  • @Michael I know. That's why I threw Concorde into the mix, as it is probably the best in class library in regards to heuristics / optimality and performance. But probably my thought of translating my problem to a classical (S)TSP problem is naive. – benjist Nov 26 '13 at 00:15
  • Do you want to visit each intermediate point only once, or any number of times? – Bernhard Barker Nov 26 '13 at 00:20
  • @Dukeling Visitng the same node again is allowed (therefore no classical TSP), only overal length of route matters. – benjist Nov 26 '13 at 00:23
  • Assuming triangle inequality holds, if you need to visit all nodes anyway, then obviously you would want to visit each node **exactly** once, because if you visit any node more than once you should remove it to get shorter path. From your comment that it involves "houses, trees, etc" it seems that you're working on Euclidean distance, in which triangle inequality holds. So this problem is essentially TSP. – justhalf Nov 26 '13 at 06:47
  • 1
    @justhalf: I think question is too broad. Vote to close. – Micromega Jun 16 '14 at 11:02
  • The use-case is quite well defined: Given a fixed start point, given a fixed end point, n waypoints in between, compute shortest path. Still too broad? – benjist Jun 16 '14 at 12:43

3 Answers3

0

The fact that you have a fixed, different end-point doesn't make the problem any easier. If we can find a polynomial-time algorithm to solve this problem, we can simply set each of the nodes as the end-point, solve all those problems, find the best solution (by adding the cost back to the start-point to each), and we'd have a polynomial-time algorithm for the (classic) TSP problem.

Allowing you to visit nodes multiple times doesn't seem to make the problem much easier. While for a formal proof, one needs to reduce TSP to this (not the other way around), consider when setting the edge cost between any two nodes equal to the shortest path between those two nodes. When you've done this, you'll end up having to basically solve the TSP problem - the optimal solution to this TSP problem should be the optimal solution to the original problem.

While simply using the shortest path may occasionally cause unnecessary repetition of nodes, this won't be the case for the optimal solution, as it will always result in a lower cost to visit a repeated node first before having it implicitly be visited through a shortest path.

To solve this using a TSP solver, consider setting the weight of the edges between each two nodes equal to the shortest path between the two and adding a path from the end-point to the start-point with cost 0.

If this is not possible using the solver you're using, Wikipedia lists a few approaches you can follow.

Performance note:

Yes, I'm suggesting running an all-pairs shortest paths algorithm to get the shortest paths above.

Note that even a (decent) approximate algorithm to the TSP should take a lot longer than solving the all-pairs shortest paths problem, so the relative overhead of first doing that should be minimal.

If you believe this can be solved using all-pairs shortest paths (but I don't think it can), do that instead - it will be a lot faster.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • My use case involves houses, buildings, and streets between them. It doesn't seem correct to rule out being able to go back where you come from. Found this fitting picture on SO (see two red pictures): http://stackoverflow.com/questions/4780110/shortest-one-way-path-through-multiple-nodes?lq=1 – benjist Nov 26 '13 at 00:43
  • @benjist If we create edges between all the nodes with the shortest path between the nodes as edge weight, this will allow it to revisit nodes (because one edge won't necessarily just be a direct travel between two nodes, it can actually involve many more nodes, but the algorithm won't know about them). – Bernhard Barker Nov 26 '13 at 00:50
  • Any explanation for the downvote? – Bernhard Barker Jun 14 '14 at 16:36
  • 1
    No idea why this got downvoted. While I still didn't implement and check this (and therefore didn't accept your answer yet), it seems a good idea. I don't understand the downvoters these days - I also consider my question as non-trivial but still I get minus points. Also: Delayed thanks for your answer ;) – benjist Jun 14 '14 at 17:14
  • Not the downvoter, but I guess the method you describe is not a correct way to reduce this to TSP, since if you set the cost between two nodes to be the shortest path, as you said, it will actually have to traverse through other intermediate nodes which the algorithm doesn't know, which is effectively making the problem more difficult for the solver. If we knew in advanced that there is no direct path between two nodes, then just put infinity, because the solver will find the intermediate node anyway. And as I said in comment, revisiting node is unnecessary, it won't be in any solution. – justhalf Jun 16 '14 at 11:26
  • @justhalf Consider having one point in the middle connected to each other point and either no other connections, or connections with costs much higher (such that picking them will *never* be a good idea) - in this case, we can only / it would be much better to repeatedly visit the point in the middle, and indeed the shortest path between two points would be through the point in the middle. – Bernhard Barker Jun 16 '14 at 11:35
  • Ah, I see. Yes, my assumption of triangle ineq may not always there in incomplete graph – justhalf Jun 16 '14 at 11:54
-1

The problem you are trying to solve is n-p complete and TSP(Travelling Salesman Problem) can be reduced to it and TSP is n-p complete so is it. But you can do better than brute force to solve this problem which is by using Dynamic Programming algorithm give by Held-Karp for TSP with slight modification which solves it in O(2^N) which far better than brute force which is O(N!). But than it also has similar space complexity. If in case you are doing this for practical application then you can certainly use heuristic algorithms like Genetic Algorithm,Ant Colony optimization which give good solution which cannot be proved optimal but are very close.

Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19
-2

I would not recommend converting this problem to Travelling Salesman. That would impose extra requirements for solutions, like you can only visit each intermediate destination point once, which based on your description is not a requirement. More than that though, TSP is NP-Hard whereas the All-Pairs Shortest Path Problem can be solved in polynomial time.

If it is indeed the All-Pairs Shortest Path Problem, your best bet would probably be to use either the Floyd-Warshall algorithm or Johnson's Algorithm, both of which can solve the problem in polynomial time.

If the problem is actually the Travelling Salesman problem and you are trying to solve it quickly, you will need to get an approximate solution. In my experience with TSP, using a simple greedy search yields pretty good results and is really simple to code up. There are methods for computing the exact answer but these are VERY costly. If you want better results than those provided with a greedy approach, I have had good luck with using Ant Colony Optimization to calculate approximate answers.

Nick Ryhajlo
  • 1
  • 2
  • Once you have all shortest paths, how are you going to find the shortest path from the start point to the end point, while visiting all the other nodes? – Bernhard Barker Nov 26 '13 at 00:24
  • I am not sure I understand your question, sorry. – Nick Ryhajlo Nov 26 '13 at 00:31
  • All-Pairs Shortest Paths gives you a list of shortest paths. How are you going to use this to solve the given problem? (the question mentions that the problem might be related to the All-Pairs Shortest Paths problem, but doesn't say how) – Bernhard Barker Nov 26 '13 at 00:51