An Analysis of a Recursive and an Iterative Algorithm for Generating Permutations Modified for Travelling Salesman Problem

Abstract

This paper presents the results of a comparative analysis between a recursive and an iterative algorithm when generating permutation. A number of studies discussing the problem and some methods dealing with its solution are analyzed. Recursion and iteration are approaches used in computer programs to implement different algorithms. An iterative approach is the repeated execution of the same source code until a certain end condition is met. On the other hand, a recursive approach uses a recursive function that repeatedly calls itself. This function contains a source code that must be executed repeatedly. Both algorithms presented in this paper can be used to generate permutations of an n element set. The algorithms are modified so that they can be used to solve the Travelling Salesman Problem (TSP) with a small number of vertices. Several publications that discuss the TSP and some approaches to its solution are also presented. The methodology and the conditions for conducting the experiments are described in details. The obtained results have been analyzed; they show that for the same conditions the iterative algorithm works from of 8 to 16 times faster than the recursive algorithm in all the tested input data. Several approaches to optimize the two algorithms in terms of the number of permutations tested when searching a minimal Hamiltonian cycle are presented.