>> 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.