Menu
Does there exist a travelling salesman problem where the optimal solution has edges that cross?
The nodes are in an x-y plane, so crossing in this case means if you were to draw the graph, two line segments connecting four separate nodes would intersect.
526
The traveling salesman problem (TSP) is a classical problem of combinatorial optimization. In the TSP, one is given a n × n distance matrix C = ( c i j ) and looks for a cyclic permutation of the set { 1 , 2 , … , n } that minimizes the function c ( τ ) = ∑ i = 1 n c i τ ( i ) .
To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes. Calculate the distance of each route and then choose the shortest one—this is the optimal solution.
However, this is extremely time consuming and as the number of cities grows, brute force quickly becomes an infeasible method. A TSP with just 10 cities has 9! or 362,880 possible routes, far too many for any computer to handle in a reasonable time.
Scientists in Japan have solved a more complex traveling salesman problem than ever before. The previous standard for instant solving was 16 “cities,” and these scientists have used a new kind of processor to solve 22 cities. They say it would have taken a traditional von Neumann CPU 1,200 years to do the same task.
If two edges in a closed polygonal line cross, then there is a polygonal line with the same vertices but with smaller perimeter. This is a consequence of the triangle inequality. So, a solution to the TSP must be a simple polygon. See this article (Figure 4).
61
If you consider a non-Euclidean metric like L1 (Manhattan distance), then it's pretty easy to construct shortest tours that self-intersect.
+--3--+
| | |
| | |
2--+--1
| | |
| | |
+--4--+
If each neighboring pair of intersections is at distance 1, then all tours have length 8, including the self-intersecting one that goes 1 --> 2 --> 3 --> 4 --> 1.
3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
