You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
The Traveling Salesman Problem 2: 2-opt Removal of Intersections
The Traveling Salesman Problem 2: 2-opt Removal of Intersections
The traveling salesman problem (TSP) is the most famous combinatorial optimization problem. Its task is to find a tour through a set of vertices in the plane with the shortest possible total length. This Demonstration explores a method that helps in attaining the optimal minimum. It is based on the removal of intersections in a path to decrease its length, relying on the following fact: given points on the plane, no three of which are collinear, there exists a closed path with no self-intersections having those points as vertices of minimal length. This method is called 2-opt and was proposed in 1958 as a way to solve the TSP. Although 2-opt does not give the optimum path, it often improves a given path. This Demonstration generates a random path and applies the method repeatedly to it, comparing the initial and final lengths obtained.
n