旅行推销员问题

在旅行推销员问题中, 推销员必须访问n个城市。可以说, 销售员希望进行巡回或汉密尔顿周期旅行, 只访问一次每个城市, 然后在其出发的城市结束。从城市i到城市j会有非负成本c（i, j）。目标是找到最低成本的行程。我们假设每两个城市相连。这种问题称为旅行推销员问题（TSP）。

我们可以将城市建模为n个顶点的完整图形, 其中每个顶点代表一个城市。

可以证明, TSP是NPC。

如果假设成本函数c满足三角不等式, 则可以使用以下近似算法。

三角不等式

令u, v, w为任意三个顶点, 我们有

开发近似解决方案的一个重要观察结果是, 如果我们从H *中删除一条边, 则巡回路线将成为生成树。

Approx-TSP (G= (V, E)) 
{
  1. Compute a MST T of G;
  2. Select any vertex r is the root of the tree;
  3. Let L be the list of vertices visited in a preorder tree walk of T;
  4. Return the Hamiltonian cycle H that visits the vertices in the order L;
}

推销员问题

凭直觉, Approx-TSP首先进行完整的MST T遍历, 该遍历每个边缘恰好两次。要从完整的步行创建汉密尔顿周期, 它绕过了一些顶点（相当于建立捷径）