A TSP algorithm based on link degree. (November 2020)

• Record Type: Journal Article
• Authors: Yu, Guyang; Shi, Huajun
• Is Part Of: Journal of physics. Volume 1682(2020)
• Publication Date: 2020-11
• Subjects: Physics -- Congresses; 530.5
• DOI: 10.1088/1742-6596/1682/1/012040
• Languages: English
• ISSNs: 1742-6588

Abstract

Abstract: The fundamentality of the traveling salesman problem (TSP) is the choice of an edge in the next step. This paper proposes a concept of link degree, which can display the potentiality of an edge to belong to the shortest Hamiltonian cycle in a more effectively manner and, on this basis, it presents a greedy algorithm for the TSP. Meanwhile, some relevant theorems and conjectures as well as some problems triggered are discussed as well.