论文标题

Demidenko矩阵上的旅行推销员路径

Travelling salesman paths on Demidenko matrices

论文作者

Cela, Eranda, Deineko, Vladimir G., Woeginger, Gerhard J.

论文摘要

在旅行推销员问题(PATH-TSP)的路径版本中,推销员正在寻找在一组n个城市中最短的哈密顿路径。推销员必须在给定的城市开始他的旅程,准确地访问每个城市,最后结束他在另一个给定的城市的旅行。在本文中,我们确定了一个新的多项式解决方法的路径-TSP,其中城市的距离矩阵是所谓的Demidenko矩阵。我们确定了最佳解决方案的许多关键组合属性,并设计了一个具有时间复杂性$ o(n^6)$的动态程序。

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s, visit every city exactly once, and finally end his trip at another given city t. In this paper we identify a new polynomially solvable case of the Path-TSP where the distance matrix of the cities is a so-called Demidenko matrix. We identify a number of crucial combinatorial properties of the optimal solution, and we design a dynamic program with time complexity $O(n^6)$.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源