I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that every optimal TSP solution contains no intersections.
How many non-intersecting routes could be there? Or in other words: what is the probability to guess an optimal solution to a TSP problem if we just enumerate or sample non-intersecting routes?
Edit: I want to ignore the case that D.W. mentioned. For every path that you can swap between two neighbors vertices(If we represent the path as an array of vertices so neighbors will be two vertices with consecutive indexes) without changing its non-intersecting quality, all of those paths will be considered as one.
Edit I found that this kind of removing crossings from the graph also know as 2-OPT