旅行商问题及其拓展

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

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

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

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

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

该问题可以约化为TSP。

解法：

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