Improving the performance of Approximation algorithm to solve Travelling Salesman Problem using Parallel Algorithm
G. S. G. N. Anjaneyulu, Rajnish Dashora, A. Vijayabarathi, Bhupendra Singh Rathore · International Journal of Scientific Engineering and Technology · 2014
Travelling salesman problem is a NP complete problem and can be solved using approximation algorithm. It is a mi nimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph. An algorithm that returns near-optimal solutions is called approximation algorithms. Through analyzing the Metric TSP the performance of approximation algorithm can be improved significantly using graphical analysis of spanning trees and depth first search and implementing a parallel algorithm/program to find a path with approximately minimum travelling cost. Keywords—Travelling Salesman Problem, approximation algorithm, Parallel Algorithms. I. Introduction Travelling salesman problem pred icts the shortest possible route to connect different cities based on given distances between each city. Here each city should be traversed only once and finally the person tracing the route should reach to the starting point of the journey with the minimal cost of the whole journey. Solving a TSP requires application of many graph algorith ms which are helpfu l in analysing the TSP and hence the in find ing the optimal solution of TSP. We call the solution optimal because TSP is a NP hard problem it means TSP cannot be solved in polynomial t ime that is, it is at least hard as hardest problem in NP (6). TSP is a challenge to the field of algorithms, many researches are going on to find the solution for TSP and hence for the set of NP hard problems. But optimal solutions can be found using algorith ms such as 1) Exponential Time A lgorith m 2) Pseudo Polynomial Time A lgorith m