Algorithmic Approaches to the Traveling Salesman Problem for the Development of Students’ Computational Thinking

The traveling salesman problem (TSP) is an algorithmic problem concentrated on finding the shortest path between a set of locations that must be visited. Dynamic programming is a powerful technique to solve this problem. Given several cities and the distance between every pair of them, the problem is set with aim to find the shortest possible path that visits each city exactly one time and returns back to the starting post. The travelling salesman problem (TSP) appears in many cases and can be applied in computer operations, circuit testing, computer wiring, stochastic vehicle routing and in other real everyday cases that demand solution. In this paper we make a synopsis of the outcomes presented in the scientific literature and try to contribute new findings to literature by proposing a basic algorithm to solve the TSP, and next an improved solution of the TSP by coding the A* algorithm in PASCAL programming language.