一、旅行商问题 TSP

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

• 带权图，完全图
• NP 难问题(即还没有多项式级别的算法，只有指数级别的算法来解决这类问题)

在物流中的描述是对应一个物流配送公司，欲将 n 个客户的订货沿最短路线全部送到。

二、哈密顿回路

1、哈密顿回路问题的起源

1859 年，爱尔兰数学家哈密顿（Hamilton）提出周游世界的游戏：在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科等世界著名大城市，正十二面体的棱表示连接这些城市的路路线。试问能否在图中做一次旅行，从顶点到顶点，沿着边行走，经过每个城市 恰好一次 之后再 回到出发点。

哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在哈密顿图中，含有图中所有顶点的路径称作 哈密顿路径(Hamilton path)，闭合的哈密顿路径称作 哈密顿回路(Hamilton cycle)。

旅行商问题对应的是完全图，任意每两个顶点之间都存在路径，并且路径长度已知。
哈密顿回路并不要求图是完全图，当图是加权

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！