Travelling Salesman Problem using Least Cost Branch and Bound || Design and Analysis of Algorithms

#sudhakaratchala #daavideos #daaplaylist
Let G=(V,E) be a directed graph defining an instance of TSP.
where V is set of vertices and E is set of edges
The edges are given along with their cost Cij where Cij 0 for all i,j
cost(i,j) Cij if (i,j) ϵ E(G)
ꝏ if (i,j) ϵ E(G)
Let |V|=n
The solution space S is given by S={1,∏,1/∏ is permutation of (2,3,…..n)} then |S|=(n-1)!
The size of S can be reduced by restricting S so that (1, i1, i2, i3,….. in-1,1) ϵ S