[NOISE] Okay. So Christine introduced this problem that we're trying to solve. The travelling sales percent problem. And in this concept challenge we're going to try to solve it. So, we'll ask you a question. We'll invite you to think about it. Watch a discussion. Confirm your understanding and listen to the explanation that we give. So let's think back to the problem that we have. And in this traveling salesperson problem we want to start at our hometown. Walk around a graph and try to do that with the least possible distance. Now, one good strategy for solving a problem would be to say I want to make sure that the distance I go at any one step is the smallest possible. So, this is called the greedy approach because we're making choices that try to improve our situation as much as we can at this particular moment, thinking about just the present and not the future, just right now take the next best choice. And so, in this greedy algorithm, at each vertex that we land. What we do is we look at all the edges that lead us to that we have not visited and pick amongst those edge that has the shortest distance and to reverse that edge go to the next vertex and do the same thing. Look at the edges that go all the vertex that we haven't yet visited, look for the minimum distance edge there. And follow it to the next hop. And keep on going until we end up back at home. So, let's think about how this greedy algorithm behaves on a warm up graph. So take a look at this graph please, and think about if the green vertex, vertex labeled number one is our hometown, what tour would the greedy algorithm construct for this graph? So how do we know that this is the best possible tour for this graph? Maybe some other tour would give us a smaller distance. And all ready compared the greedy tour with other tours what we want to do is list out all the possible tours. And so for each possible tour, what we're doing is we're starting at one and then thinking about what are the next possible hops, and at each point we can visit any of the vertices that have not yet been visited because this is a complete graph. And so we can go from one to two to three to four, back to one, and then we could also instead go from one to two to four to three to one or. Well maybe our first help wasn't a two, it was a three and so over here we have three possible tours that are listed and notice that there are actually six possible tours but the six possible rearrangements of the vertices one three four are paired off by symmetry. And when we're comparing these tours the way that we wanna compare them is to find the distance its traverse. The distance that's travelled along these tours. And so in order for the distance calculation, we don't need to worry about the directions. So we can just look at, you know half of the tours save ourselves some calculations. So these three tours that we've got listed represent all possible. Tours through [INAUDIBLE] start and end at hometown one. And now if we wanna compare our greedy tour which was that top one with all others, we can compute the distances along each of these paths by adding up the wait. Of each of the edges and so the first one gets edge 21, the next one would be 22 and the next one is 23. Yay, 21 is the smallest. So our greedy algorithm actually worked for us, which is awesome. It's a very simple to state algorithm and it found the smallest distance path. Now my question is is this always going to be the case? Will the greedy algorithm always find the best, in the sense of smallest distance to work through the graph? >> Hi, my name's Kevin. >> My name is Ashley. >> I'm Anni. >> And Anni I don't think that a best possible graph would be found if we used a greedy algorithm because if we changed node two to three's edgeway >> To ten, I don't think and if we go around the outside again, I don't think that's the best possible tour for the traveling salesman. >> I don't think it will always work, but for a different reason. I belive that when you have covered all the notes and you want to go back to your starting point, what if a previous node that you had visited has an edge that is lighter to go back to that starting node, so maybe backtracking will be better and provide a lighter short path. >> Well, I'd also like to say that when you're at your last node, you have to go back to the beginning, right? >> So there's a possibility that you can take a lot of different paths, but then when you're at the very last one and you have to get back to the beginning, you're stuck because maybe that edge back to the beginning is really, really long, so that's my biggest concern with whether there is a better path than the greedy algorithm. >> Right. So, what a counter example B from node four to one, if that edge weight was changed to something like ten. >> All right. Welcome back. As you saw when this UC San Diego learners discussed this question, there was concerned that if we fiddled around with some of the edge weights, we can fool the greedy algorithm. And what we'll do right now is will construct a counter example. An example graphs with specific concrete small graph where the greedy algorithm just makes the wrong choice. So let's see what the greedy algorithm does with this graph. We start at vertex one and we look at all the possible next steps. And we might go to vertex two, three or four. Now, vertex two is the one that we get to from the smallest distance edge because that edge is label five so we go down. And now, to vertex two we wanna go either to three or four and we compare it's distance for, it's distance six to vertex four, distance seven to vertex three. Six is less than seven so we go over to four. Now, from vortex four we're forced to go to three before we go to back to one because we wanna visit every vortex before we head back home and that means that we have to take that really expensive. The long, heavy edge over to three and spend that time going through the ten units that it costs us to go through that edge before we get to head back home to vertex one from vertex three. And so the greedy algorithm would go from one to two to four to three to one, and it has cost 27. Now let's compare this tour and this cost to the other possible tours of the graph. And we can look at all of the other possible tours just like we did before and for each one of them add up the weights along with those paths. And we see that the one that went one to two to three to four to one has caused 29 compared that's a little bit worst in the greedy algorithm and be the greedy algorithms gonna help. Except If we were clever and went from vertex one directly to vertex three in the hope of having to avoid that heavy-weight ten edge later on, then we can go one to three to two to four to one and it only costs yourself 36. And so what we see it in this graph is that sometimes making the less than optimal choice right now will lead us to better global performance later. Now, what that also means is that the simple algorithm we hoped would help us solve TSP doesn't do the job. It doesn't cut it. And so what we need to do is come up with more sophisticated algorithms. And that's what Christine will talk about next.