哈密顿回路与旅行商问题

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

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

旅行商问题

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

![](/upload_images/20210823144551.png

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

0%