WOLFRAM

Wolfram 语言与系统参考资料中心

FindShortestTour[{v1,v2,…}]

尝试找到 vi 的一种排序，使得访问所有 vi 一次的总距离最短.

FindShortestTour[graph]

尝试找到 graph 中顶点的的一种排序，使得访问每个顶点一次的总长度最短.

FindShortestTour[{v1,v2,…},j,k]

找到一个 vi 的排序，使得从 vj 到 vk 的总距离最小.

FindShortestTour[graph,s,t]

找到一个顶点的排序，使得从 s 到 t 的路径的总长度最小.

FindShortestTour[{vw,…},…]

使用规则 vw 指定图 g.

FindShortestTour[dataprop,…]

给出了 data 的属性 prop.

更多信息和选项
Details and Options Details and Options
范例  
基本范例  
范围  
选项  
DistanceFunction  
应用  
属性和关系  
可能存在的问题  
巧妙范例  
参见
相关指南
历史
按以下格式引用：

FindShortestTour

FindShortestTour[{v1,v2,…}]

尝试找到 vi 的一种排序，使得访问所有 vi 一次的总距离最短.

FindShortestTour[graph]

尝试找到 graph 中顶点的的一种排序，使得访问每个顶点一次的总长度最短.

FindShortestTour[{v1,v2,…},j,k]

找到一个 vi 的排序，使得从 vj 到 vk 的总距离最小.

FindShortestTour[graph,s,t]

找到一个顶点的排序，使得从 s 到 t 的路径的总长度最小.

FindShortestTour[{vw,…},…]

使用规则 vw 指定图 g.

FindShortestTour[dataprop,…]

给出了 data 的属性 prop.

更多信息和选项

  • FindShortestTour 又称作旅行推销员问题（TSP）.
  • FindShortestTour 返回形如 {dmin,{vi1,vi2,…}} 的列表，其中 dmin 是求得的路径的长度，而 {vi1,vi2,…} 是排序.
  • 在 FindShortestTour[dataprop,…] 中，prop 的可能形式包括：
  • "Elements"最短路径的元素
    "Indices"最短路径的索引
    "Length"最短路径的距离
    {prop1,prop2,…}多种形式列表
    All元素、索引和距离的关联
  • 可以给出下列选项：
  • DistanceFunction Automatic应用于对象对的函数
    MethodAutomatic使用的方法
  • DistanceFunction 基于 vi 的自动设置包括：
  • EuclideanDistance数值列表的个数
    EditDistance字符串
    GeoDistance地理位置
  • 对于 graph，距离被取为 GraphDistance，这是未加权图的最短路径长度，或者加权图的权值总和.

范例

打开所有单元 关闭所有单元

基本范例  (3)

求平面上经过各点的最短路径长度及各点排序：

Wolfram Language code: pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5, 4}};
Wolfram Language code: FindShortestTour[%]

根据得到的路径对点排序：

Wolfram Language code: pts[[Last[%]]]

绘制路径：

Wolfram Language code: Graphics[Line[%]]

从第一个点开始，到第五个点结束的最短路径：

Wolfram Language code: FindShortestTour[pts, 1, 5]

绘制路径：

Wolfram Language code: Graphics[Line[pts[[Last[%]]]]]

求图的最短路径：

Wolfram Language code: g = PolyhedronData["Dodecahedron", "Skeleton"];
Wolfram Language code: FindShortestTour[g]

突出显示路径：

Wolfram Language code: HighlightGraph[g, PathGraph[%[[2]]]]

找到在欧洲从阿尔巴尼亚到西班牙的最短路线：

Wolfram Language code: FindShortestTour[CountryData["Europe"] -> "Elements", Entity["Country", "Albania"], Entity["Country", "Spain"]]

显示这条路线：

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[%]}]

范围  (7)

FindShortestTour 适用于点列表：

Wolfram Language code: FindShortestTour[{{2, 2}, {5, 2}, {5, 3}, {4, 5}, {4, 4}, {3, 2}}]

字符串列表：

Wolfram Language code: FindShortestTour[{"cat", "dog", "do", "cap", "dock"}]

大地测量位置的列表：

Wolfram Language code: FindShortestTour[{GeoPosition[{41, 20}], GeoPosition[{5, 20}], GeoPosition[{49, 32}], GeoPosition[{53, 28}], GeoPosition[{47, 29}]}]

无向图：

Wolfram Language code: FindShortestTour[[image]]

加权图：

Wolfram Language code: FindShortestTour[[image]]

使用规则指定图：

Wolfram Language code: FindShortestTour[{1 -> 2, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 6, 4 -> 5, 4 -> 7, 5 -> 6, 5 -> 8, 6 -> 9, 7 -> 8, 7 -> 10, 8 -> 9, 8 -> 11, 9 -> 12, 10 -> 11, 11 -> 12}]

FindShortestTour 作用于大规模图：

Wolfram Language code: g = RandomGraph[{1000, 5000}];
Wolfram Language code: Timing[FindShortestTour[g]]//Short

选项  (3)

DistanceFunction  (3)

在默认情况下，EditDistance 用于字符串：

Wolfram Language code: FindShortestTour[{"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}]
Wolfram Language code: {"This", "finds", "the", "shortest", "tour", "through", "a", "list", "of", "strings"}[[%[[2]]]]

这里找到经过100个点的最短路径，其中对过“河”会有相应的“惩罚”：

Wolfram Language code: pts = RandomReal[1, {100, 2}];
Wolfram Language code: {len, tour} = FindShortestTour[pts, DistanceFunction -> ((If[(#1[[1]] ≤ .5 && #2[[1]] ≥ .5) || (#2[[1]] ≤ .5 && #1[[1]] ≥ .5), 100000, EuclideanDistance[#1, #2]])&)]

绘制路径，“河”用红色标出：

Wolfram Language code: Graphics[{GraphicsComplex[pts, {Point[Range[100]], Line[tour]}], Red, Line[{{0.5, 0}, {0.5, 1}}]}, Frame -> True, FrameTicks -> Automatic]

这里定义一个六个点上的稀疏距离矩阵，并求得最短路径：

Wolfram Language code: d = SparseArray[{{1, 2} -> 1, {2, 1} -> 1, {6, 1} -> 1, {6, 2} -> 1, {5, 1} -> 1, {1, 5} -> 1, {2, 6} -> 1, {2, 3} -> 10, {3, 2} -> 10, {3, 5} -> 1, {5, 3} -> 1, {3, 4} -> 1, {4, 3} -> 1, {4, 5} -> 15, {4, 1} -> 1, {5, 4} -> 15, {5, 2} -> 1, {1, 4} -> 1, {2, 5} -> 1, {1, 6} -> 1}, {6, 6}, Infinity];
Wolfram Language code: {len, tour} = FindShortestTour[{1, 2, 3, 4, 5, 6}, DistanceFunction -> (d[[#1, #2]]&)]

下面用红色绘出最短路径，以及在各边上的距离：

Wolfram Language code: HighlightGraph[WeightedAdjacencyGraph[d, EdgeLabels -> "EdgeWeight"], PathGraph[tour]]

应用  (3)

求访问平面上随机点的最短路径：

Wolfram Language code: p = RandomReal[10, {50, 2}];
Wolfram Language code: FindShortestTour[p]

显示路线：

Wolfram Language code: Graphics[{Line[p[[Last[%]]]], PointSize[Medium], Red, Point[p]}]

在三维空间上访问随机点的最短路径：

Wolfram Language code: p = RandomReal[20, {100, 3}];
Wolfram Language code: FindShortestTour[p];
Wolfram Language code: Graphics3D[{Line[p[[Last[%]]]], Sphere[p, 0.5]}]

求解欧洲旅行推销员的最短路径：

Wolfram Language code: europe = CountryData["Europe"]

地理中心的纬度和经度：

Wolfram Language code: pos = GeoPosition[CountryData[#, "CenterCoordinates"]]& /@ europe;
Wolfram Language code: FindShortestTour[europe];

显示路线：

Wolfram Language code: GeoGraphics[{Thick, Red, GeoPath[pos[[Last[%]]]]}]

将达芬奇的蒙娜丽莎以连续线段形式画出：

Wolfram Language code: monalisa = [image];

将图像转化成点图：

Wolfram Language code: monalisa = ColorQuantize[ColorConvert[monalisa, "Grayscale"], 2];
Wolfram Language code: pos = PixelValuePositions[ImageAdjust[monalisa], 0];

画出蒙娜丽莎：

Wolfram Language code: res = FindShortestTour[pos];
Wolfram Language code: Graphics[Line[pos[[res[[2]]]]]]

属性和关系  (2)

FindShortestTour 对于非哈密顿图给出空列表：

Wolfram Language code: g = GraphData[{"CayleyTree", {3, 4}}]
Wolfram Language code: HamiltonianGraphQ[g]
Wolfram Language code: FindShortestTour[g]

一个没有最短路线的图可能有一个通过所有顶点的最短路径：

Wolfram Language code: g = [image];
Wolfram Language code: FindShortestTour[g]
Wolfram Language code: FindHamiltonianPath[g]

可能存在的问题  (2)

对大数据集， FindShortestTour 找出至少其长度与最小值相近的路径：

Wolfram Language code: data = RandomInteger[100, {1000, 2}];
Wolfram Language code: FindShortestTour[data]//Short
Wolfram Language code: N[%[[1]]]

用 PerformanceGoal->"Quality" 找出最优结果：

Wolfram Language code: FindShortestTour[data, PerformanceGoal :> "Quality"]//Short
Wolfram Language code: N[%[[1]]]

在 FindShortestTour 中，将规则视为无向边：

Wolfram Language code: rules = {1 -> 2, 1 -> 4, 2 -> 3, 2 -> 5, 3 -> 6, 4 -> 5, 4 -> 7, 5 -> 6, 5 -> 8, 6 -> 9, 7 -> 8, 7 -> 10, 8 -> 9, 8 -> 11, 9 -> 12, 10 -> 11, 11 -> 12};
Wolfram Language code: FindShortestTour[rules]
Wolfram Language code: FindShortestTour[Graph[rules, DirectedEdges -> False]]

巧妙范例  (1)

设计一个游遍世界各国的旅行路线：

Wolfram Language code: places = CountryData["Countries"];
Wolfram Language code: centers = Map[GeoPosition[CountryData[#, "CenterCoordinates"]]&, places];
Wolfram Language code: {dist, route} = FindShortestTour[centers];

使用方位投影可视化该路线：

Wolfram Language code: GeoGraphics[GeoPath[centers[[route]]], GeoRange -> "World"]

在地球上可视化路线：

Wolfram Language code: r = 6371830;
Wolfram Language code: countryCenters = Map[First[GeoPositionXYZ[#]]&, centers[[route]]];
Wolfram Language code: arc[x_, y_] := Module[{a}, a = VectorAngle[x, y]; Table[Evaluate[RotationTransform[θ, {x, y}][x]], {θ, 0, a, a / Ceiling[10a]}]]
Wolfram Language code: tourLine = Apply[arc, Partition[countryCenters, 2, 1], {1}];
Wolfram Language code: countries = MapThread[Tooltip[Point[#1], #2[[2]]]&, {countryCenters, places[[route]]}];
Wolfram Language code: Graphics3D[{Sphere[{0, 0, 0}, 0.99 r], {Red, Thick, Line[tourLine]}, {Yellow, PointSize[Medium], countries}}, Boxed -> False, SphericalRegion -> True]
Wolfram Research (2007)，FindShortestTour，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindShortestTour.html （更新于 2024 年）.

文本

Wolfram Research (2007)，FindShortestTour，Wolfram 语言函数，https://reference.wolfram.com/language/ref/FindShortestTour.html （更新于 2024 年）.

CMS

Wolfram 语言. 2007. "FindShortestTour." Wolfram 语言与系统参考资料中心. Wolfram Research. 最新版本 2024. https://reference.wolfram.com/language/ref/FindShortestTour.html.

APA

Wolfram 语言. (2007). FindShortestTour. Wolfram 语言与系统参考资料中心. 追溯自 https://reference.wolfram.com/language/ref/FindShortestTour.html 年

BibTeX

@misc{reference.wolfram_2026_findshortesttour, author="Wolfram Research", title="{FindShortestTour}", year="2024", howpublished="\url{https://reference.wolfram.com/language/ref/FindShortestTour.html}", note=[Accessed: 03-November-2026]}

BibLaTeX

@online{reference.wolfram_2026_findshortesttour, organization={Wolfram Research}, title={FindShortestTour}, year={2024}, url={https://reference.wolfram.com/language/ref/FindShortestTour.html}, note=[Accessed: 03-November-2026]}