[MUSIC] All right, so Mia showed you a greedy algorithm to try and solve this traveling salesperson problem that didn't quite work. It didn't find the optimal solution for all graphs. So in this video, we're going to look at a different algorithm that hopefully will work a little better. So by the end of this video, you'll be able to describe a brute force algorithm to solve this traveling salesperson problem. So again, here's our graph. Here's our graph of eight cities. We wanna start and end in San Diego, and we wanna find the minimum cost tour that visits each city exactly once, and then comes back to San Diego. Here's again, our graph represented as this adjacency matrix, where each entry in the matrix is the distance between the city in the row and the city in the column. So what is our approach here? Instead of greedily choosing the next best edge, which could get us into these dead ends that Mia talked about, where you'd be forced to take these really high weight, high cost edges. What we're gonna do is we're going to allow our algorithm to just try all possible tours, just try all possible paths through the cities that start and end in San Diego. So that's our approach. It's pretty simple, we'll try them all, we'll just pick the on that's minimum cost. This is what's known as a brute force solution because we're not doing anything tricky, we're just gonna pound it out. We're gonna say, all right I'm gonna tackle this problem basically the hard way. I'm just gonna try everything and then pick the best. And it's a very straightforward approach, and a good approach, as we'll see, for some description of good. We'll also see it has its limitations. So let's give you an example of how this brute force solution is going to work. It's pretty straightforward. We're just gonna pick one path through the cities, from San Diego back to San Diego, calculate its cost by adding up all the distances along those edges. And then say, okay, the cost of this initial path from San Diego to Lima, to Paris, to Cairo, to Perth, to Bejing, to Johannesburg, to Chennai, and back to San Diego is 72,211 kilometers. So that is currently our best path. But it's just our first path, so let's try another one. Let's switch the last two cities, calculate the cost of that path. Well that one's only 67,115 kilometers, so that's one better. So we'll record that one as our best path so far. We'll do another switch, switch around some more cities. This is a new path. We'll calculate that cost, which is 70,016 kilometers. That one's not better than the one we had before. So, we'll keep the one that we had before as our best so far, and so on and so forth. So we're just gonna generate all of the different paths that exist, keep track of the best one at each point and at the end of the day once we've considered all the paths, we'll have the best. And so this works. It's gonna find us the best path. And in this case, I implemented a solution for this problem, this brute force solution, and I found that the best path is actually to go from San Diego to Lima, to Paris, to Cairo, to Johannesburg, to Perth, to Chennai, to Beijing and then back to San Diego. And that has a total path cost of 55,242 kilometers. All right, so this works great, but the problem is how long is it going to take? You might be thinking, mm I don't know there seems to be a lot of possible paths we can take between these cities. Is this really a feasible solution? And if you have this concern you'd be right. So in the next video we're gonna consider the running time of the solution, as well as the greedy solution that Mia presented.