旅行商问题及其拓展

旅行商问题(英文:Travelling salesman problem, TSP)是图论、组合数学中一个非常经典的问题。

旅行商问题具体内容:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。其与哈密顿有着密切的联系,TSP可以约化为哈密顿回路。

TSP属于NPC问题,故无多项式时间算法,常用求解算法有回溯法、分支限界法、等,以上均为O(n!)的时间复杂度。

TSP对路线规划有着重要应用,而路线往往为非哈密顿图。可以适当地对TSP进行拓展:(正是SYSU2020年新手赛A题。)

给定一系列城市和每对城市之间的距离,求解访问每一座城市并回到起始城市的最短回路。(该形式貌似又被称为Euclidean TSP)

该问题可以约化为TSP。

解法:

获得每个城市到其他城市的最短路径,若该城市与某城市不可直接到达,那么这两站之间增加一条边,边的权为以上所求最短路径的长度。而这个图一定是哈密顿圈。该问题现在约化为了TSP。


旅行商问题及其拓展
https://lijianxiong.work/2020/20201207/
作者
LJX
发布于
2020年12月7日
许可协议