FindShortestTour
FindShortestTour[{v1,v2,…}]
attempts to find an ordering of the vi that minimizes the total distance on a tour that visits all the vi once.
FindShortestTour[graph]
attempts to find an ordering of the vertices in graph that minimizes the total length when visiting each vertex once.
FindShortestTour[{v1,v2,…},j,k]
finds an ordering of the vi that minimizes the total distance on a path from vj to vk.
FindShortestTour[graph,s,t]
finds an ordering of the vertices that minimizes the total length on a path from s to t.
FindShortestTour[{vw,…},…]
uses rules vw to specify the graph g.
Details and Options
- FindShortestTour is also known as the traveling salesman problem (TSP).
- FindShortestTour returns a list of the form {dmin,{vi1,vi2,…}}, where dmin is the length of the tour found, and {vi1,vi2,…} is the ordering.
- The following options can be given:
-
DistanceFunction Automatic function to apply to pairs of objects Method Automatic method to use - Automatic settings for DistanceFunction depending on the vi include:
-
EuclideanDistance numbers of lists of numbers EditDistance strings GeoDistance geo positions - For graph, the distance is taken to be GraphDistance, which is the shortest path length for an unweighted graph and the sum of weights for a weighted graph.
Examples
open allclose allBasic Examples (3)
Scope (7)
Options (3)
Applications (3)
Properties & Relations (2)
Possible Issues (1)
Neat Examples (1)
See Also
FindHamiltonianCycle FindHamiltonianPath FindShortestPath FindPath FindPostmanTour FindEulerianCycle FindMinimum NMinimize Nearest FindCurvePath