Module 3 – Traveling Math – Part One – Sections 6.4, 6.5


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

Leave a Reply

Your email address will not be published. Required fields are marked *