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
Query:
Andrew James
Parker Adams
What part of this is not in the "full" salesman problem?
Aaron Howard
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
Thomas Powell
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....
Matthew Carter
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
Dominic Baker
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.
Brandon Hill
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
Jack Morris
Good point actually
Tyler Morales
>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...
Nicholas Cox
It feels like for a figure-eight geographic distribution of customers, a figure-eight path would also be the shortest solution.