Query:
Will the shortest path using the travelling salesman rules ever cross itself?
Because before reading any papers, my intuition says "no" since if the path crosses that means you backtracked at some point, which means it cant be the shortest possible path....
Other urls found in this thread:
It can cross. If a node is hanging you have to go back to his previous node
Sorry I should be a bit more specific:
With a given matrix of dots that you can travel from one to ANY other dot (no limited movement)
And you need to traverse it with salesman rules (visit every dot once and get back to start)
Will your shortest path ever cross itself?
I imagine that each dot has a weight of some kind.
If there are negative weights one could decide to go back to a previous visited dot
>Will your shortest path ever cross itself?
Aren't those two independent conditions? While it's possible the shortest may never cross itself, I think it's more likely that it will, since "not crossing itself" is just an uneccesary constraint.
In fact, like said, if you have hanging nodes you definitely will have to cross them again
>if you have hanging nodes
its like you have zero reading comprehension, OP clearly stated that all nodes are perfectly interconnected to all other nodes.
Yes but I star graph is a interconnected graph where all weights but those towards a node have a infine value
*a star graph not I
All points are just coordinates, so you can freely travel anywhere on the map.
Basically, find the shortest path to visit every coordinate from a set, everything 100% interconnected.
In this case yes, there is no reason. But this is not the full salesman problem either, I'm not sure but I suppose it can be solved in polynomial time as well
What part of this is not in the "full" salesman problem?
Your version imposes geometric relationship between weights of paths between dots.
3 points describe a triangle so one side depends on the others. This adds a huge quantity of informations that is not present in the normal version where each edge can have any weight
The 'weight' is the distance between the dots -.-;
Dont overcomplicate it.
Shortest path between a set of dots, no weighting, just actual shortest path algorithm.
Will the shortest path ever cross itself?
I feel like the shortest path visiting each point once will ALWAYS form an n sided polygon with no crossing points, drawing a perimeter....
I found an exception, if the dots position collapses to a line, then you have to go back to previous locations. Not sure that counts tho
Reading the thread you're talking about the Euclidean variant of TSP. No, in Euclidean TSP the shortest path will never cross over itself. Many solvers use this as a way to quickly test if a path can be shorter. If two line segments cross, connections are swapped between points to avoid the cross, leaving the path still fully connected but shorter. Additional methods are used to shorten the path further.
In non-Euclidean TSP, they can cross in that a node is visited multiple times. As above, a cross results in a longer path and nodes can be swapped to get a shorter path. TSP does not bound you on multiple node visitations, however usually multiple visits result in a longer path.
The proof is: let be the list L the list node visited that solves the problem. If the node n appears in the list twice, with the indices i and o, then one of the 2 can be removed because dis(L[o-1], L[o+1] ) < dis(L[o-1], L[o] ) + dis(L[o], L[o+1] ). (same thing for i). The one that has to be removed is the one that improves the solution the most
Good point actually
>I'm not sure but I suppose it can be solved in polynomial time as well
He's not sure but he supposes that P = NP, guys... STOP THE FUCKING PRESSES.
user, at this point you should probably just stop posting and read a few wiki articles at the very least...
It feels like for a figure-eight geographic distribution of customers, a figure-eight path would also be the shortest solution.
That has a cross in it though and the shorter path would simply connect points without the cross in it. The shortest path is essentially a circle.
you can have traveling salesman with weigths that does not have any topological constraints like you are imposing. this is why people get confused
Yes, it very obviously can in certain graphs. What sort of retarded question is this?
For a straight line set of points, if we're dealing with Euclidean TSP, you don't actually go through any city twice, even though it looks like it. You go through each city once in a linear fashion and then the first and last are connected. Even though that line goes through all the cities on the way back, you never stop at those cities. In non-Euclidean TSP though you'd be right.
Imagine a node that can reach any other node in distance 1. Every other node can reach every other node in 3. Then the fastest way to get from one node to another is to go to the node that can reach others in 1.