[MUSIC] So far we've been talking about a lot of algorithms for graphs to find distances and to find paths and to represent the graph itself. And in this last module, in this last week, we're gonna start to talk about some more sophisticated graph algorithms. The first algorithm we're gonna start talking about, or first problem we're gonna start talking about, is called the traveling salesperson problem. So by the end of this video, you'll be able to describe what the traveling salesperson problem is. First I'm gonna start with an example of what the traveling salesperson problem is. So imagine that there's a salesperson. And this person happened to be somebody who took our course one in the specialization, and they made a really cool project for their final project. And they turned it into an app, and now they wanna sell this app. And they know that they could put it out there online, but the best way to get people to adopt a new technology and to buy a new app is to actually go visit them in person. So, this person wants to travel the world and try to get people to buy their app that they created in this first course. They live in San Diego, so they start in San Diego, and they've targeted a number of cities where they know people and they know that some people are going to be interested in their app. So they've made a list of these seven additional cities where they wanna travel to try to sell their app. And their goal is to do this with the minimum costs, so the minimum amount of time and the minimum distance traveled to visit each of these cities exactly once and then return back to San Diego. So how are they gonna do this? Well there are a number of different paths they could follow that would complete this visitation of each of these cities. So they might follow a path like this, starting in San Diego, going to Paris, to Lima, to Chennai, to Cairo, and so on and so forth. And you might look at that path and go well, that doesn't look like a very good path. That's gonna take them way out of their way, they're gonna have to do a lot of backtracking. So maybe they shouldn't pick that path. Well, let's try another one. Maybe this one looks better, where they kind of just do a circular tour of the cities they want to look at and then come back to San Diego. Maybe that's the shortest path. Or, perhaps, a better option would be to kind of zigzag up and down the globe and then come around the other side of the world once they get to Australia. Is that the best path? Well, that's the question that we wanna answer in this traveling salesperson problem. It is of course a graph problem. If I take away the world map, you can see that those cities are just the vertices in a graph. And we're gonna imagine this problem that you can get from any city to any other city. But they're in this, in this world we're considering, there's a flight from every city in our graph to every other city in our graph. So their graph is going to be fully connected. There are edges from each city to every other city. Those edges are undirected, meaning they can go both ways between the cities. Now, importantly, these edges are weighted. These edges have weights. And that weight is the distance between the cities. Now, it would be really messy if I wrote all those distances along those edges in that graph representation that I have there. So what we're going to do instead is we're going to represent those instances in a table, where each row in the table is a particular city that you're starting from, and then, the column entries in that row are the distances to the cities that you see along the top. So for example, from Lima to Paris is 10,248 kilometers. The formulation of the traveling salesperson problem is, given n cities, you can see we have n cities here, and one hometown. And we have all pairwise distances between those cities, we wanna plan a tour, starting and ending in our hometown, that visits every city exactly once, such that that tour has minimum distance. Okay, so that's our problem. And it's good for planning a tour to sell your app that you created in our course one. But it's also good for lots of other things. This is a very popular problem and a very important problem to study in computer science. So, what else is it good for? Well, I'm sitting here filming this video in early December, and if you celebrate Christmas, you know that Christmas is coming up, and what's one problem on Christmas? Well the problem is that Santa, who lives at the North Pole, has to go visit every single child in the world and give them presents. And Santa only has one night to do this. So obviously Santa needs to find a very efficient path that visits every city, every home exactly once and then returns back to his home at the North Pole. So there's a very straightforward application of the traveling salesperson problem, the traveling Santa problem. Okay, if you want an actual application, that's a little whimsical, but if you want an actual application. Here's another one, the problem of bringing children to school on a school bus. The school bus starts at school, it has to go collect a number of children visiting each of their stops once and then return all those children to the school, do the same thing on the way home. So, that's an example of a traveling salesperson problem, a real world example. Other examples are less related to transportation and route planning. There are actually several examples in creating circuit boards. So there have been application in where to drill holes on circuit boards and how to do wiring on circuit boards. These can be mapped to instances of this travelling salesperson problem and then studied along with studying solutions for the travelling salesperson problem. So speaking of solutions, that's where we're going next. Mia is coming up with a concept challenge on how to come up with, potentially, one solution to this problem.