Advertisement
English transcript
PROFESSOR: It was written about Route 66, which used to
be the main highway between Chicago, Illinois and Los
Angeles, California.
Very famous highway because anybody who wanted to go
across country always took route 66 because it was the
shortest way to go.
And the question is, how do you find the shortest path?
Not just any old path or a good path, but how do you find
the very shortest path?
And that'll be the subject that we're
going to discuss today.
But route 66, I lament its passing, but it's been largely
replaced by the interstate highway system that was
created by President Eisenhower.
Guess why?
Let's see, maybe the ROTC people know.
You know why Eisenhower created the
interstate highway system?
Well, in public affairs, of course, there's always a
distinction to be made between the
explanation and the reason.
The explanation was--
AUDIENCE: To move weapons across the country?
PROFESSOR: Well, to move nuclear
weapons across the country.
Let's put it in, sightly, more benign terms.
Eisenhower had observed that the German army was able to
move its troops rapidly, even though we bombed their
railroads into oblivion because of their auto bond.
So Eisenhower conceived that if there were ever an invasion
in the United States, we too would want to be able to move
our forces around on a highway system.
And consequence of that, we have a pretty good highway
system and pretty awful railroad system.
It's interesting.
I'm a beneficiary of that, in a funny way, because I'm from
East Peoria, Illinois.
And I was surrounded by the factors of Caterpillar Tractor
Company, which made all of the tractors that built all of
those roads.
So my high school spent money like water from that huge tax
base of all those factors.
Anyway, today we want to find the very best path, instead of
just a good path.
And like the last time, we'll deal with, both, an example
that we can set our program to work on.
By the way, can you find the shortest path between S and G?
Would you like to bet your life on the shortest path
between S and G?
Probably, not.
With your eye, you can find a good path.
But you can't find the best possible path.
Today, what we're doing is probably not modeling any
obvious property of what we have inside our heads.
But being able to find the best path is part of the skill
set that anybody who's had a course artificial intelligence
would be expected to have.
So we're going to look at it, even though it's not like many
of the things we do.
A model of something that's, probably,
going on in your head.
So we're going to use, both, this example from Cambridge
and our Blackboard example.
Let's see, we have to caution ourselves.
Tanya, is search about maps?
No, it's about what?
Starts with a C. And the next letter is H. And it ends up
being choice.
So we're talking about choice.
Not about maps.
Even though our examples are drawn from maps because
they're convenient, they're visual, and helps understand
the concepts behind the algorithms I'm talking about.
So let's start off by looking at our classroom example.
And I did something today that I neglected to do last time.
And that's talk to you about what I meant
by heuristic distance.
It's those pink lines that I just drew on the map.
We're talking about the distance as the crow would fly
between two places, even though there's no road that
goes between those two places.
So in general, and we discussed last time, it's best
to get yourself into a place that's close, as the crow
flies, to your goal.
And of course, that's a heuristic and it can get you
in trouble because it's not always true.
It would appear that being at node E is a good place to be
because it's not very far from G. But in that particular case
designed to illustrate the point, being close is,
actually, not a good thing because it's a dead end.
But in general, it's a good thing to be close.
And we talked last time about hill climbing and beam search,
being close was the objective of those kinds of searches.
And at one point, in a beam search illustration, we had C,
B, A, and D. We had paths terminating at all four of
those nodes as candidates for the next round of search.
And we decided on the basis of these airline distances to
keep D and B, and reject A and C because they're further away
as the crow flies.
Now, I repeat this even though many of you have had this
fixed already in your tutorials because we're going
to need this concept of heuristic distance today.
And I wanted to be sure that that point has been clarified.
So now, with this smaller map I imagine you can do, by eye,
a determination of what the shortest path is.
What is it, Juana?
Can you help me out with that?
AUDIENCE: S, A, D, G.
PROFESSOR: S, A, D, G. And if you add up those distances,
the distance is 11 along that path that goes from S, first
to A, and then to D, and then from D to G. So Juana asserts
that that is the best path.
And we're going to treat Juana as an Oracle because we're
going to follow, in our initial attempt to understand
these algorithms, a very important
principle of problem solving.
And that is that, if you want to solve a problem, the
easiest way is, usually, ask somebody who knows the answer.
Or Google, which also, probably, knows the answer.
So in this particular case, we believe that
Juana knows the answer.
And she said that the shortest path is S,A, D, G, and its
path length is 11.
But we don't trust her because we're applying to the same
medical school and she may be trying to screw us.
[LAUGHTER]
PROFESSOR: So we're going to be very cautious about
accepting her answer until we've checked it to make sure
that she hasn't attempted to delude us.
So how do we go about doing that?
Well, one way to do that is to check to be sure that all
other possible paths that we could develop end up being,
for sure, longer than the one that Juana has told us about.
So she's told us about S, A, D, G. And it has a total path
length of 11.
And now what I'm going to do is I'm just going to develop
the rest of this tree-like diagram.
But what I'm going to do is, I'm not going to do it in a
British Museum or random way.
What I'm going to do is, I'm going to look at the choice
that corresponds the shortest path that can be extended.
So the shortest path that can be extended is
this one right here.
The one that just has the starting node in it.
And I could have gone this other way to B. And if I go
that other way to B, then the path length along
that side is 5.
And likewise, if I look at the path that terminates in A,
that has a path length of 3.
So now I've got two choices.
A and B. I've got choices that extend
beyond those two places.
So I'm always going to extend the one that
has the shorter length.
So in this case, that would be the path that goes from S to
A.
So if I from S to A, I don't have to go to D. I can also go
to B. And if I go to B, then the accumulated path length is
S, A, B. That's 7.
And know that we're talking now about the path, like the
accumulated path length, that we've traveled so far.
Last time we were talking a lot about
distances to the goal.
Heuristic estimates of how far we are from the goal.
Now we're doing exactly the opposite.
We're not considering how far we've got to go.
We're only thinking about how far we've gone so far.
So now, repeating these steps again.
I've got 7 and 5.
So I'll go over and consider the choices that go through
the B node on the path S, B. And that gives me S, B, A and
S, B, C. And what are those path lengths?
Well, let's see.
S, B, A would be 9.
And S, B,C would be 9.
And now the shortest path is this one over here.
So I extend that.
I go S, A, B. S, A, B. The only place I can go is C. That
adds another 4.
So that's 11.
And what do I know about that path?
I don't have to take that any further, right?
Because the path length, since I've gone on that path
already, is equal to the path length that Juana has told me
gets me to the goal.
So it'll be foolhardy to carry on because, presuming that
these lengths are all non-negative, I
can't do any better.
And I can't even do as well, unless I've got a length that
has 0 length.
So now that I have that idea, I can quickly finish up by
saying, well, let me consider these two paths.
S, B, A can only go to D. And if I go to D, that adds 3.
9 plus 3 is 12.
Nothing else can happen there because that's 12 and I've got
a path of a goal that's 11.
C, I can only go to E. It's a dead-end but I don't have to
think about that because I know that the accumulated
distance along this path is 6 plus 9.
That's 15.
So all of these need not be extended any further because
their length, accumulated so far, is equal to or less than
a length of a goal.
So I've checked the Oracle.
And although we're applying to the same medical school, Juana
has told me the truth.
So now, unfortunately, Juana's not always around.
And I don't always have an Oracle.
So I'm going to have to have some way of finding the
shortest path without that Oracle
that I can check against.
Let's see.
What can I do?
Maybe I can do the same thing I just did.
Always extend the shortest path so far and hope that I
run into the goal at some point.
And then I have to ask myself the question how much extra
work did I need to do when I don't have the Oracle?
Let's just try it and see what happens.
You don't have that path to start.
So I just have S. This distance is 0.
I can go either to A or B. If I go to A, I've got
a distance of 3.
Here, I've got a distance of 5.
I'll extend the path that goes S, A. That can either got to B
or D. Going to B or D gives me 7 that way.
S, A, D gives me 6.
So looking across all of these and extending the shortest
path so far takes me back over to S, B. So I extend those.
S, B takes me to A or C.
And those, in turn, have total accumulated path
lengths of 9 and 9.
Now the shortest one is S, A, D. You see the pattern.
Now let's see.
I haven't found the goal yet.
So I can ask myself the question is any of the work
that I've done so far wasted?
No because all of the paths that I've got so far are
shorter than the path of the goal because the goal
hasn't shown up.
So when I do my oracle checking after I found the
goal, none of that work's going to be wasted.
So in the end, I don't, actually, need the Oracle.
I could just develop this graph by extending the
shortest path, so far, until I hit the goal.
And then, perhaps, do a little remaining checking to make
sure that all the other paths extend with a length that's
greater than the path of the goal.
So if those words are confusing, let's carry on with
the algorithm, and I think it'll be clearer.
So let's see.
We've got the 7, 6, and two 9s.
We're going to extend the one that's 6.
That gets this to the goal.
Boom, we've got it.
And we've got a path length of 11.
Note, though, we can't quit because we have to be sure
that all other paths are longer than 11.
So now we have to carry on with the same algorithm that
we started with.
The Oracle checking algorithm.
And when we do that, we look for this shortest path, so
far, that has not been extended.
That's B, S, A, B. That goes to C. That's 11.
So we're done there.
A goes to D. That adds 3.
That's 12.
C goes to E. That adds 6.
That's 15.
And sure enough, we're done.
OK?
Elliot?
AUDIENCE: Does it know that there's know that there isn't
a chance that you could have a zero distance extension from
the [INAUDIBLE]?
PROFESSOR: The question is, does it know that there's no
zero distance length that's coming up.
That's an implementation detail.
This guarantees you'll find a path that's as short as any
that you can possibly find.
But there might be others if they're zero-length lengths.
As long as they're non-negative
lengths, we're safe.
We've got a shortest path.
So that was easy.
And now we can repeat the exercise with our more
complicated map of Cambridge.
First of all, let's do depth first just to recall what that
looks like.
That is, certainly, not a short path.
So let's try this idea, which, by the way, bares the label
branch inbound.
Let's try branch inbound on the same map.
And there it goes.
Each of those little flickers is trying another path.
So you can see it's working it's guts out to find the
shortest path.
It's almost there but it's almost a pathological case.
Or it's almost doing British Museum.
There it's finally found the shortest path.
Now there are some things we can ask about that.
But first of all, before I ask anything about it, I'd like to
get the flow chart up on the board because we're going to
decorate that flow chart, a little bit, as we go.
So the first thing we do is initialize queue.
Then we're going to test first path on the queue.
Then we might be happy because we might be done.
We might have a shortest path to the goal.
Actually, that's not quite true, is it?
We can't really quit until every other path is it.
Well, that's interesting.
If the first element on the queue gets us all the way to
the goal, and we sorted our queue by path length, are we
through as soon as that first element on the queue gets us
to the goal?
Yeah because every other path must have been
sorted beyond it.
And therefore, it can't offer us a shorter path to the goal.
So if the first path is a path to the goal we're done.
Alas, it usually isn't.
So we'll extend first path.
We're going to put all those extensions back on the queue,
and then we're going to sort them.
So that's, pretty much, the same as we did last time.
We're always going to put the elements back on the queue.
We're going to look at the first element the queue and
see if it's a winner.
If it is we're done.
If it's not, we're going to extend it.
And then go back in here and try again.
Well, sort of.
But we noted that this did a awful lot of work because if
we look at those statistics up there, it put 1,354
paths onto the queue.
That's the N queueing part.
And then it extended 835,000 paths that had come to the
front of the queue.
Now I'd like to give you an aside because it's easy to get
confused about N queueing and extending.
In all of the searches we did last time, it would have been
perfectly reasonable to keep a list of all the paths that we
had put onto the queue.
An N queueing list.
And never add a path to our queue if it terminates in a
node that some other path terminate in that has already
gone to the queue.
What I said last time was let us keep track of the things
that have been extended and not extend them again.
So you can either keep track of the nodes that have been
extended and not extend them again.
Or look at the paths with nodes that terminate, and
blah, blah, blah and been put on the queue, the queued ones.
And not put things back on the queue again.
And I think, last time, I may have put a column in there
that said N queued.
It should have been extended.
Even though N queued worked last time, only extended works
this time because we want to be sure that anything we
extend is a short path.
So the N queued idea doesn't work, at all, for these
optimal paths.
So now I want to come back over here off the side bar and
say that we're keeping track of all of the nodes, all of
the paths that end in nodes unless they have already been
extended beyond that particular place.
So we need to decorate our algorithm here and say test
first path and extend the first path
if not already extended.
Because you can see that in the example I had, so far, we
did that same silliness that we talked about last time.
We extended paths that went through A more
than once, like so.
Would it ever make sense to extend this path?
No because we've already extended a path that got there
with less distance.
Will it ever make sense to extend this path?
No because we've already extended another path that
gets to be by a shorter distance.
So if we keep an extended list, we can add that to
branch inbound to our advantage.
So let's see how that would work on the classroom example.
And then we'll do Cambridge.
So this is bridge inbound, plus an extended list.
And I do mean extended.
Not in the N queued list.
N queued list won't work here.
So let's see, I start off the same way as I did before.
S goes to either A or B. That's a length of 3.
That's a length of 5.
So I extend A. That goes to either B or D. But B is as if
it wasn't there at all.
Oh, sorry.
Hang on.
B goes there.
And those path lengths are 7 and 6.
And now I look around on the board, and I say what is the
shortest path so far?
And it's B. So I extend that to get to A and C with path
lengths of 9 and 9.
And what's the shortest one next?
It's D. And that goes to G. And the path length is 11.
And what's the shortest one on the board?
The one that has to be extended next.
That's this one that gets to B. But I've already extended a
path that get to B. So I don't,
actually, do that extension.
So I've saved some work.
But I've got to go over here and do these two now.
But wait.
I've already extended B. I've already extended A, so I don't
have to do that one either.
The only one I have to do is the one that goes to C. And
that those then to E with a path length of 15.
And I'm done.
So if you compare this one with a previous one, you can
see that there might be vast areas of this tree that are
pruned away and don't have to be examined all.
So now, just for the sake of illustrating that, I would
like to keep track of just one of those statistics.
The number of extensions.
So for this particular example, case one, the number
of extensions was 835.
Why don't you see if you can guess to yourself what it
would be if I use this concept of an extended list.
See, I'm not going to extend anything I've already extended
because it's guaranteed to have a longer path length then
something that already got to that same place.
So it makes no sense to do it.
So let me change the type to branch-and-bound with an
extended list.
I'm going to turn the speed down a little bit so
we can watch it.
It might take the rest of the hour.
Who knows?
Still doing a lot of work.
Still examining a lot of paths.
Well, look at that.
Instead of 835 extensions it only did 38.
So that's a pretty substantial savings.
And you would never not want to do that.
So note that that's a layering on top of branching out.
That's not a different algorithm.
It's an adjustment improvement to the algorithm, and it makes
it more efficient.
So this whole thing is based on what I call
the dead horse principle.
As soon as we figure out that a path that goes to a
particular place can't possibly be the winning path,
we get rid of it, and don't bother extending it.
It's a dead horse principle.
But if we look at this example, what's the shortest
possible length of a path that's already
gone from S to B?
What do you think, Tanya?
Well, first of all, it can't be less than 5 because we've
already gone that distance.
So when I say what's the shortest length of any path
that there could possibly be that goes from S to D. We know
it's at least 5.
But can we say something more about it?
Especially, when we look at these airline distances, and
note that this airline distance is 6, and that's a
little more than 7, and that's a little more than 7.
So what do you think?
So it's gone from S to B, and the question is what's the
shortest path that could possibly be that had started
out going from S to B?
11 right?
Because we can't have a path that's shorter than the
airline distance.
If there were a straight line road from A to G, its length
would be 6.
But there isn't.
So that gives us a lower bound on the distance that we have
along that path.
So we're using the accumulated distance, plus the airline
distance, to give us a lower bound on the path that we've
started off on that goes from S to B.
Once again, let's solidify a little bit by simulating the
search and seeing how it turns out.
Not just I did last time, I'm going to forget that I've got
an extended list.
I don't want to carry both of those things around with me at
the same time.
So forget that we've got an extended list.
We'll bring all those back together a little later.
So we're going to forget what we just did
…
be the main highway between Chicago, Illinois and Los
Angeles, California.
Very famous highway because anybody who wanted to go
across country always took route 66 because it was the
shortest way to go.
And the question is, how do you find the shortest path?
Not just any old path or a good path, but how do you find
the very shortest path?
And that'll be the subject that we're
going to discuss today.
But route 66, I lament its passing, but it's been largely
replaced by the interstate highway system that was
created by President Eisenhower.
Guess why?
Let's see, maybe the ROTC people know.
You know why Eisenhower created the
interstate highway system?
Well, in public affairs, of course, there's always a
distinction to be made between the
explanation and the reason.
The explanation was--
AUDIENCE: To move weapons across the country?
PROFESSOR: Well, to move nuclear
weapons across the country.
Let's put it in, sightly, more benign terms.
Eisenhower had observed that the German army was able to
move its troops rapidly, even though we bombed their
railroads into oblivion because of their auto bond.
So Eisenhower conceived that if there were ever an invasion
in the United States, we too would want to be able to move
our forces around on a highway system.
And consequence of that, we have a pretty good highway
system and pretty awful railroad system.
It's interesting.
I'm a beneficiary of that, in a funny way, because I'm from
East Peoria, Illinois.
And I was surrounded by the factors of Caterpillar Tractor
Company, which made all of the tractors that built all of
those roads.
So my high school spent money like water from that huge tax
base of all those factors.
Anyway, today we want to find the very best path, instead of
just a good path.
And like the last time, we'll deal with, both, an example
that we can set our program to work on.
By the way, can you find the shortest path between S and G?
Would you like to bet your life on the shortest path
between S and G?
Probably, not.
With your eye, you can find a good path.
But you can't find the best possible path.
Today, what we're doing is probably not modeling any
obvious property of what we have inside our heads.
But being able to find the best path is part of the skill
set that anybody who's had a course artificial intelligence
would be expected to have.
So we're going to look at it, even though it's not like many
of the things we do.
A model of something that's, probably,
going on in your head.
So we're going to use, both, this example from Cambridge
and our Blackboard example.
Let's see, we have to caution ourselves.
Tanya, is search about maps?
No, it's about what?
Starts with a C. And the next letter is H. And it ends up
being choice.
So we're talking about choice.
Not about maps.
Even though our examples are drawn from maps because
they're convenient, they're visual, and helps understand
the concepts behind the algorithms I'm talking about.
So let's start off by looking at our classroom example.
And I did something today that I neglected to do last time.
And that's talk to you about what I meant
by heuristic distance.
It's those pink lines that I just drew on the map.
We're talking about the distance as the crow would fly
between two places, even though there's no road that
goes between those two places.
So in general, and we discussed last time, it's best
to get yourself into a place that's close, as the crow
flies, to your goal.
And of course, that's a heuristic and it can get you
in trouble because it's not always true.
It would appear that being at node E is a good place to be
because it's not very far from G. But in that particular case
designed to illustrate the point, being close is,
actually, not a good thing because it's a dead end.
But in general, it's a good thing to be close.
And we talked last time about hill climbing and beam search,
being close was the objective of those kinds of searches.
And at one point, in a beam search illustration, we had C,
B, A, and D. We had paths terminating at all four of
those nodes as candidates for the next round of search.
And we decided on the basis of these airline distances to
keep D and B, and reject A and C because they're further away
as the crow flies.
Now, I repeat this even though many of you have had this
fixed already in your tutorials because we're going
to need this concept of heuristic distance today.
And I wanted to be sure that that point has been clarified.
So now, with this smaller map I imagine you can do, by eye,
a determination of what the shortest path is.
What is it, Juana?
Can you help me out with that?
AUDIENCE: S, A, D, G.
PROFESSOR: S, A, D, G. And if you add up those distances,
the distance is 11 along that path that goes from S, first
to A, and then to D, and then from D to G. So Juana asserts
that that is the best path.
And we're going to treat Juana as an Oracle because we're
going to follow, in our initial attempt to understand
these algorithms, a very important
principle of problem solving.
And that is that, if you want to solve a problem, the
easiest way is, usually, ask somebody who knows the answer.
Or Google, which also, probably, knows the answer.
So in this particular case, we believe that
Juana knows the answer.
And she said that the shortest path is S,A, D, G, and its
path length is 11.
But we don't trust her because we're applying to the same
medical school and she may be trying to screw us.
[LAUGHTER]
PROFESSOR: So we're going to be very cautious about
accepting her answer until we've checked it to make sure
that she hasn't attempted to delude us.
So how do we go about doing that?
Well, one way to do that is to check to be sure that all
other possible paths that we could develop end up being,
for sure, longer than the one that Juana has told us about.
So she's told us about S, A, D, G. And it has a total path
length of 11.
And now what I'm going to do is I'm just going to develop
the rest of this tree-like diagram.
But what I'm going to do is, I'm not going to do it in a
British Museum or random way.
What I'm going to do is, I'm going to look at the choice
that corresponds the shortest path that can be extended.
So the shortest path that can be extended is
this one right here.
The one that just has the starting node in it.
And I could have gone this other way to B. And if I go
that other way to B, then the path length along
that side is 5.
And likewise, if I look at the path that terminates in A,
that has a path length of 3.
So now I've got two choices.
A and B. I've got choices that extend
beyond those two places.
So I'm always going to extend the one that
has the shorter length.
So in this case, that would be the path that goes from S to
A.
So if I from S to A, I don't have to go to D. I can also go
to B. And if I go to B, then the accumulated path length is
S, A, B. That's 7.
And know that we're talking now about the path, like the
accumulated path length, that we've traveled so far.
Last time we were talking a lot about
distances to the goal.
Heuristic estimates of how far we are from the goal.
Now we're doing exactly the opposite.
We're not considering how far we've got to go.
We're only thinking about how far we've gone so far.
So now, repeating these steps again.
I've got 7 and 5.
So I'll go over and consider the choices that go through
the B node on the path S, B. And that gives me S, B, A and
S, B, C. And what are those path lengths?
Well, let's see.
S, B, A would be 9.
And S, B,C would be 9.
And now the shortest path is this one over here.
So I extend that.
I go S, A, B. S, A, B. The only place I can go is C. That
adds another 4.
So that's 11.
And what do I know about that path?
I don't have to take that any further, right?
Because the path length, since I've gone on that path
already, is equal to the path length that Juana has told me
gets me to the goal.
So it'll be foolhardy to carry on because, presuming that
these lengths are all non-negative, I
can't do any better.
And I can't even do as well, unless I've got a length that
has 0 length.
So now that I have that idea, I can quickly finish up by
saying, well, let me consider these two paths.
S, B, A can only go to D. And if I go to D, that adds 3.
9 plus 3 is 12.
Nothing else can happen there because that's 12 and I've got
a path of a goal that's 11.
C, I can only go to E. It's a dead-end but I don't have to
think about that because I know that the accumulated
distance along this path is 6 plus 9.
That's 15.
So all of these need not be extended any further because
their length, accumulated so far, is equal to or less than
a length of a goal.
So I've checked the Oracle.
And although we're applying to the same medical school, Juana
has told me the truth.
So now, unfortunately, Juana's not always around.
And I don't always have an Oracle.
So I'm going to have to have some way of finding the
shortest path without that Oracle
that I can check against.
Let's see.
What can I do?
Maybe I can do the same thing I just did.
Always extend the shortest path so far and hope that I
run into the goal at some point.
And then I have to ask myself the question how much extra
work did I need to do when I don't have the Oracle?
Let's just try it and see what happens.
You don't have that path to start.
So I just have S. This distance is 0.
I can go either to A or B. If I go to A, I've got
a distance of 3.
Here, I've got a distance of 5.
I'll extend the path that goes S, A. That can either got to B
or D. Going to B or D gives me 7 that way.
S, A, D gives me 6.
So looking across all of these and extending the shortest
path so far takes me back over to S, B. So I extend those.
S, B takes me to A or C.
And those, in turn, have total accumulated path
lengths of 9 and 9.
Now the shortest one is S, A, D. You see the pattern.
Now let's see.
I haven't found the goal yet.
So I can ask myself the question is any of the work
that I've done so far wasted?
No because all of the paths that I've got so far are
shorter than the path of the goal because the goal
hasn't shown up.
So when I do my oracle checking after I found the
goal, none of that work's going to be wasted.
So in the end, I don't, actually, need the Oracle.
I could just develop this graph by extending the
shortest path, so far, until I hit the goal.
And then, perhaps, do a little remaining checking to make
sure that all the other paths extend with a length that's
greater than the path of the goal.
So if those words are confusing, let's carry on with
the algorithm, and I think it'll be clearer.
So let's see.
We've got the 7, 6, and two 9s.
We're going to extend the one that's 6.
That gets this to the goal.
Boom, we've got it.
And we've got a path length of 11.
Note, though, we can't quit because we have to be sure
that all other paths are longer than 11.
So now we have to carry on with the same algorithm that
we started with.
The Oracle checking algorithm.
And when we do that, we look for this shortest path, so
far, that has not been extended.
That's B, S, A, B. That goes to C. That's 11.
So we're done there.
A goes to D. That adds 3.
That's 12.
C goes to E. That adds 6.
That's 15.
And sure enough, we're done.
OK?
Elliot?
AUDIENCE: Does it know that there's know that there isn't
a chance that you could have a zero distance extension from
the [INAUDIBLE]?
PROFESSOR: The question is, does it know that there's no
zero distance length that's coming up.
That's an implementation detail.
This guarantees you'll find a path that's as short as any
that you can possibly find.
But there might be others if they're zero-length lengths.
As long as they're non-negative
lengths, we're safe.
We've got a shortest path.
So that was easy.
And now we can repeat the exercise with our more
complicated map of Cambridge.
First of all, let's do depth first just to recall what that
looks like.
That is, certainly, not a short path.
So let's try this idea, which, by the way, bares the label
branch inbound.
Let's try branch inbound on the same map.
And there it goes.
Each of those little flickers is trying another path.
So you can see it's working it's guts out to find the
shortest path.
It's almost there but it's almost a pathological case.
Or it's almost doing British Museum.
There it's finally found the shortest path.
Now there are some things we can ask about that.
But first of all, before I ask anything about it, I'd like to
get the flow chart up on the board because we're going to
decorate that flow chart, a little bit, as we go.
So the first thing we do is initialize queue.
Then we're going to test first path on the queue.
Then we might be happy because we might be done.
We might have a shortest path to the goal.
Actually, that's not quite true, is it?
We can't really quit until every other path is it.
Well, that's interesting.
If the first element on the queue gets us all the way to
the goal, and we sorted our queue by path length, are we
through as soon as that first element on the queue gets us
to the goal?
Yeah because every other path must have been
sorted beyond it.
And therefore, it can't offer us a shorter path to the goal.
So if the first path is a path to the goal we're done.
Alas, it usually isn't.
So we'll extend first path.
We're going to put all those extensions back on the queue,
and then we're going to sort them.
So that's, pretty much, the same as we did last time.
We're always going to put the elements back on the queue.
We're going to look at the first element the queue and
see if it's a winner.
If it is we're done.
If it's not, we're going to extend it.
And then go back in here and try again.
Well, sort of.
But we noted that this did a awful lot of work because if
we look at those statistics up there, it put 1,354
paths onto the queue.
That's the N queueing part.
And then it extended 835,000 paths that had come to the
front of the queue.
Now I'd like to give you an aside because it's easy to get
confused about N queueing and extending.
In all of the searches we did last time, it would have been
perfectly reasonable to keep a list of all the paths that we
had put onto the queue.
An N queueing list.
And never add a path to our queue if it terminates in a
node that some other path terminate in that has already
gone to the queue.
What I said last time was let us keep track of the things
that have been extended and not extend them again.
So you can either keep track of the nodes that have been
extended and not extend them again.
Or look at the paths with nodes that terminate, and
blah, blah, blah and been put on the queue, the queued ones.
And not put things back on the queue again.
And I think, last time, I may have put a column in there
that said N queued.
It should have been extended.
Even though N queued worked last time, only extended works
this time because we want to be sure that anything we
extend is a short path.
So the N queued idea doesn't work, at all, for these
optimal paths.
So now I want to come back over here off the side bar and
say that we're keeping track of all of the nodes, all of
the paths that end in nodes unless they have already been
extended beyond that particular place.
So we need to decorate our algorithm here and say test
first path and extend the first path
if not already extended.
Because you can see that in the example I had, so far, we
did that same silliness that we talked about last time.
We extended paths that went through A more
than once, like so.
Would it ever make sense to extend this path?
No because we've already extended a path that got there
with less distance.
Will it ever make sense to extend this path?
No because we've already extended another path that
gets to be by a shorter distance.
So if we keep an extended list, we can add that to
branch inbound to our advantage.
So let's see how that would work on the classroom example.
And then we'll do Cambridge.
So this is bridge inbound, plus an extended list.
And I do mean extended.
Not in the N queued list.
N queued list won't work here.
So let's see, I start off the same way as I did before.
S goes to either A or B. That's a length of 3.
That's a length of 5.
So I extend A. That goes to either B or D. But B is as if
it wasn't there at all.
Oh, sorry.
Hang on.
B goes there.
And those path lengths are 7 and 6.
And now I look around on the board, and I say what is the
shortest path so far?
And it's B. So I extend that to get to A and C with path
lengths of 9 and 9.
And what's the shortest one next?
It's D. And that goes to G. And the path length is 11.
And what's the shortest one on the board?
The one that has to be extended next.
That's this one that gets to B. But I've already extended a
path that get to B. So I don't,
actually, do that extension.
So I've saved some work.
But I've got to go over here and do these two now.
But wait.
I've already extended B. I've already extended A, so I don't
have to do that one either.
The only one I have to do is the one that goes to C. And
that those then to E with a path length of 15.
And I'm done.
So if you compare this one with a previous one, you can
see that there might be vast areas of this tree that are
pruned away and don't have to be examined all.
So now, just for the sake of illustrating that, I would
like to keep track of just one of those statistics.
The number of extensions.
So for this particular example, case one, the number
of extensions was 835.
Why don't you see if you can guess to yourself what it
would be if I use this concept of an extended list.
See, I'm not going to extend anything I've already extended
because it's guaranteed to have a longer path length then
something that already got to that same place.
So it makes no sense to do it.
So let me change the type to branch-and-bound with an
extended list.
I'm going to turn the speed down a little bit so
we can watch it.
It might take the rest of the hour.
Who knows?
Still doing a lot of work.
Still examining a lot of paths.
Well, look at that.
Instead of 835 extensions it only did 38.
So that's a pretty substantial savings.
And you would never not want to do that.
So note that that's a layering on top of branching out.
That's not a different algorithm.
It's an adjustment improvement to the algorithm, and it makes
it more efficient.
So this whole thing is based on what I call
the dead horse principle.
As soon as we figure out that a path that goes to a
particular place can't possibly be the winning path,
we get rid of it, and don't bother extending it.
It's a dead horse principle.
But if we look at this example, what's the shortest
possible length of a path that's already
gone from S to B?
What do you think, Tanya?
Well, first of all, it can't be less than 5 because we've
already gone that distance.
So when I say what's the shortest length of any path
that there could possibly be that goes from S to D. We know
it's at least 5.
But can we say something more about it?
Especially, when we look at these airline distances, and
note that this airline distance is 6, and that's a
little more than 7, and that's a little more than 7.
So what do you think?
So it's gone from S to B, and the question is what's the
shortest path that could possibly be that had started
out going from S to B?
11 right?
Because we can't have a path that's shorter than the
airline distance.
If there were a straight line road from A to G, its length
would be 6.
But there isn't.
So that gives us a lower bound on the distance that we have
along that path.
So we're using the accumulated distance, plus the airline
distance, to give us a lower bound on the path that we've
started off on that goes from S to B.
Once again, let's solidify a little bit by simulating the
search and seeing how it turns out.
Not just I did last time, I'm going to forget that I've got
an extended list.
I don't want to carry both of those things around with me at
the same time.
So forget that we've got an extended list.
We'll bring all those back together a little later.
So we're going to forget what we just did
…