7.3 Traveling Salesman Problem - Branch and Bound

the topic is travelling salesperson problem using branch and bound in this video i'll explain you about the problem then the approach of branch and bound then i'll solve a textbook problem using branch and bound. See,the problem is a weighted graph is given here is an example of 5 vertices graph and we have to find out a shortest tour that is going through all the vertices once and returning back to the starting vertex so usually we have to take the starting vertex as one so we have to around all the vertices that is 2,3,4,5 and again we have to come back to vertex 1 for that cause adjacency matrix is given here now we understand how this problem is solved using branch and bound so for that i'll take a small graph with just 4 vertices and i'll discuss the approach then we will solve this one. See suppose there's a graph with just 4 vertices and suppose the salesman is starting from vertex 1 and he is going around all the vertices and returning back to vertex 1

Channel: Abdul Bari

Views: 753,398

Rating: 4.8630109 out of 5

Keywords: Traveling Salesman Problem, traveling salesperson problem, tsp, branch and bound, Traveling Salesman Problem - Branch and Bound, abdul bari, bari, gate

Id: 1FEP_sNb62k

Length: 24min 42sec (1482 seconds)

Published: Fri Apr 13 2018