JAVA SEMINAR ON TRAVELLING
SALESMAN PROBLEM AND
SPARSE ARRAY
MADE BY : KESHAV MALIK
TRAVELLING SALESMAN PROBLEM
• The Travelling Salesman Problem (TSP) is the most known computer
science optimization problem in a modern world . In sample words , it
is a problem of finding optimal route between nodes in the graph .
The total travel distance between can be one of the optimization
criterion.
• In order to solve the TSP problem, we'll need two model classes,
namely City and Travel. In the first one, we'll store the coordinates of
the nodes in the graph
• Given A Set of Cities and distance between every pair of cities, the
problem is to find the shortest possible route that visit every city
exactly once and return to the starting point
• The Hamilton cycle problem is to find if there exist a tour that visit
every cycle at least once . The problem is a famous np hard problem
there is no polynomial time solution for this problem .
• Following are the different solution for the travelling salesman
problem :
Naïve solution
Dynamic programming
NAIVE SOLUTION
• Consider city 1 as the starting and ending point
• Generate all n-1 permutation of cities
• Calculate cost of every permutation and keep
Track of minimum cost permutation
• Return the permutation with minimum cost
PERMUTATION CORRESPOND COST PERMUTATION CORRESPOND
COST
1-2-3-4-1 95 1-3-4-2-1 80
1-2-4-3-1 80 1-4-3-2-1 95
1-3-2-4-1 95 1-4-2-3-1 95
DYNAMIC PROGRAMMING
• Let the given set of vertices be {1,2,3,4…n} let us consider 1 as the
starting point and ending point of output . For every other vertex I
(other than 1) , we find the minimum cost path with 1 as the starting
point , I as the ending point and all vertices appearing exactly once .
• S = Subset of the graph not yet traversed
• Dist(I,1) = distance from i to 1
if size of s is 2 then s be {1,i}
C{s,i} = dist{1,i}
Else if size of s is greater than 2
C{s,i} = min{c s-[i],j} + dis(j,i) where j belongs to s j1=I and i1=1
• For a set of size n , we consider n-2 subsets of Each n-1 such that all
alphabets don’t have nth in item .
• There are atmost (o n*2n) subproblems and each one take linear time
to solve . The total running time is therefore 0(n*n2n) subproblems ,
and each one take linear time to solve . The time complexity is much
less than naive solution , but still exponential . Space requires is also
exponential . So this approach is also infeasible only for slightly
higher number of vertices .
SPARSE ARRAY
• A sparse array is a data structure which maps keys to value . Same
idea as a map , but different implementation . Both the keys and
value are object instances. A sparse array is made up of two arrays :
1. an array of primitive keys .
2. an array of object values .
• The main interest of the SparseArray is that it saves memory by using
primitives instead of objects as the key. For instance the screenshot
below (courtesy of visual VM), shows the memory used when storing
1,000,000 elements in an sparse array of <int, String>
Public Constructor in Sparse Array
• Sparse array()
: creates a new sparse array containing no mapping.
• Sparse array( int initial capacity)
:creates a new sparse array containing no mapping that will
require any additional to store the specified number of mappings .
• PUBLIC METHOD:
APPEND : put a key or value pair into array , optimizing for the
case where the key is greater than all existing keys in array .
ex: public void append (int key E value)
THANKYOU