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