Tip:
Highlight text to annotate it
X
So the Nearest Neighbor Algorithm turns out to be so cheap and easy that a quick
improvement to it is called the Repeated Nearest Neighbor Algorithm.
And the idea here is that we repeat the Nearest Neighbor Algorithm starting at
each of the vertices. So let's start at vertex A.
So starting at vertex A, we would go Cheap, cheap only choice, only choice.
And our total cost for the circuit AD, oop, that's not a D.
for AD CBA. Our total cost there is, is, 26 that's
the one we found earlier. And that's not a particularly great
circuit. Okay so lets try again and this time lets
start at vertex b. And from vertex b.
our cheapest option is up to a and from a down to d and my only option is this way
and then this way. So we got BADCB.
And let's see DA, sorry, BADCB. That's what?
4, 4 plus 1 plus 8 plus 13. That's, that's also 26.
How? Well actually, that's exactly the same
circuit we just had here. Notice that if we sort of started at B,
this'd be BADCB. This is actually the, the same circuit.
Okay, well that didn't help much. Let's try another one.
So let's try starting at c this time. So if we start at c, we're going to go,
let's see, two, eight, 13. Cheap, cheap, only choice, only choice.
So we go D, I'm sorry, CADBC and it looks like the cost of that one is what, 2 plus
1 plus 9 plus 13 Is 25. And notice that we've made an improvement
now, we've found a, a slightly better circuit than we had before.
So this is an improvement. And so we got one more to try here, so
let's go ahead and try starting at vertex D.
Here we go, let's see, 1, 9, 8. So cheap 4 or 2, cheap.
only choice only choice and this looks like its exactly the same circuit we just
had here, right? CADBC, yep so this is the same circuit.
we certainly could write it as DACBD, but it's the same circuit that we had there,
so it's going to have the same cost. So this is our so of the circuits that we
found using the nearest neighbor algorithm starting at each of the
individual vertices Twenty five is the cheapest cost and so this is our winning
circuit. Now often times we will go ahead and
rewrite our circuits starting at the vertex A, so we can do that here by
saying if I were to start at A, from A I would go to D to B From, sorry, from A to
D to B to C. From C back to A.
And so this circuit is equivalent, equivalent to this one.
It's just written with a different starting point, and so there is our
answer for the Circuit generated by the nearest neighbor algorithm, which, if you
remember back, is still not the optimal circuit, but it's certainly better than
the pla, the, than the, just doing the neighbor, nearest neighbor algorithm once
gave us.