This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.2)

FindShortestTour

FindShortestTour
attempts to find an ordering of the that minimizes the total distance on a tour that visits all the once.
  • FindShortestTour returns a list of the form , where is the length of the tour found, and is the ordering.
  • The following options can be given:
DistanceFunctionthe distance function to apply to pairs of objects
Methodthe method to use
  • The can be numbers or lists of numbers, in which case the default distance function used is EuclideanDistance.
  • If the are strings, the default distance function used is EditDistance.
  • For small numbers of points, FindShortestTour will usually find the shortest possible tour. For larger numbers of points, it will normally find a tour whose length is at least close to the minimum.
  • Possible settings for the Method option include , , , , , , , , , , and .
  • For small numbers of points in the Euclidean space, an method is used, which is guaranteed to give the shortest tour.
Find the length and ordering of the shortest tour through six points in the plane:
Specify a list of points:
Order the points according to the tour found:
Plot the tour:
Find the length and ordering of the shortest tour through six points in the plane:
In[1]:=
Click for copyable input
Out[1]=
 
Specify a list of points:
In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=
Order the points according to the tour found:
In[3]:=
Click for copyable input
Out[3]=
Plot the tour:
In[4]:=
Click for copyable input
Out[4]=
Find the shortest tour through points in 3D space:
Find the shortest tour through a list of strings:
Use a DistanceFunction based on a (symmetric) connectivity matrix:
This finds all points on an grid with coordinates that are coprime:
Find the shortest tour using the method, the default for 2D real inputs:
Find the shortest tour using the method, the default for non-2D or nonreal inputs:
The algorithm performs exchanges of edge endpoints for improvement:
(Convex hull, Cheapest insertion and Angle selection) intended for points in :
The algorithm moves from one point to the nearest unvisited neighbor:
is a variant of the algorithm with a known upper bound:
uses simulated annealing to minimize the tour length:
By default, EditDistance is used for strings:
This finds the shortest tour through 100 points, with a penalty added to cross a "river":
This plots the tour with the "river" in red:
This defines a sparse distance matrix among six points and finds the shortest tour:
This plots the shortest tour in red, and the distance on each edge:
Find the shortest tour visiting 50 random points in the plane:
Find the shortest tour visiting 100 random points in 3D:
Find the shortest tour through 2D points whose coordinates are relatively prime:
Find the shortest tour for 3D points with relatively prime coordinates:
Find the "shortest tour" through the names of countries in Europe:
Find a traveling-salesman tour of Europe:
Plan a tour through every country of the world:
Visualize the tour:
New in 6