旅行商问题（TSP）

旅行商问题，常被称为旅行推销员问题（Travelling salesman problem, TSP），是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。

TSP 问题在物流中的描述是对应一个物流配送公司，欲将 n 个客户的订货沿最短路线全部送到。如何确定最短路线。TSP 问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是 n 个点的所有排列的集合，大小为（n-1）。

应用领域

• 1、如何规划最合理高效的道路交通，以减少拥堵；
• 2、如何更好地规划物流，以减少运营成本；
• 3、在互联网环境中如何更好地设置节点，以更好地让信息流动等。

哈密顿回路

哈密顿图(哈密尔顿图)(Hamiltonian graph，或 Traceable graph)是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路(Hamiltonian cycle)，含有图中所有顶点的路径称作哈密顿路径(Hamiltonian path)。

旅行商问题与哈密顿回路问题十分相似，都是经过每一个顶点一次最后回到出发的城市，不同的是旅行商问题对应的是完全图，即每个顶点之间都存在路径，并且路径长度已知。
哈密顿回路之中的图并不要求是完全图，而当这个图的完全图也就是每个顶点之间都存在路径，并且是加权图的时候，哈密顿