Data Structures Algorithms 简明教程

Travelling Salesman using Approximation Algorithm

我们已经使用 greedy 和 dynamic programming 方法讨论了旅行商问题，并且已经确立，以多项式时间解决旅行商问题以寻求完美的最佳解决方案是不可能的。

因此，近似解有望为这个 NP 难问题找到一个近似最优解。然而，仅当问题中的成本函数（定义为两个绘图点之间的距离）满足 triangle inequality 时，才会设计近似算法。

只有当三角形的所有顶点 u、v 和 w 的成本函数 c 满足以下等式时，才会满足三角不等式

                 c(u, w)≤ c(u, v)+c(v, w)

它在许多应用程序中通常会自动得到满足。

Travelling Salesperson Approximation Algorithm

旅行商近似算法需要执行一些先决条件算法，以便我们能够获得近似最优解。让我们简单了解一下这些先决算法−

Minimum Spanning Tree − 最小生成树是一个树数据结构，其中包含主图的所有顶点，连接它们的边数最少。在这种情况下，我们为最小生成树应用 Prim 算法。

Pre-order Traversal − 前序遍历是在树数据结构上完成的，其中一个指针按照 [根 - 左子节点 - 右子节点] 顺序遍历树的所有节点。

Algorithm

Step 1 − 随机选择给定图的任何顶点作为起始点和终点。

Step 2 − 使用 Prim 算法构造一个图的最小生成树，其中选定的顶点作为根。

Step 3 − 一旦构造了生成树，便对前一步中获得的最小生成树执行前序遍历。

Step 4 − 所获得的预序解是旅行商问题的一条哈密顿路径。

Pseudocode

APPROX_TSP(G, c)
   r <- root node of the minimum spanning tree
   T <- MST_Prim(G, c, r)
   visited = {ф}
   for i in range V:
      H <- Preorder_Traversal(G)
      visited = {H}

Analysis

如果满足三角不等式，那么旅行商问题的近似算法就是 2-近似算法。

为了证明这一点，我们需要展示该问题的近似成本是最佳成本的两倍。支持这一说法的几个观察结果如下−

最小生成树的成本绝不会低于最佳哈密顿路径的成本。即， c(M) ≤ c(H *）。
全走查的成本也刚好是最小生成树的成本的两倍。全走查定义为遍历最小生成树的先序时所追溯的路径。全走查准确地遍历图中现有的每条边两次。因此， c(W) = 2c(T)
由于先序走查路径小于全走查路径，因此算法的输出始终低于全走查的成本。