哈密顿回路与旅行商问题

哈密顿路径、哈密顿回路、哈密顿图

G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。
若G中一个回路通过且仅通过每一个顶点一次，称这个环为哈密顿回路。
若一个图存在哈密顿回路，就称为哈密顿图。

旅行商问题

旅行商问题又称为旅行推销员问题（Travelling salesman problem, TSP），它是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

![](/upload_images/20210823144551.png

由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。
早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。