Open AccessA TSP algorithm based on link degree
Author(s) -
Guyang Yu,
Huajun Shi
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1682/1/012040
Subject(s) - travelling salesman problem , hamiltonian path , link (geometry) , greedy algorithm , degree (music) , enhanced data rates for gsm evolution , computer science , algorithm , basis (linear algebra) , mathematical optimization , mathematics , theoretical computer science , combinatorics , graph , artificial intelligence , physics , geometry , acoustics
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.