Evaluation of Complexity of Some Programming Languages on the Travelling Salesman Problem
D. R. Aremu, O. A. Gbadamosi (Mrs)

Abstract
The classical Travelling Salesman Problem and its approximate solution by means of the Nearest Neighbour Heuristic were presented in this study. The objective of the work was to find out the performance of some selected programming languages in solving the TSP. Being an NP- complete problem, it was considered that any means or techniques of reducing the time taken in solving the TSP was a welcome development; hence the need for using very efficient programming languages in developing software having many NP-complete modules cannot be over emphasised. In this study the Nearest Neighbour Heuristic was implemented using C++, C#, and Java. The complexities of the three programs using the Halstead complexities measures were computed. Also, the computer execution times of the three programs were captured. A 10-city TSP was used for illustration. Using the computer execution times, the study showed that both C++ and C# are faster than Java in solving the TSP. The complexities of the C++ programs are the highest, followed by those of C# and Java respectively. These results are in agreement with the fact that C++ is a middle- level language, whereas both C# and Java are higher-level languages. The programming implication of this is that a C++ programmer writes codes more from the scratch than a programmer using C# or Java. The study was concerned only with the classical TSP formulation.

Full Text: PDF