Hello and welcome to this video on the Traveling Salesman Problem with dynamic programming. Today we're going to have a look at some source code. This is the second video on the Traveling Salesman Problem. The first video explains how to solve this problem with dynamic programming. And in this video, we're looking at unique the source code. So make sure you watch the previous video before diving into this one.

The source code I'm going to present today can be found@github.com slash William slash algorithms. Under the graph theory or dynamic programming section, there will be a link in the description. All right here we are in the source code for the Traveling Salesman Problem with dynamic programming. This is the intuitive implementation. If you look in the repository, you should see that there is also a recursive implementation if you are interested in that. This implementation is in the Java programming language, but you should be able to translate it pretty easily to any programming language.

So let's get started. So if we want to solve this problem, we're going to have to create this object called tsp dynamic programming iterative and it has two constructors, one with a distance matrix as an input. And the other optional constructor is the distance matrix, but also with a designated starting node. So by default, I have the starting node to be zero, but you can set that to be whichever node you like. And then I simply store how many nodes are in the graph, and then check for some edge cases. I haven't supported n equals two yet, but that should be pretty good.

Trivial to do. And then just check some edge cases, make sure the matrix is square, you know, just that kind of stuff. And then I cashed the start position and the distance in these instance variables. And then here are the two methods that you will be interested in the first called get tour, and it returns a list of integers representing the optimal tour for the input graph. And this other method called get tour costs, returns the minimum torque cost. And notice that they both call the solid method if the solver has not been run yet.

I could call the solve method in the constructor but that's generally considered bad practice to do work in the constructor. So I leave it up to the methods to call the self method Or you can explicitly call it yourself doesn't matter. So the solve method is what basically solves the traveling salesman person problem. So the first thing I do is I initialize a variable called the end state. And this is the state with all nodes visited. So all bits are set to one.

Then I initialize a memo table of size and times to the end, and it takes type double. So initially, this entire table is filled with null values. And then I do an initialization step, where I add all edges from the starting node to every other node, which is not the starting node. So this is like the first step in the slides, if you remember correctly, and then you set it equal to the value in the adjacency matrix. Then we start the phase where we're trying to create tours of path that are one longer. So our is once again, the number of nodes in the partially completed tour.

Then we loop through all subsets with our bits set produced from our combinations function, which is below. I guess I'll jump to that right now. So that's right here. And this method basically generates all the bits sets of size and where our bits are set to one. And then you can see that the result is returned in this variable called subsets. So this is the combinations method and then this calls the private combinations method down here.

So it ignoring this part, which is just an optimization, if r is zero, meaning we've selected exactly our elements, then we find found a valid subset and then add it to our subsets array. Otherwise, we flip on the AI bit recursively, call the method and then backtrack and flip off the ice bit. Alright, so going back over here. Now we make sure that the starting node is inside the subset. Otherwise, we're not going to be able to create a valid tour. Next, Next, we loop over the variable called next, from zero to n. And the next node is going to be our next like Target notes.

The one we're trying to expand to, if you will. So we make sure That the next node is not the starting node. And we also make sure that it is in the subset produced by the combinations function. Otherwise we're not interested in it. Then we generate the mask, which is called subset without next. And this is the the state or the partially completed tour without that next node.

So we basically flip off the next node and set it to zero. And this allows us to do a look up in our memo table later on. So we can compute the new distance. But before that, we initialize a variable called min distance, which I initialize to positive infinity. And this is the variable we're trying to minimize. For the next note Then for every possible end node, every possible end node, which is not the start node or the end node and is part of our subset, we calculate the new distance from the end node using the subset without next, and then from the node to the next node.

And then if that new distance is less than the global, or sorry, the just the min distance we declared up here, then just update the min distance and finally, cache that and the memo table. So this is the the bulk of the algorithm right here. But we're not done yet. We still want to calculate the minimum cost, like the overall minimum cost of the optimal tour. And to do that, we simply loop from I zero to n skip over the starting node and and then do a look up in our table for that and node, ally, and the state and state. So we finished a tour and the tour ended on node i, and then go from I, which we ended on back to the start node.

So that's the tour cost. Now we just minimize over this variable and update the mentor cost, which if we go back, you can see was one of our instance variables which had set the positive infinity, so we're minimizing this and this is why it gets returned on the get total cost function. All right. So this finds the minimum tour cost. And this section you see right here finds what the actual Pour is, which is really useful, and does that by looking inside the the memo table at the values we've computed. So we initialize a variable called the last index and it initialize the starting node, because that's essentially the very last known if you want, when we do the tour, we end up starting over again.

And the state is the end state. So we're working our way backwards. So we start at the end state, and then we're going to slowly I guess, reduce our tour until we're back to the starting node. So So in our tour, we add that starting node and then we're going to loop n minus one times, and this variable is just for, for counter. So it's not it's not used. Anywhere in here.

So we loop n minus one times and for this index variable, so this is like the, the node we want to, to go to next. So it's the best. That's the index of the best next node. But define that next best node, we need to look at where we were last, which is the last index and go to the next best node which is going to be J. So we loop over all possible j nodes if you will start j at zero and loop up to n. And then skip over when j is equal to the start or is not in the state, because we would have already visited a node otherwise. And if indexes minus one that's the first valid Do we encounter so set index equal to J.

Otherwise, look at the previous distance, so for the node at index versus the node j, and then if selecting node j gives us a smaller value, then we know we want to update index to be j and, and doing this for all all the nodes will find us the next best node going backwards. Then we want to add that nodes index to the tour and then toggle the that bit off and then set the last index to be the current index. So we're going backwards and basically starting from a fully completed touring like shrinking the tour down to just the starting Note again, and at the very end, we want to add that starting node to the tour and then reverse the order of the tour. This is because we're going backwards, we're starting at the end state and then working our way backwards. So our tour is, in fact in reverse order.

So we want to reverse the tour order. And then we can mark the solver as completed. And tour if we look up here was just a list of integers and tour is the variable we return when we call get Tor. The only thing I did not cover was this not in function, which just checks if a bit or the element was not set in subset. So you check that bit is equal to to zero and that's it for the Traveling Salesman Problem. If you have any questions, please leave a comment in the description.

If you like this video, please give it a thumbs up and subscribe for more mathematics and computer science videos. Thank you