旅行推销员问题旅行推销员问题|算法设计与分

在旅行推销员问题中, 推销员必须访问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; }

推销员问题