Traveling Salesman Problem | Dynamic Programming | Graph Theory

Key Takeaways

hello and welcome to this tutorial on how to solve the Traveling Salesman problem with dynamic programming today we're going to look at two things first is how to find the cost of the best tour and then how to actually find that tour all right so let's get started what is the Traveling Salesman problem in a nutshell it's when you're given a list of cities and the distances between each pair of cities and you want to find the shortest possible route that visits each city exactly once and then it returns to the city of origin in some other words we can say that the problem is given a complete graph with weighted edges what is the Hamiltonian cycle of minimum cost a Hamiltonian cycle is simply a path which visits each node exactly once in practice you will probably want to represent whatever graph you have as an adjacency matrix for simplicity if an edge between two nodes does not exist simply set the edges value to be positive infinity so in the graph I had you can see that one optimal tour consists of going from A to D to C to B and then finally back to a with a minimum cost of nine note that it is entirely possible that there are many possible valid optimal tours but they will all have the same minimum cost as it turns out solving the Traveling Salesman problem is extremely difficult in fact the problem has been proven to be np-complete meaning it's very difficult to find an optimal solution for large inputs however numerous approximation algorithms exist if you want to get an algorithm that runs very quickly even for large inputs so the brute-force way to solve this problem is to actually compute all possible tours and this means we have to try all permutation of node orderings which will take Big O of n factorial time which is very slow but as you can see I've listed all the permutation of nodes and highlighted the ones which yield the optimal solution the dynamic programming solution we're going to develop today is able to improve on this naive approach by reducing the complexity to Big O of N squared x to the N at first glance this may not seem like a substantial improvement however it now makes graphs with roughly twenty three nodes give or take feasible for modern home computers here's a table of n factorial versus N squared to the N at first you notice that n factorial is optimal for small numbers but this quickly changes favor to N squared to the N which can give a significant improvement over n factorial you can always see that how large the numbers get friend factorial when we hit N equals 15 versus the N squared to the N all right time to talk about how to solve this problem using dynamic programming the main idea is going to be to compute the optimal solution for paths of length and we will have to reuse information from paths of length and minus 1 but before we get started there's some set up information we need to talk about the first thing we're going to need to do is pick a starting node s it doesn't matter which notice picked just make sure that this nodes index is between 0 and n non-inclusive suppose we have this graph with 4 nodes and we choose our starting node to be nodes 0 the next thing we need to do is store the optimal value from s the starting node to every other node this will solve the Traveling Salesman problem for all paths with exactly two notes the optimal value for paths with two nodes is given in the input through the adjacency matrix and this is all the setup we need to do visually if you want to look at it we can see that we would weed store the value from 0 to 1 0 to 2 and finally 0 to 3 in the last slide I talked about storing the solution for N equals 2 but what is it we really need to store there are two key things the first is obvious and that's the set of visited nodes and the partially completed tour the other is the index of the last visited node in the path for each partially completed tour we need to save which node was the last node we were on so that we can continue extending that partially completed tour from that node we were on and not from some other node this is very important so together these two things the set of visited notes and index of the last visit node form what I call the dynamic programming state since there are n possible last nodes and to the power of n node subsets our storage space is bounded by Big O of n times to the end an issue we're going to face when trying to store the DP state is representing the set of visited nodes and the way and I mean the way to do this is to use a single 32-bit integer the main idea is that if the eighth node has been visited we on the 8th bit 2 a1 in the binary representation of the integer the advantage to this representation is that a 32-bit integer is compact quick and allows for easy cashing in a memo table for example on the leftmost graph we have visited the 0th and first nodes so the binary representation is 0 0 1 1 if the least significant bit is on the right similarly the binary representation of the middle graph is 1 0 0 1 or just the number 9 in decimal since nodes 0 & 3 have been visited now suppose we're trying to expand on our previous state one particular instance of a two node partial tour shown below what we want to do from our last node which in this graph is no.3 is expand to visit all other unvisited nodes these are the gray nodes 1 & 2 to make our partial tour a little longer with 3 nodes for this particular state we were able to generate an additional 2 States but we would also need to do this for all states with two nodes not just this one with 0 & 3 in total this process would result in 6 new states for partial tours with 3 nodes this process continues with gradually longer and longer paths until all paths are of length n the last thing we need to do to wrap up the travelling salesman problem is to reconnect the tour to the designated starting node s to do this loop over the end state in the memo table for all possible end positions excluding the start node and minimize the lookup value plus the call of going back to s note that the end state is the one where the binary representation is composed of all ones meaning each note has been visited it's finally time to look at some pseudocode for the Traveling Salesman problem just a heads-up to everyone who's still a beginner the following slides make use of advanced bit manipulation techniques so make sure you're comfortable with how binary shifts and ORS and Xers work here's the function that solves the Traveling Salesman problem it takes two inputs the first is an A two-dimensional adjacency matrix representing the input graph and s the index of the starting node the first thing we do is get the size of the matrix and story in a variable called n which tells us how many nodes there are then we initialize the two-dimensional memo table the table should have size and by to the power of n I recommend filling the table with null values so that programmatic errors throw runtime exceptions then we're going to call for functions setup solve find min cost and find optimal tour let's begin by looking at what happens inside the setup method the setup method is very easy it simply does what I Ellis trated a few slides ago by storing the optimal value from the start node to every other node you loop through each node skipping over the start node and then you cache the optimal value from s to I which can be found in the distance matrix the DP state you store is the end node as I and the mask with bits s and I set to 1 hence the double bit shift visually the node is the start node and the orange node is node I which changes with every iteration you notice now that the orange node is never on top of the green node which is why I had a continued statement to skip that case now let's look at how the solve method works the solid method is by far the most complicated but I've broken it down to be easy to understand the first line in the method loops over R equals 3 up to an inclusive think of R as the number of nodes in a partial tour so we're increasing this number one at a time the next line says for subset in combinations the combinations function generates all bit sets of size and width exactly our bits set to 1 for example as seen in the comments when calling the combinations function with R equals 3 and N equals 4 we get four different bit sets each distinct and with three ones turned on these are meant to represent a subset of visit nodes moving on notice that I enforce the node s to be part of the generated subset otherwise the subset of nodes is not valid since it could not have started at our designated starting node notice that this if statement calls the not in function defined at the bottom of this slide all it does is it checks if the 8th bit in the subset is a zero then we loop over a variable called next which represents the index of the next node the next node must be part of the current subset this may sound strange but know that the subset variable generated by the combinations function has a bit which is meant for the next node this is why the variable state on the next line represents the subset excluding the next node this is so we can look up in our memo table to figure out what the best partial tour value is when the next node was not yet in a subset being able to look back and reuse parts of other partially completed tours is essential to the dynamic programming aspect of this algorithm the following variable to consider is e short for end node because I ran out of room this variable is quite important because while the next node is temporarily fixed in the scope of the inner loop we try all possible end nodes of the current subset and try to see which end node best optimizes this partial tour of course the end node cannot be any of the start node the next node or not be part of the current subset that we're considering so we skip all those possibilities so we compute the new distance and compare it to the minimum distance if the new distance is better than the minimum distance then we update the best minimum distance afterwards once we've considered all possible end nodes to connect to the next node we store the best partial tour in the memo table and this concludes the solve method the only unanswered question in this slide is how the combinations method works now I do not mean to leave this unanswered so let's see how this gets done this method is actually far simpler than you might imagine for what it does what the first combinations method does is it fills the subsets array using the second combinations method and then it returns that result so what does the psyche in the combinations method do I already covered this in more detail in my tutorial backtracking the power set if you want more detail but I'll give you a quick rundown of what this recursive method does basically starting with the empty set which is zero you want to set are out of n bits to be one for all possible combinations so you keep track of which index position you're currently at and then try and set the bit position to a one and then keep moving forward hoping that at the end you have exactly R bits but if you didn't you backtrack flip off the bit you flipped on and then move to the next position this is a classic backtracking problem you might want to research this is how you solve it but I don't want to focus on this in this video per se so I want to get back the Traveling Salesman problem watch my back tracking video on the powerset for more guidance if you're lost I'll try and remember to put a link in the description so right now in our memo table we have the optimal value for each partial tour with n nodes so let's see how we can reuse that information to find the minimum tour of value the trick is going to be to construct a bit mask for the end state and use that to do a lookup in our memo table the end state is the bit mask with n bits set to 1 which we can obtain by doing a bit shift and then subtracting 1 then what we do is look at each end node candidate and minimize over the torque cost by looking at what's in our memo table and the distance from the end node back to the start node s the last method we need to look at is the find optimal tour function because what good is our algorithm if it cannot actually find you what the optimal tour is for this method what we're going to do to find the actual tour is work backwards from the end state and do lookups in our memo table to find the next optimal note we will keep track the last index we were at and the current state which begins with all visited notes then we loop over I from n minus 1 to 1 which tracks the index position for the tour to actually find the next optimal node going backwards we're going to use a variable called index which will track the best node the inner loop loops over J which represents all possible candidates for the next node we must ensure that J is not the starting node and that it is part of the state meaning it has not yet been visited if this is the first valid iteration the variable index will be set to minus 1 so set it to J otherwise compare the optimal values of the best distances between nodes index and J and update index if node J is better once the optimal index is found store that as part of the tour and flip off the bit in the state which represents the index node finally set the first and last nodes of the tour to be s the starting node because the tour needs to start and end on that note then simply return the tour and that is how you solve the Traveling Salesman problem with dynamic programming of course I might have accidentally fudged a detail or two unintentionally in the pseudocode but there's no getting around that in the true source code so catch me in the next video for a complete code implementation of the Traveling Soul improv if you're eager to see an implementation check out my github repo github.com slash William Visa slash algorithms under the graph theory or dynamic programming section thank you for watching I hope you enjoyed this video and learn something give it a thumbs up and subscribe for more mathematics and computer science videos thank you