Data Structures Algorithms 简明教程
Travelling Salesman using Approximation Algorithm
我们已经使用 greedy 和 dynamic programming 方法讨论了旅行商问题，并且已经确立，以多项式时间解决旅行商问题以寻求完美的最佳解决方案是不可能的。
We have already discussed the travelling salesperson problem using the greedy and dynamic programming approaches, and it is established that solving the travelling salesperson problems for the perfect optimal solutions is not possible in polynomial time.
因此，近似解有望为这个 NP 难问题找到一个近似最优解。然而，仅当问题中的成本函数（定义为两个绘图点之间的距离）满足 triangle inequality 时，才会设计近似算法。
Therefore, the approximation solution is expected to find a near optimal solution for this NP-Hard problem. However, an approximate algorithm is devised only if the cost function (which is defined as the distance between two plotted points) in the problem satisfies triangle inequality.
只有当三角形的所有顶点 u、v 和 w 的成本函数 c 满足以下等式时，才会满足三角不等式
The triangle inequality is satisfied only if the cost function c, for all the vertices of a triangle u, v and w, satisfies the following equation
c(u, w)≤ c(u, v)+c(v, w)它在许多应用程序中通常会自动得到满足。
It is usually automatically satisfied in many applications.
Travelling Salesperson Approximation Algorithm
旅行商近似算法需要执行一些先决条件算法，以便我们能够获得近似最优解。让我们简单了解一下这些先决算法−
The travelling salesperson approximation algorithm requires some prerequisite algorithms to be performed so we can achieve a near optimal solution. Let us look at those prerequisite algorithms briefly −
Minimum Spanning Tree − 最小生成树是一个树数据结构，其中包含主图的所有顶点，连接它们的边数最少。在这种情况下，我们为最小生成树应用 Prim 算法。
Minimum Spanning Tree − The minimum spanning tree is a tree data structure that contains all the vertices of main graph with minimum number of edges connecting them. We apply prim’s algorithm for minimum spanning tree in this case.
Pre-order Traversal − 前序遍历是在树数据结构上完成的，其中一个指针按照 [根 - 左子节点 - 右子节点] 顺序遍历树的所有节点。
Pre-order Traversal − The pre-order traversal is done on tree data structures where a pointer is walked through all the nodes of the tree in a [root – left child – right child] order.
Algorithm
Step 1 − 随机选择给定图的任何顶点作为起始点和终点。
Step 1 − Choose any vertex of the given graph randomly as the starting and ending point.
Step 2 − 使用 Prim 算法构造一个图的最小生成树，其中选定的顶点作为根。
Step 2 − Construct a minimum spanning tree of the graph with the vertex chosen as the root using prim’s algorithm.
Step 3 − 一旦构造了生成树，便对前一步中获得的最小生成树执行前序遍历。
Step 3 − Once the spanning tree is constructed, pre-order traversal is performed on the minimum spanning tree obtained in the previous step.
Step 4 − 所获得的预序解是旅行商问题的一条哈密顿路径。
Step 4 − The pre-order solution obtained is the Hamiltonian path of the travelling salesperson.
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-近似算法。
The approximation algorithm of the travelling salesperson problem is a 2-approximation algorithm if the triangle inequality is satisfied.
为了证明这一点，我们需要展示该问题的近似成本是最佳成本的两倍。支持这一说法的几个观察结果如下−
To prove this, we need to show that the approximate cost of the problem is double the optimal cost. Few observations that support this claim would be as follows −
-
The cost of minimum spanning tree is never less than the cost of the optimal Hamiltonian path. That is, c(M) ≤ c(H*).
-
The cost of full walk is also twice as the cost of minimum spanning tree. A full walk is defined as the path traced while traversing the minimum spanning tree preorderly. Full walk traverses every edge present in the graph exactly twice. Thereore, c(W) = 2c(T)
-
Since the preorder walk path is less than the full walk path, the output of the algorithm is always lower than the cost of the full walk.
Example
让我们看一个示例图来形象化这个近似算法 −
Let us look at an example graph to visualize this approximation algorithm −
Solution
把上述图中的顶点 1 视为旅行商的起始点和终点，并从这里开始算法。
Consider vertex 1 from the above graph as the starting and ending point of the travelling salesperson and begin the algorithm from here.
Step 1
Step 1
从顶点 1 开始算法，从图中构建一个最小生成树。为了更多地了解构建最小生成树，请参阅 click here.
Starting the algorithm from vertex 1, construct a minimum spanning tree from the graph. To learn more about constructing a minimum spanning tree, please click here.
Step 2
Step 2
一旦构造出最小生成树，就把起始顶点视为根节点（即，顶点 1），并以先序遍历生成树。
Once, the minimum spanning tree is constructed, consider the starting vertex as the root node (i.e., vertex 1) and walk through the spanning tree preorderly.
为了便于理解，旋转生成树，我们得到 −
Rotating the spanning tree for easier interpretation, we get −
树的先序遍历发现是 − 1 → 2 → 5 → 6 → 3 → 4
The preorder traversal of the tree is found to be − 1 → 2 → 5 → 6 → 3 → 4
Step 3
Step 3
在所跟踪的路径的末尾加上根节点，我们得到， 1 → 2 → 5 → 6 → 3 → 4 → 1
Adding the root node at the end of the traced path, we get, 1 → 2 → 5 → 6 → 3 → 4 → 1
这是旅行商近似问题的输出哈密顿路径。该路径的成本将是最小生成树的所有成本之和，即， 55 。
This is the output Hamiltonian path of the travelling salesman approximation problem. The cost of the path would be the sum of all the costs in the minimum spanning tree, i.e., 55.