Coders Packet

Approximation Algorithm for Traveling Salesman Problem, using nearest neighbor in Java

By Naman Panpaliya

A Java program of Approximation Algorithm for Traveling Salesman Problem, using the nearest neighbor.

In this blog, you will learn about approximation algorithms and how to implement a java program of an approximation algorithm for traveling salesman problems using the nearest neighbor mechanism.

 

Approximation Algorithm:

This algorithm is used for an optimization problem. This type of algorithm gives us the best value which is close to an optimum value. The time taken by this algorithm is very less. This type of algorithm is also known as heuristic algorithms.

In travelling salesman problems, Approximation algorithms are used to find the shortest cycle and optimization problems are used to find the shortest path.

In vertex cover problems, approximation algorithms are used to find the vertex cover with few vertices and in optimization problems, vertex cover is found with the fewest vertices. 

 

Travelling salesman problem:

In these types of problems, a salesman or a salesperson have to visit n cities. For example, we can say that the salesman makes a tour i.e if he started from city A then he went to city B then from City B to city C then from city C to city D and al last he same back from city D to original city A from where he started so this cycle is known as Hamiltonian cycle i.e A-B-C-D-A. So in this, a salesman wants to visit from city A to city D and he has three ways for it so this problem helps us know the shortest path to travel from city A to city D. The goal of this problem is to find a tour of minimum cost. In this, we assume that each and every two cities are connected so this type of problems are called as travelling salesman problems. 

We can model the cities as a complete graph of n vertices, where each vertex represents a city.

 

Here is the Output for the Approximation Algorithm for Traveling Salesman Problem, using nearest neighbor in Java

Ouput

Download project

Reviews Report

Submitted by Naman Panpaliya (Naman9999)

Download packets of source code on Coders Packet