A class of greedy algorithms for solving the travelling salesman problem /
Mohammed Ali Almulla · eScholarship@McGill (McGill) · 1990
The travelling salesman problem is one of the NP-complete problems. It has been under consideration in computer science for at least forty years. Solving this hard problem using search methods can be accomplished by choosing: a starting point, a solution generation scheme and a termination rule. When the termination rule is such that search stops if and only if the tour is optimal, we call the method "exact". When the termination rule is such that the search stops but not necessarily with an optimal tour, we call the method "approximate". This thesis looks closely at one of the approximate methods, namely sub-optimal tour building. In particular, it focuses on the nearest neighbour algorithm (a greedy algorithm). By being greedy at every step of the procedure, this algorithm returns an approximate solution that is near optimal in terms of solution cost. Next, this greedy algorithm is used in implementing a new algorithm that is called the "Multi-Degree Greedy Algorithm". By being greedy at half of the procedure steps, this algorithm returns optimal solutions to travelling salesman problems 99% of the time. Thus, this algorithm is an approximate algorithm, designed to run on small-scale travelling salesman problems (n $<$ 20).