Traveling Sales Person - 函数族

一般信息

问题定义

旅行推销员问题 (TSP) 提出以下问题：

给定一个城市列表以及每对城市之间的距离，哪条是访问每个城市一次并返回出发城市的最短路线？

起源

旅行推销员问题由数学家 William Rowam Hamilton 爵士 和 Thomas Penyngton Kirkman 于 18 世纪研究。

关于汉密尔顿和柯克曼工作的讨论可参见《图论》（比格斯等人，1976 年）一书。

  • ISBN-13: 978-0198539162

  • ISBN-10: 0198539169

人们认为旅行推销员问题（TSP）的一般形式最早由维也纳和哈佛的卡尔·门格尔（Karl Menger）研究。后来，普林斯顿的哈斯勒、惠特尼和梅里尔（Hassler, Whitney & Merrill）进一步推动了这个问题。关于门格尔和惠特尼之间的联系以及TSP的发展，可以在`组合优化的历史(直到1960年) <https://homepages.cwi.nl/~lex/files/histco.ps>`__

计算经过 : math:n 城市的不同旅行次数：

  • 给定一个起始城市，

  • 第二个城市还有 \(n-1\) 个选择，

  • 第三个城市的 \(n-2\) 选项等。

  • 相乘得到 \((n-1)！= (n-1) (n-2) ..1\).

  • 现在，由于旅行成本不取决于旅行的方向：

    • 这个数字乘2

    • \((n-1)!/2\)。

特征

  • 该问题是一个NP-hard优化问题。

  • 使用度量算法

  • 在最坏的情况下，实施产生的解决方案的时间是最佳旅行的两倍：

    • 图是无向的

    • 图是全连通的

    • 图中，边上的旅行成本服从三角不等式。

  • 在无向图上：

    • 旅行费用是对称的：

    • 从 u 到 v 的旅行费用与从 v 到 u 的旅行费用相同

TSP 可选参数

列

类型

默认

描述

start_id

ANY-INTEGER

0

第一个访问顶点

  • 当 0 时，任何顶点都可以成为第一个访问顶点。

end_id

ANY-INTEGER

0

返回 start_vid 之前最后访问的顶点。

  • 当为 0 时，任何顶点都可以成为返回 start_id 之前最后访问的顶点。

  • 当 NOT 0 且 start_id = 0 时，它是第一个和最后一个顶点

另请参阅

参考

索引和表格