In the last video, if I remember
correctly 'cause it was a good month ago now.
I drew a graph out and we
worked through it with Dijkstra, and at the end
I pointed out a couple of problems.
So let's just remind ourselves about
those problems and then when we'll talk about A star
we can see how it addresses it.
The problem is with Dijkstra that it will follow
the path currently shortest and that -- and
doesn't pay any attention to what
direction it's going.
So if i'm coming down here to my end goal,
and I'm starting up here, that's fine if
the weights are all the same because it will
look at it up here and there, but I'll
get there quite quick.
The problem is of course if you've got
the map of the UK and it's searching quickly
down all nice motorways when in
fact actually we don't need to go down
the motorways because it's a country road drive
or something like this. Now, course in
practice, it wouldn't take very long
still because your computer is quite fast
but the whole point of these algorithms
is they're quick and you can imagine if you're
writing a sat-nav, you don't want it to
take a long time churning for the roads unnecessarily.
The other problem is,
if your graph doesn't look like a map because,
you know, in some sense the UK road network
isn't quite sparse but the most of the
country doesn't have a road on it. It's
mostly fields and sheep and stuff. But,
you know, all houses. If you have a
situation where you've got a quite a
dense network like this, so I guess you
could say a bit like Manhattan. But also just,
you know, another problem where your
graph structure is different. So if
you're looking through an image or
something like this. I'm starting up here
and cross that out. There we are and I'm
finishing down,
I don't know... here. Let's remember that
Dijkstra follows the shortest path based
on the distance of each of these. Now, if
it is just a uniform grid, let's
say, we have no interesting information
to provide for these weights and all
these weights say one so it's just
gonna to flood fill from here. It's gonna
go here, and then here and then to
these three and then to these four, and so on and
that's not very optimal. Especially
if we just literally want to go
straight down here, like this. So we want to
build in some kind of idea of, but not
necessarily the direction we're heading but we are
at least going towards our goal, so we can
aim for it. And that's what A star does.
A star is basically a small extension to
Dijkstra that builds in a heuristic that
says we're getting a bit closer.
This is our nice screwed up graph from last time
and this is our nice new fresh graph
that I've done which is, topologically exactly
the same. I may have traced it. So, we
could do Dijkstra on this.
I've got my little cards for my priority queue.
I've reminded myself how the end condition is
so I can end it properly.
That's all fine. What we want to do is extend this
to A star. Now, A star is basically exactly the
same as Dijkstra, except it has an
additional heuristic that is how far do
we have to go. And, in this case,
a pretty reasonable heuristic to come up with
will be literal Euclidean distance
of how far we have to go. So, in this case
S to E will be that far, C to E will be that far.
And so on. I couldn't think of a good way of
calculating this without literally just
measuring it. So I got my, got my...
dainty 10 meter tape measure,
which is a little bit overkill. But we'll,
you know, make it work. So this is all a bit odd.
I don't use tape measures as much as you can
imagine 'cause I mostly sit at a desk
and do typing. This is a tape measure in
centimeters and inches. Let's use inches today.
Alright.
Imperial, woo. So I'm gonna literally
measure the amount of inches from S to E,
and then A to E, and then I'm just gonna put
this on here now. And this is where
you fast forward. So, I'm gonna use it,
the black pen for this. So let's say this is 10.
There. This is harder than I thought it would be.
I haven't got enough hands.
8... 6... I'm rounding up a bit
it's not very accurate. 4... So the green
ones are our step distances from Dijkstra and the
black ones are measured inches.
Also 3, 6, 7. We're getting there. 6 again.
Alright. That's me doing my workman's... Now:
we've got exactly the same graph as before but now we
have some measure of the distance to our thing.
It's not a very good heuristic in
a sense that my measuring is not very
accurate and for A star to work really
well, you have to have a consistent
metric and you have to, not
overestimate how far you've got to go.
Things like this... But, we'll just
hope it works, sort of work itself out....
You know, it can't be any worse than me
you know, doing it by hand anyway. So, recall
when we did Dijkstra. What we had was we had
some queue here like this. These had the current
distance from the start to these nodes.
And if one of the nodes had a
shorter path, it would move up the queue and
then when we wanted to expand a node we take it
off the queue. A star works exactly the
same way, except the distance isn't what
we ordered them by anymore. It's a
distance of the path plus how far they
have to go.
so for example. B, the distance is
going to be 2 plus 7 which is 9. Alright.
So B will have a value of 9 on this queue.
And the idea is that if something has a
long way to go,
it's going to receive a higher weight
and be further down the queue and
expanded later. What it will do is
prioritize nodes, that are going roughly
in the right direction, unless... I mean it will
still go down really good paths, really
short paths. But not at the expense of
everything else, it's the idea.
OK, so let's run through this just like we did
with Dijkstra and hopefully I won't make
any mistakes. People will very kindly
point them out if I do. Oh look, look. Checkered flag.
This is why I don't draw things, because
it's not it's never good... Right,
okay, we're starting at S. I'm not going to
draw the infinity symbols on because we
know that all of these nodes start with
a distance of infinity because we
don't know how far the path is. In Dijkstra,
we store the distance to each path, and
we also ordered by that distance. We've
now got two separate measures we're
measuring in A star: one is the distance
to the node, and one is the distance to
a node and any remaining distance. So, we
kind of need to have two values on each
of these things. So I'm going to try and
keep the colors the same so that we
don't lose track.
So anything I draw in green is
going to be this 'g' cost function which
is the distance to a current node,
so for C that would be 3.
And then, in black I'm going to have 3
plus 8 which is the sort of combined
cost; the thing we're actually ordering by.
OK, so the path cost to S is 0 and the sort
of distance to go is 10, but it won't
matter because S is the only thing in
our queue. So we'll put S in the queue but everything
else have a distance to infinity. So
let's start expanding some stuff. So A
first. A has... I gotta find A mate. Fast forward.
Oh here we are.
Why aren't these in alphabetical order?
I mean, you know... What was I thinking?
Right, so A has a distance of 7 and a combined
distance of 9 plus 7 which is 16. The
same for B. Same B, B, B... Again B.
I mean it's actually at the end.
Unbelievable. So I'm gonna
keep seeing it at the top now 'cause I know
that's coming.
OK, so B has a weight of 2 and a
combined cost of 7 plus 2, which is 9.
So, I'm gonna put that in there. Now, B goes in
the queue and goes ahead of A, because
9 is smaller than 16, right. We're
keeping a track of these green distances.
We're not actually using them to see which one
comes next. And then C. C has a path
cost of 3 and then a combined weight
of 11. 8 plus 3. And then that goes in
just above A like this, right. So
actually, so far, pretty similar to Dijkstra,
apart all the numbers are changed. So what's next.
We start expanding B. I haven't been
keeping track of the previous node so
all of these currently there's the storm
in red all are going through S
at the moment.
OK, so B next. We can go to A. A has a
distance of seven when we deciding
whether the path to A better via B
we don't care about this heuristic,
we only care about the actual cost of it,
the path to A, so in this case 2 + 3 is
less than 7 just like with Dijkstra
we're going to replace it so A, its new weight
is going to be 5, and 16 is going to
be 5 + 9, so 14, right? And this now,
this path is going through B, not..
Do you think I can turn this into a B?
Oh yes, there we go, look at that.
So it stays below C, it's not a big deal.
OK, D... Let's find in my shuffled list.
If you're implement this, don't shuffle it because
it'll be a lot harder to find in memory
Right, there we are. B has a path length of 2
D has a path length of 4, so that's a path length of 6
and D has got a distance of 8 to the end so
actually you can see here that D is
traveling forward in this direction, but is actually
getting further away than B so these
going to be quite heavily penalized
that's our hope so D is not going to be
expanded for a while we're going to look
there until it's a last resort
So 8 + 4 is 12, and that path goes through...
You know what, I'm just gonna leave the lids off.
And that goes through B. So put that in.
And that goes above A because A is a terrible one,
remember there's a fallen tree on that one,
but it still could be back and then
finally H. Now, H has a path length of 1 which is
nice and quick, B has a path length of 2 so
the total path cost is 3 and the
actual heuristic cost is 3 plus 6 which
is 9, that's 9 in here, 9 is looking
pretty good right now.
Now H goes straight above everything
like this, right?
B is about to pop out so that's good.
So B is finished, and we put B on our finished pack.
Huh, finished stack... Finished list?
Finished data structure over here.
Next up is H, right? Now,
last time we didn't expand H next,
we expanded C next in Dijkstra because
they had the same rough paths cost which
is 3 and C was already in the list so
now we already started to move a little bit
faster with A star which is good because
it means my example is working so H comes off
and let's see where we can go
we could go to F, so that's easy, I'll find F
F has a past of 3 + 3
which is 6 and it has a distance to go
of 6, so that's a total heuristic cost of 12
and it's going through H. Right, this goes in
and it will come in behind D here with a
path cost also of 12, right, in general
if there's a conflict will just put the first on in
you know, depends on your implementation
G has a path cost of 3 from H plus another
2 so that's 5 and then plus another 3 is 8.
Ok, we're done with H
G goes in right to the top which is good
news for us, for our nice elegant search.
So we're going to expand G, so where's E?
But I'm not gonna go off half-cocked this time
and finish my algorithm here. G has a path
length of 5 and so E has a path length
of 7
see now I've drawn this checkered flag and
it's in the way of my numbers, thanks for
the suggestion there. Right, E has a
heuristic cost of zero because we're at
the goal so actually 7 is the final
value that we get given here and this
goes through G and we're going to
put E in, so E goes in here
G is not really on the stack anymore.
G can't expand anywhere else, we've already
been to H and so the next iteration of the
algorithm starts, right? We popping off the
top
we're about to expand it and we realize
that's where we're going and we finished
our algorithm
ok so then just like before we trace
back through so E goes to G and then...
Where's my G? There it is. And G goes to H,
and then H goes to B,
and B goes to S, and S is the start, alright?
So we've got our path, S-B-H-G-E
Now in this case it's exactly the same path
as Dijkstra because
I picked a fairly reasonable heuristic, right?
Plus or minus a bit of my dodgy measuring
But you can see we didn't bother to expand
C or L or even consider I and J many fewer
nodes got put in the stack...In both terms
of the amount of computation we did and
the memory footprint was reduced and we
still obtained the same result.
So there were one or two comments on the last
video about not expanding those but
you're saying that on A star you
definitely don't have to expand those,
No. The comments on the video were
because basically I forgot to wait
until E was expanded to finish, I got
overexcited and as soon as I saw E,
I declared it over when we went and got
coffee and yeah and that's not right
because technically speaking there could
have been a path from say, F to E, that
was super-sneaky and really quick, right?
I'm sorry, super-sneaky is not a technical
term you see in the literature, and if
that had happened we have to wait until
E bubbles to the top of our priority
queue to be able to know for sure that we've got
the shortest path. In this case it was
very straightforward, E went straight to
the top, but you can never guarantee and a
different graph will have a different
thing
so the actual stopping criterion for
both Dijkstra and A star is when your goal
node gets to the top of your priority queue.
But yeah that was good that people pointed that out
because it completed the video with a
bit of extra comments. To wrap up you can
imagine now that we've seen a video on
how that works in terms of GPS positions
and we've seen a couple of videos on
pathfinding and there's lots of videos on data
structures in this you can imagine now
that you might start to think i can
actually not see how that might be
implemented I could see you know the
parts of the system that have to work together
we've got a map that stored in the
memory
we've got nodes that we're trying to get
to and from, that we've got an algorithm
that will find a way through
Now, you can imagine also that it's
unrealistic to expect a small sat-nav
to completely compute its way through the
UK but if you saw "I what the best path
from Land's End to John O'Groats" you
might melt your sat-nav unless you do
something a little bit smarter so you
can imagine they might precompute some
of these things but they know the
shortest way of getting from Nottingham
into London is via the M1 or
something like this
to sort of hard code some of it in some sense
to be honest
I don't work for a sat-nav company, I don't
know what their proprietary algorithms
are, but you can see this is the kind of
thing we're doing we're trying to find a
nice elegant way of getting from A to B
and there's lots of pathfinding algorithms
and you could come up with lots of
interesting heuristics, not just euclidean distance
Also of course they're going to
have a GPS to measure up in your dating
that I mean yet although i would say VPS
often has an accuracy of possibles few
meters so it was shoddy measuring tape
is actually pinpoint precision compared
to that still have maps are carefully
crafted would be exact known positions
of all these junctions and they know how
long it takes to travel out the
roundabout and they know how long it
takes because of traffic and think about
this they're going to be doing a lot
smarter or albums and i'm doing but this
is a start and you can see you could
build this up into a really good system