论文研究 对称旅行商问题的精确排序线性分配解决方案

在本文中,我们展示了如何将Murty的排名线性分配算法应用于精确解决对称旅行商问题(TSP)。 为了提高Murty算法解决TSP的计算效率,我们开发了一种简单的算法来确定Murty的顺序节点分区过程中生成的节点是否包含长度小于n的子循环,其中n是要被访问。 每个此类节点均无法生成真正的解决方案,该解决方案必须是完整的n周期,因此可以从进一步的分区中消除。 确切地说,解决TSP Murty的排名过程一直在进行,丢弃所有此类节点,当遇到第一个这样的排名为完整n周期的解决方案时,终止有限数量的排名。 第一个排名第n个周期是给定TSP问题的精确解决方案。