welcome back to module three traveling

Mac part two we’re going to be covering section six point four and six point

five the nearest neighbor and repetitive nearest neighbor algorithm so remember

we talked about two strategies brute force which we covered in the last video

and the nearest neighbor so the pros and cons of the nearest neighbor the idea is

you’re gonna hop from vertex to vertex using just the simple rule from the

starting point what’s the nearest vertex and from there choose the next nearest

vertex and repeat now we do want to pick the nearest one that’s the least cost so

that’s really pretty much it it’s an efficient algorithm because it doesn’t

take much time but it doesn’t get McGarrett it’s not going to guarantee

the best optimal tour because we’re not going through every option we’re just

looking at a small subset so it’s an approximate algorithm okay let’s look at

Willie’s the Traveling Salesman problem the optimal tour on page 182 you end up

finding out that the optimal tour cost 676 but when we do the nearest neighbor

we get 773 so let’s do the nearest neighbor together so we’re starting at

Point a the nearest neighbor so I’ve got choices of 133 152 119 and 185 so the

nearest neighbor that’s the cheapest is 119 so then from there I look at what

are my next options so I’ve got 174 121 122 I’m gonna pick 120 now from there

I’ve got 133 200 119 now you might be thinking 133 but that’s gonna close my

circuit back to the starting point and so I’m not going to do 133 so the next

nearest neighbor is gonna be 199 now from that I could do the 150 to the 170

for the 150 now I’m not going to go back to a cuz I haven’t gotten to be yet so

I’m not going to do that one but I am gonna do 150 and that would have been

the cheapest one anyway and then from be the only way back to a is that so that

is the nearest neighbor and if you add all this up you’re going to get 773 so

what is the optimal tour was not being was not found but that is exactly how

you do the nearest neighbor way easier than brute force so you can calculate

the relative error we won’t be doing that in our problems in our project but

this is how you do the nearest neighbor again can pause it and review it you

start at the starting point and then from there you pick the next closest one

with the least weight and you continue making sure you don’t go back to the

beginning until the very end now there’s the repetitive nearest

neighbor it’s just a variation on the nearest neighbor so the reason that we

would do the nearest neighbor depends on the starting vertex if we change the

starting vertex then it’s likely to be different it’s not unreasonable to

repeat the process several times each time starting at a different vertex in

Willie’s case we have to start at a because that’s where he lives but

sometimes it doesn’t matter where the starting point is and so you can start

at different places and get different nearest neighbors so what do we do with

that or that’s our somewhere other than the vertex we really want to start up

it’s not really a problem because remember that in an abstract sense

you’re starting where you end and so really there is no start and end in a

circuit I know mind blown okay we’re back to Willie

they’ve just removed some of the stuff this is the path we just mapped out of

the nearest neighbor but if we use B as a starting vertex the

nearest neighbor tour takes us from B to C and then to a and then to E and then

to D and then back to B and that gives us 722 which is an improvement it’s a

lot less we could repeat the process again and again and when you do this

you’re going to get closer and closer to the optimal tour and among all the

nearest neighbors the closest we get is 722 so how do you do the repetitive

nearest neighbor you might opt to do this on your project you just start at

any point and again it won’t really work in the project because you have to start

like Willie but if I the nearest neighbor you calculate the

cost of that tour and you repeat the process with all of the vertices and

that’s how you do it and the least cost wins the last thing we’re going to talk

about is the cheapest link algorithm the idea behind it is to piece together a

tour by picking the separate links where legs based on cost so it doesn’t matter

if in the immediate stages the links are all over the place like if we’re

building a tour that doesn’t connect but there’s some rules we can follow and

they’ll come together at the end so this is how it works we’re gonna look at the

entire graph and choose the cheapest edge of the graph so step one choose

just the cheapest edge once that’s done choose the next cheapest edge whatever

that may be now there’s two rules we want to be

careful of don’t allow it to form a circuit except at the very end and don’t

allow three edges to come together at a vertex so what that means is you can’t

have as your vertex one two three that will create a problem so as long as you

follow that rule it will come together at the end okay so among all the edges

of the graph the cheapest link of this is AC right 119 is the cheapest link so

we’ve got 119 now what’s the next cheapest link is seee that’s 120 so so

far we’re just they connected and we got lucky but now we’re looking we’ve got

119 and 120 the next cheapest link is BC but the problem is that coming out of C

if we did that see how there would be one two three legs one two three and we

don’t want to do that so we’re actually gonna cross off that 120 leg because

that’s not possible anymore because it will create that third edge so then the

next cheapest after 120 would be 133 see how they got rid of the 121

but the problem with that is that’s gonna take us back to the starting point

and we’re not ready to end yet so we can’t do that either

so now we’re back here we’ve eliminated those other links and now we’re looking

for the next cheapest and the next cheapest is 150 now you may be thinking

well that’s not connected to anything that’s okay you’re just building the

cheapest links not worrying if they connect so now we’ve got our cheapest

our next cheapest our next cheapest and then we’ve got 152 and again it’s not

violating any rules sewing two edges coming out of D we’ve hit all the other

vertices so it’s fine to go back and so this is it actually

ended up building a link all together formed a circuit when you add it up you

get 741 it’s a little better than the nearest neighbor but not as good as the

repetitive neighbor so again the optimal is always gonna be brute-force but we’re

trying to find other options so it’s not as time consuming so how do you do the

cheapest link you pick the cheapest link you mark it you pick the next cheapest

link and mark it and you just make sure you don’t close the circuit and you

don’t create three edges out of a vertex connect the last two and close the

circuit so we’ve got these seven sites on Mars and we went ahead and changed it

up now again it looks really different but these are all the different

distances in between the graph so if we wanted to do brute force on this we’d

have to do 720 different tours so I think that’s gonna be a pass cheapest

link is reasonable but it’s not too hard so let’s take a peek at it so for

cheapest link we’re basically looking for the smallest numbers first so we’ve

got the smallest number that we see on here is 1300 and that’s PW the next

smallest number is 1500 and that doesn’t violate any rules now we need to be

careful P already has two lines coming out of it we cannot add a third so this

one we did this one we did i n would be the next one so that’s two thousand and

that doesn’t break any rules now aw if we were to do aw it would create a

circuit you see how it would close that loop and we don’t want to close any

loops so we’re not going to do aw the next two that we’re gonna do is HW and

AI and again we’re not breaking any rules

now if we do I w-what happens we get three out of

I wear don’t want to do that so we have to not do that link now IP has the same

thing we can’t do I P but we can do G H and then GN is gonna close our circuit

and then by using the cheapest edge we were able to get it really quickly and

create a loop and get our total length the nearest neighbor algorithm we could

do the same thing so let me grab this guy for you let’s copy this alright so

if we start here we start from a the shortest nearest neighbor would be a P

and then we would go to W because that’s the least edge and then we would go to H

because that’s the shortest out and then to G and then to I and then to n and

then back to a so that would be our nearest neighbor and that’s going to

give us about 20,000 and our cheapest link it just gave us a little bit more

so in this case the the nearest neighbor actually worked a little better so the

first surprise is that the nearest neighbor actually gave us a better one

than the cheapest link so sometimes the cheapest link produces a better tour but

that’s why we call these approximate algorithms again the one that’s always

going to work as brute force but when you have too many vertices you just

can’t do it so that’s the end of the Hamilton circuit unit at the Traveling

Salesman problem you guys in your project are going to complete one as

well