Travelling SalesMan Problem(TSP)

TSP is np- hard problem which has number of solution but it's difficult to find optimal solution . I gave here fast,easy and efficient solution on TSP using one algorithm with good explanation.Hope you understood very well.

1. Travelling Salesman Problem
Travelling Salesman Problem

2. Travelling Salesman Problem
Problem
Given a list of cities and the distances between each pair of cities,
what is the shortest possible route that visits each city exactly
once and returns to the origin city.
Travelling Salesman Problem

3. Travelling Salesman Problem
Example
Akshay has following list of cities and want to visit each city once,
return back to home:
Pune(Home)(A)
Bangalore(B)
Chennai(C)
Delhi(D)
Kolkata(E)
ShriNagae(F)
Travelling Salesman Problem

4. Travelling Salesman Problem
Matrix
A B C D E F
A 0 36 32 54 20 40
B 36 0 22 58 54 67
c 32 22 0 36 42 71
D 54 58 36 0 50 92
E 20 54 42 50 0 45
F 40 67 71 92 45 0
Let say that , These are the distances from the cities and akshay
want to go from Home-city(Pune) to ShriNagar with minimum
cost. In which order/path he do these?
Travelling Salesman Problem

5. Travelling Salesman Problem
We Solve the problem using Nearest neighbor algorithm:
Algorithm:
1
Select a city as current city.
2
Find out the shortest edge connecting the current city and an
unvisited city.
3
Set the new city as current city.
4
Mark the previous current city as visited.
5
If all the cities are visited, then terminate.
6
Go to step 2.
Travelling Salesman Problem

6. Travelling Salesman Problem
Explanation : We visit Cities As follows Using Above algorithm,
A!E= 20
E!C= 42
C!B= 22
B!D= 58
D!F= 92
F!A= 40
Total Cost = 20 + 42 + 22 + 58 + 92 + 40 = 274
Travelling Salesman Problem

7. Travelling Salesman Problem
Pseudo Code :
HomeCity = Visited = Currentcity
While(!visitedAllCity)
Node = FindShortestdistance(Currentnode)
AddNode (Node)
Currentnode = Node
Result = All node + HomeCity[0][lastVisitNode]
return Finalresult= Result
Travelling Salesman Problem

8. Travelling Salesman Problem
Summary
1
Complexity of this algorithm is o(n
2
)
which is much better than brute force algorithm.
2
It is Fast, Easy and Ecient.
Travelling Salesman Problem

9. Travelling Salesman Problem
Reference
We can solve TSP problem using genetic algorithm.
1
Research Paper on Travelling Salesman Problem And its
Solution Using Genetic Algorithm.
http://www.ijirt.org/vol1/paperpublished/IJIRT101672PAPER:pdf
2
https://thesai.org/Downloads/Volume3No7/Paper15-
ImprovingtheSolutionofTravelingSalesmanProblem
UsingGenetic,MemeticAlgorithmandEdgeassemblyCrossover.pdf
Travelling Salesman Problem