2
$\begingroup$

I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of nodes, say, o_1..o_n, which CAN but do not NEED to be included in the route (see picture).

Travelling Salesman Problem with unknown shortest paths between nodes

i.e., this means, in the graph, I do not know the shortest paths between the nodes n_1..n_n which I want to travel.

Is there a more elegant way to retriev a relativley optimal solution than transforming the original graph into a graph only including the nodes n_1..n_n (e.g. by solving the shortest path problem for each pair of nodes [n_i|n_j]) and then using e.g. an evolutional algorithm to get a solution for the TSP?

$\endgroup$
  • $\begingroup$ It looks like nested graphs. 0_ graph nested in n_ graph, as you have multiple paths between n_ nodes e.g. n1 -> 02 -> n2 or n1 -> o1 -> n2 it will good start to solve this issue and eliminate one of o_ nodes $\endgroup$ – Faraz May 25 '16 at 14:37
  • $\begingroup$ It sounds like you already have an elegant solution to your problem, so I'm not sure what more you are looking for or why you are unhappy with the solution you already have. What do you mean by "more elegant"? Elegant is often in the eye of the beholder, and subjective questions tend not to work well here. If you already know how to solve your problem, what is left to answer here? $\endgroup$ – D.W. May 27 '16 at 0:07
  • 1
    $\begingroup$ The biggest problem I am seeing is the runtime. So, to get the shortest path between each pair of nodes, e.g. via Bellmann-Ford, i have to iterate an algorithm with O((n+o)*m) complexity n(n+1)/2 times. So basically, something with O(n^2*(n+o)) complexity, which is quite a lot when having big graphs, before i even get to the TSP. This is why I wanted to know, if there is a solution combining both problems and thus reducing the overall runtime needed to solve the problem. (And this is what I meant by "elegant". $\endgroup$ – Jannik Michel Jun 1 '16 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.