论文标题
Demidenko矩阵上的旅行推销员路径
Travelling salesman paths on Demidenko matrices
论文作者
论文摘要
在旅行推销员问题（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)$.
