Built-in Mathematica Symbol

FindShortestTour

FindShortestTour[{e₁, e₂, ...}]
attempts to find an ordering of the e_i that minimizes the total distance on a tour that visits all the e_i once.

MORE INFORMATION

The following options can be given:

	DistanceFunction	the distance function to apply to pairs of objects
	Method	the method to use

The e_i can be numbers or lists of numbers, in which case the default distance function used is EuclideanDistance.

If the e_i 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.

EXAMPLES

CLOSE ALL

Basic Examples (2)

Find the length and ordering of a 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 a shortest tour through six points in the plane:

In[1]:=

Out[1]=

Specify a list of points:

In[1]:=

In[2]:=

Out[2]=

Order the points according to the tour found:

Plot the tour:

Scope (2)

Find the shortest tour through points in 3D space:

Find the shortest tour through a list of strings:

Generalizations & Extensions (1)

Use a DistanceFunction based on a (symmetric) connectivity matrix:

Options (4)

This finds all points on a

grid with coordinates that are coprime:

Find the shortest tour using "OrZweig" method, the default for 2D real inputs:

Finding shortest tour using "OrOpt" method, the default for non-2D or nonreal inputs:

The "TwoOpt" algorithm performs exchanges of edge endpoints for improvement:

"CCA" (Convex hull, Cheapest insertion and Angle selection) intended for points in

ⁿ:

The "Greedy" algorithm moves from one point to the nearest unvisited neighbor:

"GreedyCycle" is a variant of the "Greedy" algorithm with a known upper bound:

"SimulatedAnnealing" 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, and the "river" in red :

This defines a sparse distance matrix among six points and find the shortest tour:

This plot the shortest tour in red, as well as the distance on each edge:

Applications (6)

Find a shortest tour visiting 50 random points in the plane:

Find a shortest tour visiting 100 random points in 3D:

Find the shortest tour through 2D points whose coordinates are relatively prime:

Find a shortest tour for 3D points with relatively prime coordinates:

Find a "shortest tour" through the names of countries in Europe:

Find a traveling-salesman tour of Europe:

Neat Examples (1)

Plan a tour through every country of the world:

Visualize the tour: