Advertisement
English transcript
PATRICK WINSTON: Today we're going to be
talking about Search.
I know you're going to turn blue with yet
another lecture on Search.
Those of you who are taking computer science subjects,
you've probably seen in 601.
You'll see it again as theory course.
But we're going to do it for a little different purpose.
I want you to develop some intuition about various kinds
of Search work.
And I want to talk a little bit about Search as a model of
what goes on in our heads.
And toward the end, if there's time, I'd like to do a
demonstration for you of something never before
demonstrated to a 603.4 class, because it was only completed
last spring.
And some finishing touches were added by me this morning.
Always dangerous, but we'll see what happens.
There's Cambridge.
You all recognize it, of course.
You might want to get from some starting position s to
some goal position g.
So, you'll hire a cab and hope for the best.
So, here's what might happen, not too hot.
Let's move the starting position over here.
I've had cab drivers like this New York.
But it's not a very good path.
It's the path of a thief.
Let's change the way that the search is done to that of a
beginner, an honest beginner.
Not too bad.
Now, let's have a look at how the Search would happen if the
cab driver was a Ph.D. in physics
after his third post-doc.
These are not actually traverse.
These are just things that the driver is thinking about, and
that is the very best of all possible paths.
So, the thief does a horrible job.
The beginner does a pretty good job, but
not an optimal job.
This is the optimal job as produced by the Ph.D. in
physics after his third post-doc.
So, would you like to understand how those all work?
The answer, of course, is yes.
I'm going to talk to you about procedures that are different
from the way that you just solved this problem.
I imagine that if I said to you, please find a path for s
to g, you would, within a few seconds, find
a pretty good path--
not the optimal one, but a pretty good one--
using your eyes.
And we're not going to tell you about how that works,
because we don't know how that works.
But we do know that problem solving with the eyes is an
important part of our total intelligence.
And we'll never have a complete theory of human
intelligence until we can understand the contributions
of the human visual system to solving everyday problems like
finding a pretty good path in that map.
But, alas, we can't talk about that, because we don't know
how to do it.
We're working on it.
But we don't know how to do it.
So, I'm not going to use Cambridge in my illustrations.
There's too much there to work through in an hour.
So, we're going to use this map over here which has been
designed to illustrate a few important points.
You, too, can find a path through that graph pretty
easily with your eyes.
Our programs don't have eyes, and they don't have visually
grounded algorithms, so they're going to have to do
something else.
And the very first kind of search we want to talk about
is called the British Museum approach.
This is a slur against at least the British Museum, if
not the entire nation, because the way you do a British
Museum search is you find every possible path.
So, it'll be helpful to have a diagram of all possible paths
on the board.
We're going to start with a British Museum search.
From the starting position, it's clear, you can go from my
s to either a or b.
And already there's an important quiz point.
Whenever we have these kinds of problems on a quiz, we ask
you to develop the tree associated with a search in
lexical order.
So, the nodes there under s are listed alphabetically,
just to have an orderly way of doing it.
So, from a we can go either b or d.
And another convention of the subject, another thing you
have to keep in mind in quizzes, is it we don't have
these searches bite their own tail.
So, I could have said that if I'm at a, I can
also go back to s.
But no path is ever allowed them to bite itself, to go
around and enter and get back to a place that's
already on the path.
Now if I go on to b first, that means that from b I can
go to either a or c.
This is getting fat pretty fast.
But let's see, s, a, b.
The only place I can go is c and then to e.
s, a, d, without biting my own tail and going back to a, the
only place I can go is g.
s b, a, I can only go to d and then to g.
And finally, s, b, c, I can only go to e.
So, that is a complete set of paths as produced by any
program that you will feel you'd like to write that finds
all possible paths.
I haven't been very precise about how to do that, because
you don't have to be.
You can't save much work by being clever, because you have
to find everything.
So, that's the British Museum expansion of the tree.
So, what have I done?
I've been playing around with a map.
I showed you an example of a map.
And pretty soon you're going to think that
Search is about maps.
So, before going even another tiny step, I want to emphasize
that Search is not equal to maps.
Search is about choice.
And I happen to illustrate these searches with maps,
because they are particularly cogent.
But Search is not about maps.
It's about the choices you make when you're trying to
make decisions.
These things I'm going to be talking to you about today are
choices you make when you explore the map.
You can make other kinds of choices when you're exploring
other kinds of things.
And, in fact, at the end, if there's time, I'll show you
how you do searches when you're solving problems in a
humanities class.
That's the British Museum algorithm.
Search is not about maps.
Our first gold star idea, Search is about choice.
But for our illustration, Search is about maps.
So, the first kind of Search we want to talk about that's
real is Depth-first Search.
And the idea of Depth-first Search is that you barrel
ahead in a single-minded way.
So, from s, your choices are a or b.
And you always go down the left branch by convention.
So, from s, we go to a.
From a we have two choices.
We can go to either b or d following our lexical
convention.
After that, we can go to c.
And after that we can go to e.
And too bad for us, we're stuck.
What are we going to do.
We've got into a dead end, all is lost.
But of course, all isn't lost.
Because we have the choice of backing up to the place where
we last made a decision and choosing another branch.
So, that process is called variously back-up or
backtracking.
At this point, we would say, ah, dead end.
The first place we find when we back up the tree where we
made a choice is when we chose b instead of d.
So, we go back up there and take the other route.
s, a, d now goes to g.
And we're done.
We're going to make up a little table here of things
that we can embellish our basic searches with.
And one of the things we can embellish our basic searches
with is this backtracking idea.
Now, backtrack is not relevant to the British Museum
algorithm, because you've got to find everything.
You can't quit when you've found one path.
But you'd always want to use backtracking with Depth-first
Search, because you may plunge on down and miss the path that
gets to the goal.
Now, you might ask me, is backtracking, therefore,
always part of Depth-first Search?
And you can read textbooks that do it either way.
Count on it.
If we give you a Search problem on a quiz, we'll tell
you whether or not your Search is supposed to use
backtracking.
We consider it to be an optional thing.
You'd be pretty stupid not to use this optional thing when
you're doing Depth-first Search.
But we'll separate these ideas out and call
it an optional add-on.
so, that's Depth-first Search, very simple.
Now, the natural companion to Depth-first Search will be
Breadth-first Search, Breadth-first.
And the way it works is you build up this tree level by
level, and at some point, when you scan across a level,
you'll find that you've completed a path
that goes to the goal.
So, level by level, s can go to either a or b.
a can go either to b or d.
And b can go to either a or c.
So, you see what we're doing.
We're going level by level.
And we haven't hit a level with a goal in it yet, so
we've got to keep going.
Note that we're building up quite a bit of stuff here,
quite a lot of growth in the size of the path set that
we're keeping in mind.
At the next level, we have b going to c, d going to g, a
going to d, and c going to e.
And now, when we scan across, we do hit g.
So, we found a path with Breadth-first Search, just as
we found a path with Depth-first Search.
Now, you might say, well, why didn't you just quit
when you hit g?
Implementation detail.
We'll talk about a sample implementation.
You can write it in any way you want.
But now that we know what these searches are, let's
speed things up a little bit here and do a couple searches
that now have names.
The first type will be Depth-first, boom.
That's the one that produces the thief path.
And then we can also do a Breadth-first Search, which we
haven't tried yet.
What do you suppose is going to happen?
Is it going to be fast, slow, produce a good path,
produce a bad path?
I don't know, let's try it.
I had to speed it up, you see, because it's doing an awful
lot of Search.
It's generating an awful lot of paths.
Finally, you got a path.
Is it the best path?
I don't think so.
But we're not going to talk about optimal paths today.
We're just going to talk about pretty good
paths, heuristic paths.
Let's move the starting position here in the middle.
Do you think Breadth-first Search is going to be stupid?
I think it's going to be pretty stupid.
Let's see what happens.
This Search is a lot to the left, which you would never do
with you eye.
Let me slow that down just to demonstrate it.
It finds a shorter path, because it's right there in
the middle.
But it spends a lot of its time looking off to the left.
It's pretty stupid.
But that's how it works.
So, now that we've got two examples of searches on the
table, I'd like to just write a little flow chart for how
the search might work.
Because if I do that, then it'll be easier for us to see
what kind of small differences there are between the
implementations of these various searches.
So, what we're going to do is we're going to develop a
waiting list, a queue, a line, whatever you'd
like to call it.
Let's call if a queue.
We're going to develop a queue of paths that are under
consideration.
So, the first step in our algorithm will be to
initialize our queue.
And I think what I'll do is I'll simulate Depth-first
Search on this problem up there on the
left using this algorithm.
I need to have some way of representing my paths.
And what I want to do is I'm going to betray my heritage as
a list programmer, because I'm just going to put these up as
if there were lisp s-expressions.
To begin with, I just have one path.
And it has only one node in it, s.
That's the whole path.
The next thing I do after I initialize the queue is I
extend first path on the queue.
OK, when I extend s, I get two paths.
I get s goes to a, and I get s goes to b.
I take the first one off the front of the queue.
And I put back the two that are produced by
extending that path.
Now, after I've extended the first path on the queue, I
have to but those extended paths on to the queue.
In here there's an explicit step where I've checked to see
if that first path is a winner.
If it's not, I extend it.
And I have to put those paths onto the queue.
So, I'll say that what I do is I end queue.
Now, I've done one step.
And let's let me do another step.
I'm going to take this first path off.
I'm going to extend that path.
And where do I put these new paths on the queue if I'm
doing Depth-first Search?
Well, I want to work with the path that I've just generated.
I'm taking this plunge down deep into the search tree.
So, since I want to keep going down into the stuff that I
just generated, where then do I want to put these two paths?
At the end of the queue?
I don't think so, because it'll be a long
time getting there.
I want to put them on the front of the queue.
For Depth-first Search, I want to put them on the
front of the queue.
And that's why s, a, b goes here, and s, a, d, and then
that's s, b.
So, s, b is still there.
That's still a valid possibility.
But now I've stuck two paths in front of it, both of the
ones I generated by taking a path off the front of the
queue, discovering that it doesn't go to the goal,
extending it and putting those back on the queue.
I might as well complete this illustration here.
While I'm at it, I take the s, a, b off, s, a, b, and I can
go only there to c.
But, of course, I keep s, a, d and s, b on the queue.
Now, I take the front off the queue again, and I get s, a,
b, c, e, and not to forget s, a, d and s, b.
I take the first one off the queue.
It doesn't go to the goal.
I try to extend it, but there's nothing there.
I've reached a dead end.
So, in this operation, all I'm doing is taking the front one
off the queue and shortening the queue.
We're almost home.
I take s, a,d off of queue.
And I get s, a, d, c.
And, of course, I still have s, b.
Now, the next time I visit the situation, buried in that
first step, I discover a path that actually does get to
goal, and I'm done.
So, each time around I visualize the queue.
I check to see if I'm done.
If not, I take the extensions and put them
somewhere on the queue.
And then I go back in.
And then here there's a varied test which checks to see if
we're done.
That's how the Depth-first Search algorithm works.
And now, would we have to start all over again if we did
Breadth-first Search?
Nope.
Same algorithm.
All the code we've got needs one line
replaced, one line changed.
What do I have to do different in order to get a
Breadth-first Search out of this instead of
a Depth-first Search?
Tanya?
TANYA: Change [INAUDIBLE] on the queue.
PATRICK WINSTON: And where do I put it on the queue?
She says to change it.
TANYA: On the back?
PATRICK WINSTON: Put it on the back.
So, with Breadth-first Search all I have to do
is put on the back.
Now, if we were content with a inefficient search, and didn't
care much about how good our path was, we'd be done.
And we could go home.
But we are a little concerned about the
efficiency of our search.
And we would like a pretty good path.
So, we're going to have to stick around
for a little while.
Now, you may have noticed, up there in that the development
of the Breadth-first Search, that the algorithm is
incredibly stupid.
Why is the algorithm incredibly stupid?
Ty, what do you think?
TY: It can't tell whether it's getting closer or further away
from the goal.
PATRICK WINSTON: It certainly can't tell whether it's
getting closer or further away from the goal.
And we're going to deal with that in a minute.
But it's even stupider than that.
Why is it stupid?
What's your name?
DYLAN: Dylan.
It [? hits ?] the same nodes twice.
PATRICK WINSTON: Dylan said it's extending paths that go
to the same node more than once.
Let's see what Dylan's talking about.
Down here, it extends a.
But it's already extended a up there.
Down here, it extends a path that goes to b.
And it's already extended a path that goes to d.
Over here, it could extend a path that went through c, but
it's already got a path that goes through c.
So, all of these paths are duplicated.
And we're still going through them.
That's incredibly stupid.
What we're going to do is we're going to amend our
algorithm just a little bit.
And we're not going to extend the first path on the queue
unless final node never before extended.
What we're going to do is we're going to look to see if
there-- we've got this path.
And we're going to extend it.
And it's got a final note.
If we've ever extended a path that goes to that final node,
and it was a final node on that path, then we're not
going to do it again.
We got to keep a list of places that have already been
the last piece of a path that was extended.
Everybody got that?
It's a little awkward to say it, because it's the last node
we care about.
If a path terminates in a node, and if some other path
previously terminated in that node and got extended--
we're not going to do it again.
Because it's a waste of time.
Now, let's see if this actually helps.
Now, use the extended list.
Let's see, well, gee, we got that place
in the center there.
Let's just repeat the previous search.
Wow, it's taking a long time.
But notice it put 103 paths back on the queue.
Now, let's add a filter and try again.
A lot less.
So, let's speed this up, and we'll start way over here.
You remember how tedious that search was.
And now we'll repeat it with this list, boom, there it is.
That's all because we didn't do that silly thing of going
back through the final node that's
already been gone through.
So, you would never not want to do this.
We better list this as another option.
It doesn't help with a British Museum algorithm, because
nothing helps with the British Museum algorithm.
Does it help with Depth-first?
Yes.
Does it help with Breadth-first?
Yes.
Do we do backtracking with Breadth-first?
No, because backtracking can't do us any good.
OK, we're almost, except that search that's starting in the
middle is still pretty stupid.
Both the Breadth-first version and the Depth-first version
are going off to the left.
And we would never do that with our eyes in any case.
The next thing we want to do is we want to have ourselves a
slightly more informed search by taking into consideration
whether we seem to be getting anywhere.
So, in general, it's a good thing to get closer to where
we want to go.
In general, if we've got a choice of going to a node
that's close to the goal or a node that's not so close to
the goal, we'll always want to go to the one that's
close to the goal.
And as soon as we add that to what we're doing, we have
another kind of Search, which goes by the
name of Hill Climbing.
And it's just like Depth-first Search, except instead of
using lexical order to break ties, we're going to break
ties according to which node is closer to the goal.
I went to some trouble to talk to you about
this enqueued list.
And having gone to that trouble, I'm now
going to ignore it.
Not because it isn't a good idea, but because trying to
keep track of everything in the example is
confusing the example.
It won't work out right in the small example and all that.
Put the queueing thing aside, queued list aside, and think
instead just about the value of going in the direction
that's getting us closer to the goal.
In Hill Climbing Search, just like a Depth-first Search, we
have a and b.
And we're still going to list them lexically on underneath
the parent node.
But now which one is so closer to the goal?
Now, this time b is closer to the goal than a.
So, instead of following the Depth-first course, which
would take us down through a, we're going to go to the one
that's closest which goes through b.
And b can either go to a or c.
b is six units away from the goal. a is about seven plus,
not drawn exactly to scale.
Use the numbers not your eyes.
Now where are we?
It's symmetric, so a and c are both equally
far from the goal.
Now we're going to use the lexical order
to break the tie.
Now from s, b, a, we'll go to d.
And now, which is closest to the goal?
That's the only choice we have.
So, now we have no choice but to go down to the goal.
That's the Hill Climbing way of doing the search.
And notice that this time there's no backtracking.
It's not the optimal path.
It's not the best path.
But at least there's no backtracking.
That's not always true.
That's just an artifact of this particular example.
Do you think Hill Climbing would produce a faster search?
I think so.
Let's see what happens when we add these
things at one at a time.
First, let's turn off our extended list.
We turned off our extended list.
And we're going to do Depth-first again just for the
sake of comparison.
It produces a very roundabout path with 48 enqueueings.
Now, let's switch over to Hill Climbing.
And what do think?
Do you t
…
talking about Search.
I know you're going to turn blue with yet
another lecture on Search.
Those of you who are taking computer science subjects,
you've probably seen in 601.
You'll see it again as theory course.
But we're going to do it for a little different purpose.
I want you to develop some intuition about various kinds
of Search work.
And I want to talk a little bit about Search as a model of
what goes on in our heads.
And toward the end, if there's time, I'd like to do a
demonstration for you of something never before
demonstrated to a 603.4 class, because it was only completed
last spring.
And some finishing touches were added by me this morning.
Always dangerous, but we'll see what happens.
There's Cambridge.
You all recognize it, of course.
You might want to get from some starting position s to
some goal position g.
So, you'll hire a cab and hope for the best.
So, here's what might happen, not too hot.
Let's move the starting position over here.
I've had cab drivers like this New York.
But it's not a very good path.
It's the path of a thief.
Let's change the way that the search is done to that of a
beginner, an honest beginner.
Not too bad.
Now, let's have a look at how the Search would happen if the
cab driver was a Ph.D. in physics
after his third post-doc.
These are not actually traverse.
These are just things that the driver is thinking about, and
that is the very best of all possible paths.
So, the thief does a horrible job.
The beginner does a pretty good job, but
not an optimal job.
This is the optimal job as produced by the Ph.D. in
physics after his third post-doc.
So, would you like to understand how those all work?
The answer, of course, is yes.
I'm going to talk to you about procedures that are different
from the way that you just solved this problem.
I imagine that if I said to you, please find a path for s
to g, you would, within a few seconds, find
a pretty good path--
not the optimal one, but a pretty good one--
using your eyes.
And we're not going to tell you about how that works,
because we don't know how that works.
But we do know that problem solving with the eyes is an
important part of our total intelligence.
And we'll never have a complete theory of human
intelligence until we can understand the contributions
of the human visual system to solving everyday problems like
finding a pretty good path in that map.
But, alas, we can't talk about that, because we don't know
how to do it.
We're working on it.
But we don't know how to do it.
So, I'm not going to use Cambridge in my illustrations.
There's too much there to work through in an hour.
So, we're going to use this map over here which has been
designed to illustrate a few important points.
You, too, can find a path through that graph pretty
easily with your eyes.
Our programs don't have eyes, and they don't have visually
grounded algorithms, so they're going to have to do
something else.
And the very first kind of search we want to talk about
is called the British Museum approach.
This is a slur against at least the British Museum, if
not the entire nation, because the way you do a British
Museum search is you find every possible path.
So, it'll be helpful to have a diagram of all possible paths
on the board.
We're going to start with a British Museum search.
From the starting position, it's clear, you can go from my
s to either a or b.
And already there's an important quiz point.
Whenever we have these kinds of problems on a quiz, we ask
you to develop the tree associated with a search in
lexical order.
So, the nodes there under s are listed alphabetically,
just to have an orderly way of doing it.
So, from a we can go either b or d.
And another convention of the subject, another thing you
have to keep in mind in quizzes, is it we don't have
these searches bite their own tail.
So, I could have said that if I'm at a, I can
also go back to s.
But no path is ever allowed them to bite itself, to go
around and enter and get back to a place that's
already on the path.
Now if I go on to b first, that means that from b I can
go to either a or c.
This is getting fat pretty fast.
But let's see, s, a, b.
The only place I can go is c and then to e.
s, a, d, without biting my own tail and going back to a, the
only place I can go is g.
s b, a, I can only go to d and then to g.
And finally, s, b, c, I can only go to e.
So, that is a complete set of paths as produced by any
program that you will feel you'd like to write that finds
all possible paths.
I haven't been very precise about how to do that, because
you don't have to be.
You can't save much work by being clever, because you have
to find everything.
So, that's the British Museum expansion of the tree.
So, what have I done?
I've been playing around with a map.
I showed you an example of a map.
And pretty soon you're going to think that
Search is about maps.
So, before going even another tiny step, I want to emphasize
that Search is not equal to maps.
Search is about choice.
And I happen to illustrate these searches with maps,
because they are particularly cogent.
But Search is not about maps.
It's about the choices you make when you're trying to
make decisions.
These things I'm going to be talking to you about today are
choices you make when you explore the map.
You can make other kinds of choices when you're exploring
other kinds of things.
And, in fact, at the end, if there's time, I'll show you
how you do searches when you're solving problems in a
humanities class.
That's the British Museum algorithm.
Search is not about maps.
Our first gold star idea, Search is about choice.
But for our illustration, Search is about maps.
So, the first kind of Search we want to talk about that's
real is Depth-first Search.
And the idea of Depth-first Search is that you barrel
ahead in a single-minded way.
So, from s, your choices are a or b.
And you always go down the left branch by convention.
So, from s, we go to a.
From a we have two choices.
We can go to either b or d following our lexical
convention.
After that, we can go to c.
And after that we can go to e.
And too bad for us, we're stuck.
What are we going to do.
We've got into a dead end, all is lost.
But of course, all isn't lost.
Because we have the choice of backing up to the place where
we last made a decision and choosing another branch.
So, that process is called variously back-up or
backtracking.
At this point, we would say, ah, dead end.
The first place we find when we back up the tree where we
made a choice is when we chose b instead of d.
So, we go back up there and take the other route.
s, a, d now goes to g.
And we're done.
We're going to make up a little table here of things
that we can embellish our basic searches with.
And one of the things we can embellish our basic searches
with is this backtracking idea.
Now, backtrack is not relevant to the British Museum
algorithm, because you've got to find everything.
You can't quit when you've found one path.
But you'd always want to use backtracking with Depth-first
Search, because you may plunge on down and miss the path that
gets to the goal.
Now, you might ask me, is backtracking, therefore,
always part of Depth-first Search?
And you can read textbooks that do it either way.
Count on it.
If we give you a Search problem on a quiz, we'll tell
you whether or not your Search is supposed to use
backtracking.
We consider it to be an optional thing.
You'd be pretty stupid not to use this optional thing when
you're doing Depth-first Search.
But we'll separate these ideas out and call
it an optional add-on.
so, that's Depth-first Search, very simple.
Now, the natural companion to Depth-first Search will be
Breadth-first Search, Breadth-first.
And the way it works is you build up this tree level by
level, and at some point, when you scan across a level,
you'll find that you've completed a path
that goes to the goal.
So, level by level, s can go to either a or b.
a can go either to b or d.
And b can go to either a or c.
So, you see what we're doing.
We're going level by level.
And we haven't hit a level with a goal in it yet, so
we've got to keep going.
Note that we're building up quite a bit of stuff here,
quite a lot of growth in the size of the path set that
we're keeping in mind.
At the next level, we have b going to c, d going to g, a
going to d, and c going to e.
And now, when we scan across, we do hit g.
So, we found a path with Breadth-first Search, just as
we found a path with Depth-first Search.
Now, you might say, well, why didn't you just quit
when you hit g?
Implementation detail.
We'll talk about a sample implementation.
You can write it in any way you want.
But now that we know what these searches are, let's
speed things up a little bit here and do a couple searches
that now have names.
The first type will be Depth-first, boom.
That's the one that produces the thief path.
And then we can also do a Breadth-first Search, which we
haven't tried yet.
What do you suppose is going to happen?
Is it going to be fast, slow, produce a good path,
produce a bad path?
I don't know, let's try it.
I had to speed it up, you see, because it's doing an awful
lot of Search.
It's generating an awful lot of paths.
Finally, you got a path.
Is it the best path?
I don't think so.
But we're not going to talk about optimal paths today.
We're just going to talk about pretty good
paths, heuristic paths.
Let's move the starting position here in the middle.
Do you think Breadth-first Search is going to be stupid?
I think it's going to be pretty stupid.
Let's see what happens.
This Search is a lot to the left, which you would never do
with you eye.
Let me slow that down just to demonstrate it.
It finds a shorter path, because it's right there in
the middle.
But it spends a lot of its time looking off to the left.
It's pretty stupid.
But that's how it works.
So, now that we've got two examples of searches on the
table, I'd like to just write a little flow chart for how
the search might work.
Because if I do that, then it'll be easier for us to see
what kind of small differences there are between the
implementations of these various searches.
So, what we're going to do is we're going to develop a
waiting list, a queue, a line, whatever you'd
like to call it.
Let's call if a queue.
We're going to develop a queue of paths that are under
consideration.
So, the first step in our algorithm will be to
initialize our queue.
And I think what I'll do is I'll simulate Depth-first
Search on this problem up there on the
left using this algorithm.
I need to have some way of representing my paths.
And what I want to do is I'm going to betray my heritage as
a list programmer, because I'm just going to put these up as
if there were lisp s-expressions.
To begin with, I just have one path.
And it has only one node in it, s.
That's the whole path.
The next thing I do after I initialize the queue is I
extend first path on the queue.
OK, when I extend s, I get two paths.
I get s goes to a, and I get s goes to b.
I take the first one off the front of the queue.
And I put back the two that are produced by
extending that path.
Now, after I've extended the first path on the queue, I
have to but those extended paths on to the queue.
In here there's an explicit step where I've checked to see
if that first path is a winner.
If it's not, I extend it.
And I have to put those paths onto the queue.
So, I'll say that what I do is I end queue.
Now, I've done one step.
And let's let me do another step.
I'm going to take this first path off.
I'm going to extend that path.
And where do I put these new paths on the queue if I'm
doing Depth-first Search?
Well, I want to work with the path that I've just generated.
I'm taking this plunge down deep into the search tree.
So, since I want to keep going down into the stuff that I
just generated, where then do I want to put these two paths?
At the end of the queue?
I don't think so, because it'll be a long
time getting there.
I want to put them on the front of the queue.
For Depth-first Search, I want to put them on the
front of the queue.
And that's why s, a, b goes here, and s, a, d, and then
that's s, b.
So, s, b is still there.
That's still a valid possibility.
But now I've stuck two paths in front of it, both of the
ones I generated by taking a path off the front of the
queue, discovering that it doesn't go to the goal,
extending it and putting those back on the queue.
I might as well complete this illustration here.
While I'm at it, I take the s, a, b off, s, a, b, and I can
go only there to c.
But, of course, I keep s, a, d and s, b on the queue.
Now, I take the front off the queue again, and I get s, a,
b, c, e, and not to forget s, a, d and s, b.
I take the first one off the queue.
It doesn't go to the goal.
I try to extend it, but there's nothing there.
I've reached a dead end.
So, in this operation, all I'm doing is taking the front one
off the queue and shortening the queue.
We're almost home.
I take s, a,d off of queue.
And I get s, a, d, c.
And, of course, I still have s, b.
Now, the next time I visit the situation, buried in that
first step, I discover a path that actually does get to
goal, and I'm done.
So, each time around I visualize the queue.
I check to see if I'm done.
If not, I take the extensions and put them
somewhere on the queue.
And then I go back in.
And then here there's a varied test which checks to see if
we're done.
That's how the Depth-first Search algorithm works.
And now, would we have to start all over again if we did
Breadth-first Search?
Nope.
Same algorithm.
All the code we've got needs one line
replaced, one line changed.
What do I have to do different in order to get a
Breadth-first Search out of this instead of
a Depth-first Search?
Tanya?
TANYA: Change [INAUDIBLE] on the queue.
PATRICK WINSTON: And where do I put it on the queue?
She says to change it.
TANYA: On the back?
PATRICK WINSTON: Put it on the back.
So, with Breadth-first Search all I have to do
is put on the back.
Now, if we were content with a inefficient search, and didn't
care much about how good our path was, we'd be done.
And we could go home.
But we are a little concerned about the
efficiency of our search.
And we would like a pretty good path.
So, we're going to have to stick around
for a little while.
Now, you may have noticed, up there in that the development
of the Breadth-first Search, that the algorithm is
incredibly stupid.
Why is the algorithm incredibly stupid?
Ty, what do you think?
TY: It can't tell whether it's getting closer or further away
from the goal.
PATRICK WINSTON: It certainly can't tell whether it's
getting closer or further away from the goal.
And we're going to deal with that in a minute.
But it's even stupider than that.
Why is it stupid?
What's your name?
DYLAN: Dylan.
It [? hits ?] the same nodes twice.
PATRICK WINSTON: Dylan said it's extending paths that go
to the same node more than once.
Let's see what Dylan's talking about.
Down here, it extends a.
But it's already extended a up there.
Down here, it extends a path that goes to b.
And it's already extended a path that goes to d.
Over here, it could extend a path that went through c, but
it's already got a path that goes through c.
So, all of these paths are duplicated.
And we're still going through them.
That's incredibly stupid.
What we're going to do is we're going to amend our
algorithm just a little bit.
And we're not going to extend the first path on the queue
unless final node never before extended.
What we're going to do is we're going to look to see if
there-- we've got this path.
And we're going to extend it.
And it's got a final note.
If we've ever extended a path that goes to that final node,
and it was a final node on that path, then we're not
going to do it again.
We got to keep a list of places that have already been
the last piece of a path that was extended.
Everybody got that?
It's a little awkward to say it, because it's the last node
we care about.
If a path terminates in a node, and if some other path
previously terminated in that node and got extended--
we're not going to do it again.
Because it's a waste of time.
Now, let's see if this actually helps.
Now, use the extended list.
Let's see, well, gee, we got that place
in the center there.
Let's just repeat the previous search.
Wow, it's taking a long time.
But notice it put 103 paths back on the queue.
Now, let's add a filter and try again.
A lot less.
So, let's speed this up, and we'll start way over here.
You remember how tedious that search was.
And now we'll repeat it with this list, boom, there it is.
That's all because we didn't do that silly thing of going
back through the final node that's
already been gone through.
So, you would never not want to do this.
We better list this as another option.
It doesn't help with a British Museum algorithm, because
nothing helps with the British Museum algorithm.
Does it help with Depth-first?
Yes.
Does it help with Breadth-first?
Yes.
Do we do backtracking with Breadth-first?
No, because backtracking can't do us any good.
OK, we're almost, except that search that's starting in the
middle is still pretty stupid.
Both the Breadth-first version and the Depth-first version
are going off to the left.
And we would never do that with our eyes in any case.
The next thing we want to do is we want to have ourselves a
slightly more informed search by taking into consideration
whether we seem to be getting anywhere.
So, in general, it's a good thing to get closer to where
we want to go.
In general, if we've got a choice of going to a node
that's close to the goal or a node that's not so close to
the goal, we'll always want to go to the one that's
close to the goal.
And as soon as we add that to what we're doing, we have
another kind of Search, which goes by the
name of Hill Climbing.
And it's just like Depth-first Search, except instead of
using lexical order to break ties, we're going to break
ties according to which node is closer to the goal.
I went to some trouble to talk to you about
this enqueued list.
And having gone to that trouble, I'm now
going to ignore it.
Not because it isn't a good idea, but because trying to
keep track of everything in the example is
confusing the example.
It won't work out right in the small example and all that.
Put the queueing thing aside, queued list aside, and think
instead just about the value of going in the direction
that's getting us closer to the goal.
In Hill Climbing Search, just like a Depth-first Search, we
have a and b.
And we're still going to list them lexically on underneath
the parent node.
But now which one is so closer to the goal?
Now, this time b is closer to the goal than a.
So, instead of following the Depth-first course, which
would take us down through a, we're going to go to the one
that's closest which goes through b.
And b can either go to a or c.
b is six units away from the goal. a is about seven plus,
not drawn exactly to scale.
Use the numbers not your eyes.
Now where are we?
It's symmetric, so a and c are both equally
far from the goal.
Now we're going to use the lexical order
to break the tie.
Now from s, b, a, we'll go to d.
And now, which is closest to the goal?
That's the only choice we have.
So, now we have no choice but to go down to the goal.
That's the Hill Climbing way of doing the search.
And notice that this time there's no backtracking.
It's not the optimal path.
It's not the best path.
But at least there's no backtracking.
That's not always true.
That's just an artifact of this particular example.
Do you think Hill Climbing would produce a faster search?
I think so.
Let's see what happens when we add these
things at one at a time.
First, let's turn off our extended list.
We turned off our extended list.
And we're going to do Depth-first again just for the
sake of comparison.
It produces a very roundabout path with 48 enqueueings.
Now, let's switch over to Hill Climbing.
And what do think?
Do you t
…