Travelling Salesman Problem Using Least Cost Branch and Bound Method | 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