Travelling Salesman Problem

假设一个销售员想要访问分配给他的若干个城市。他知道每两个城市之间的行程距离。他的问题是选择一条从他的家乡城市出发，恰好经过每个城市一次，然后返回他的家乡城市的最短可能距离的路线。这个问题与寻找最小长度的哈密顿回路密切相关。如果我们用顶点表示城市，用连接两个城市的道路表示边，我们就得到一个加权图，其中每条边 e_i 都关联一个数字 w_i（权重）。

以上抽象的物理解释是：将图 G 视为 n 个城市的地图，其中 w(i, j) 是城市 i 和城市 j 之间的距离。一个销售员想要对这些城市进行一次巡回，从同一个城市开始和结束，包括每个剩余的 a 个城市一次且仅一次。

在图中，如果我们有 n 个顶点（城市），那么就有 (n-1)! 条边（路线），并且 n 个顶点的完整图中的哈密顿回路总数为 .

最近邻算法

此过程为旅行商问题提供了相当不错的结果。该方法如下

步骤1： 选择一个任意顶点，并找到距离该起始顶点最近的顶点，以形成一条边的初始路径。

步骤2： 让 v 表示添加到路径的最新顶点。现在，在路径中不存在的顶点中，选择距离 v 最近的顶点，并将该路径、连接 v 和该顶点的边添加到路径中。重复此步骤，直到图 G 的所有顶点都包含在该路径中。

步骤3： 连接起始顶点和通过边添加的最后一个顶点，形成回路。

示例： 使用最近邻算法来解决以下旅行商问题，图示见下图，从顶点 v₁ 开始。

解决方案： 我们必须从顶点 v₁ 开始。通过使用最近邻算法，旅行或哈密顿回路的顶点逐个构建如图所示

这条路线的总距离为 18。