BUILT-IN MATHEMATICA SYMBOL

FindShortestTour

attempts to find an ordering of the

that minimizes the total distance on a tour that visits all the

once.

MORE INFORMATION

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:

	DistanceFunction	the distance function to apply to pairs of objects
	Method	the 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.

EXAMPLES

CLOSE ALL

Basic Examples (2)

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]:=

Out[1]=

Specify a list of points:

In[1]:=

In[2]:=

Out[2]=

Order the points according to the tour found:

In[3]:=

Out[3]=

Plot the tour:

In[4]:=

Out[4]=

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 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:

Applications (6)

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:

Neat Examples (1)

Plan a tour through every country of the world:

Visualize the tour: