Hi I'm trying to solve TSP (Travelling salesman problem) and I have found some method with one assumption, I need to know where does the SHP start and end. If anyone knows any algorithms or any articles talking about this problem, I'd be glad to know.
#Looking for theorems or lemma about SHP's (shortest hamiltonian path's) first and last vertices
slow musk
tropic ridge
Hi I'm trying to solve TSP (Travelling salesman problem) and I have found some m...
Have you tried Google OR-Tools? It handles TSP variants including fixed start/end points really well. 👀
slow musk
no, I'm looking for a general answer and not fixed start/end points, but given a graph (if hamiltonian), where could be starting/ending points?
tropic ridge
no, I'm looking for a general answer and not fixed start/end points, but given a...
For Hamiltonian paths, try testing peripheral/leaf nodes as endpoints first, or nodes with degree 1-2. If the graph has specific structure, endpoints are often at the ‘edges’ of the graph.
(Sorry, excuse me for the response time, my cat lost me)
slow musk
the graph is complete and weights are any real numbers
I'm not looking for "good" solution but exact one