YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 1,297 lines · added Nov 18, 2015

Report a problem
What's wrong?
Advertisement

English transcript

The following content is provided under a Creative
Commons license.
Your support will help MIT OpenCourseWare
continue to offer high quality educational resources for free.
To make a donation or view additional materials
from hundreds of MIT courses, visit MIT OpenCourseWare
at ocw.mit.edu.
PROFESSOR: This week's problem is from the 2008 quiz
one on search.
It is motivated by the search of evil overlord, Mark Vader, who
is shopping for a new evil stronghold.
He starts from his current stronghold,
which is S, the Depth-First Search Star.
Now the Depth-First Search Star has the following qualities.
It has a small, thermal Exhaust Pipe Weakness.
It has the quality of That's No Moon,
but it does not have a Race of Enslaved Minions,
or a Secret Escape Route, or Sharks with Laser Beams.
Now when I originally wrote this problem in 2008,
there was another quality that very important.
It was a giant Laser, and it did have that property, as did
Dr. Evil's Moon Base, but that was removed
to make it easier to solve.
So we're going to solve it without the giant laser,
that we can just have the Sharks with Laser Beams.
So Mark Vader has gone to Ackbar's Emporium of New Evil
Strongholds, which are listed on the left,
and he's trying to figure out the best
way to get from his current stronghold
to his goal stronghold, the 603 Fortress, which
has the admirable qualities of no small thermal Exhaust Pipe
Weakness, and it still has That's No Moon.
It has a Race of Enslaved Minions,
and a Secret Escape Route, and Sharks with Laser Beams.
So it's got everything you would want and no weakness.
However, he can only move between fortresses that
have exactly one difference.
Fortunately, Mark remembers how to perform the search
techniques he learned in 6.034 from his mentor, Emperor
Palpatine.
So we've got several fortresses here.
We've got the Depth-First Search Star.
We've also got Shaoul Ghoul, which
has the qualities, basically, of That's
No Moon, and none of the other qualities.
Dol Guldur here, has got the Exhaust Pipe Weakness somehow,
despite being Sauron's stronghold.
It's not a moon, and it has those enslaved minions.
I guess the Orcs are enslaved.
Moonraker, here, only has the Exhaust Pipe Weakness,
so it's not very good.
But James Bond didn't need to deal with stuff.
Zeal Underwater Palace has That's
No Moon and a Secret Escape Route.
Zeromus' Lunar Core has an Exhaust Pipe Weakness
and a Race of Enslaved Minions.
Whalers of the Moon Ride has the Exhaust Pipe Weakness,
Race of Enslaved Minions, and Sharks with Laser Beams.
6.03 Fortress we've already been over.
Atlantis has all qualities except for a Secret Escape
Route.
Willy Wonka's Factory has some of everything.
It is, after all, Willy Wonka's Factory.
Highlight, the Race of Enslaved Minions, the Oompa Loompas.
And Dr. Evil's Moon Base is only missing
That's No Moon, because it is a moon, because it's a moon base.
So if you got all the references that
were used in making those fortresses, I'm sorry.
There's nothing I can do for you.
Now, Mark, being a clever evil overlord,
realizes that he can produce a graph of the exploration
choices with edges joining strongholds that
differ by just one feature.
So although this is a graph here,
as Patrick often says-- and you get to hear again right now--
search is about choice, not just about maps.
So we're not moving around anywhere in the real world,
but we certainly are going to move around
this graph to pick between these many stronghold choices.
How can we decide where to travel?
Well, we're about to find out.
So we've got this lovely graph right here,
and now we're going to get to do depth-first search
on the graph.
Now there's a lot of ways to do search,
and you've seen Patrick do it, you
may have seen some people do it in recitation.
And I'm going to offer you guys a unique opportunity to see me
do search in one of several ways, or possibly more.
I have the tried and true method.
You have the queue, or agenda, or whatever
you want to call it.
You keep track of it at every level.
You make damn sure that everything you're doing
is right.
It takes a long time, and you get the answer right.
Or there's one where you only work with the goal tree,
and you draw it really fast, and you might make a mistake,
but it's going to solve it more quickly.
So who would rather see the reliable, but slower, approach?
Who would rather see the faster, but less reliable, approach?
All right.
Monte Carlo people here, rather than Las Vegas.
If you don't know what that is, you'll
learn it in algorithms class.
All right.
Then there's a third approach that I probably
won't show you unless there's overwhelming favor for it.
That is the approach that is manically fast
and will solve depth-first search in no time at all,
but it is very likely to make mistakes.
That is the approach that I use when
solving depth-first search.
I've used it enough times that I don't make mistakes that often,
but even I still do.
So does anyone want to see that one?
OK.
Not that many people.
Well, it doesn't take much time, but I'm
just afraid that if I show it you, that you'll be like, ooh,
that's the only way to do it.
So we'll save that for later if we have more time.
It essentially, for people that are interested,
involves just using your chalk or finger
to trace through the tree really fast
and figure out what it's doing by drawing little tiny lines.
It is very fast, but it's not very accurate.
And you have shown, basically, no work if you get it wrong,
so shame on you.
OK.
Well, let's do the somewhat faster way
where we don't draw out the entire agenda,
and then people who were the almost nobody who
raised their hand for that way can check it out
in tutorial the way that you do it using the agenda.
So let's do it using the goal tree.
So it's a bit faster that way.
So we're going to start, starting at S, the start node,
and going to G, the goal node.
That's a standard notation, but make sure
that when you're taking the test,
you check to make sure where the start node is,
where the goal node is.
It's pretty much an asshole move to have
a G node that isn't the goal node,
but sometimes there won't be an S node.
That's a pretty good clue that something else
is the start node.
Now there's a few little white star ideas that we have,
or silver star ideas, for search.
One is lexicography.
What it lexicography?
Who cares?
Well, the most famous lexicographer I know of
is Samuel Johnson, who wrote a really famous dictionary.
And the only reason we care about it in this class
is because you'll always see the instructions "break
ties in lexicographic order."
And then you might be like, wow, that's
really rather a wordy word, or a sesquipedalion word,
or whatever really long word you want to use to describe
the word "lexicographic."
What the heck does it mean?
Basically, it means alphabetical order,
like you would do in a dictionary.
So for instance, in alphabetical order, A comes before B.
So you would go to A before B. No, even beyond that point,
there's several ways to do a lexicographic tiebreak.
And it's not always consistent between algorithms
how you would do a lexicographic tiebreaker.
In the most recent time that Patrick
was kind of randomly talking to the staff,
he made it clear that the way he would like us to do it,
and therefore, the way we'd like you to do it,
is to tiebreak based on the very latest nodes at the end.
So you might say, that's not really lexicographic.
Wouldn't SAB come before SGA in the dictionary?
And my answer to you is, yes, it would.
Yes, yes, it definitely would.
However, that is apparently what we're
doing, according to the last thing that Patrick said,
and we will keep you updated if he decides
to go back to dictionary order.
So that's lexicography.
You might be wondering what the picture here is.
Well, this is our friend, the ouroboros.
Long has it been a symbol in alchemy
of infinity, eternity, or maybe a sort of infinite energy
engine, turning iron into gold.
But today, unfortunately, the ouroboros
is an endangered species because no biting your own tail
in 6.034.
A lot of people mess up from this.
It's an honest mistake.
I mean, we've gotten some emails from staff members who
couldn't solve one of the problems
because they forgot about this.
So it's OK if you forget, but try your best to remember.
No biting your own tail is the only smart thing
our system does.
You'll remember last week when we were talking about rules,
and we were saying that the rule system is not a smart creature.
It doesn't know that "not Polly is dead"
should be the same as "Polly is not dead",
or something like that.
It's too dumb to figure that out.
Well, this system is also dumb, but one thing it knows
is that Patrick really hates if the same node appears twice
within the same path.
And it will destroy that immediately,
before even adding it to the queue.
It's gone.
It's not considered.
It's out of there.
So very important, sad ouroboros,
no biting your own tail.
All right.
So now that I've gotten through that,
let's actually solve the problem with some depth-first search.
How will we do that?
Well, we're not going to use the queue, as popular demand,
we're going to use a goal tree.
So we'll start at node S. What are our choices at node S?
Well, I'm going to force you guys to help.
So it won't be quite as fast, but it'll be fun.
So what are our choices at node S?
You.
AUDIENCE: Me?
PROFESSOR: Yes.
AUDIENCE: A or B?
PROFESSOR: Not quite, and this is something
I like about this problem.
You got most of them.
Do you see that there might be another choice?
Everyone?
Yeah, C. This is a big problem that
has happened on a few different quiz problems where there's
a sort of a grid that looks like a tree,
or a graph that looks like a tree, where
people aren't as willing to go up as they are to go down.
You can see it on some of the other past quiz problems too.
Make sure that you check the connectivity,
and also note that unless otherwise specified--
and I don't think we've really done this much-- the little
connecting edges in our graphs are bidirectional.
You'll see a big arrow, and probably
instructions written at least eight font sizes higher
than all the rest of them, and bold,
if we're going to do something different for this quiz.
It happens that they do it sometimes,
where I'll just say in recitation, we never do this.
And then on the quiz, they do it.
But it will be in giant bold letters, which also leads me
to another silver star idea that I forgot
to tell you guys last week.
So I hope people didn't ditch out on me,
like, oh, Mark's boring.
We won't come next week.
And then miss this one because it just came to my mind.
That is, read the instructions.
It is a very important thing for the quizzes,
and Patrick will, in a later lecture,
tell you guys, ask why five times,
and he'll explain why that's a gold star idea.
My parallel to this is read the instructions five times.
Maybe not five, maybe three or four, but at least three.
Read the instructions.
Read them again.
Then read them a third time only paying attention
to whatever is bold and eight sizes larger
than all the other ones, cause there's going to be something
there that's that size.
And it going to be the thing that everyone misses.
So make sure you're not everyone,
and you read the instructions a lot of times.
But anyway, so yeah, we've got it right.
S goes to A, B, and C. OK.
We're looking at A, B, and C as possibilities.
Everyone, help me make the lexicographic tiebreak.
Where do we go?
AUDIENCE: A.
PROFESSOR: A. That's right.
Actually, I'll call on you guys for other ones,
but that first step is pretty simple.
We could have everyone do it together.
Everyone, A only leads to?
AUDIENCE: D.
PROFESSOR: That's right.
Why doesn't it lead to S as well?
AUDIENCE: [CHATTER]
PROFESSOR: No biting your own tail.
Everyone's right.
Good job, everyone.
All right.
S leads to these three.
You go to A, go to D. Dead end.
Backtrack.
OK.
When we backtrack, we backtrack up to A.
There's no other children.
We backtrack up to S. Where will we go now?
AUDIENCE: B.
PROFESSOR: B. It's the next one alphabetically.
All right.
B can't go to S, so it only goes to?
AUDIENCE: H.
PROFESSOR: Yes.
When we're at H, we can go to?
AUDIENCE: [CHATTER]
PROFESSOR: F or I. That's right.
You guys get this.
Depth-first search is easy.
All right.
But we choose?
F. That's right.
When we're at F, we can go to?
E and J. That's right.
We'll choose?
E. When we're at E, we can go to?
We can go to C. It's not on this particular path.
People are correct when they say C. When we go to C,
we can go to nowhere.
We're dead.
Backtrack.
We backtrack.
We can't do anything at E. We go to F.
Now I forgot to tell you guys, but this is an important note.
Someone's going to get this wrong.
It's going to be one of you.
Look around you, all through the room.
At least one of you is going to do this.
So, now I'm going to tell you not to do this,
and then hopefully, that will still
be true, but for fewer people.
When I went to D, and then I backtracked, and I went to S,
how many times did I backtrack?
Once.
I backtracked once.
This would have been more obvious
if we were doing the really slow boring agenda
way, or queue way, because when we got to SAD,
and we expanded it, and there was nothing left,
we throw it off the top of the queue,
and go to the next thing on the queue.
And it turns out the next thing on the queue is SB.
That step was only taken once.
Since we're using the goal tree, which is faster,
it looked like we did two, but we didn't.
And if you use the queue, you'll see that because it'll go S,
and then we expand that, SASBSC.
SBIC OK.
We expand SA.
SADSBSC.
We expand SAD.
It's dead.
SBSC.
One backtrack.
We're back at SB.
So, so far we've done two, not four.
It's pretty intuitive to say that you did two there.
It turns out you didn't because of the algorithm that's
backing what lets us do this goal tree search.
So try to make sure you're not the one who says two.
And I, on the other hand, will try
to make sure that we don't take off too many points if you do.
Question?
AUDIENCE: So any time you backtrack, regardless
of how much it chains, any backtracking
is just considered once.
PROFESSOR: It is always going to be considered one step.
It's possible to backtrack two times in a row.
Like, if B didn't go to anything, instead
of going to H, then we might backtrack twice
before we got to SC.
Generally, anytime you draw a swizzle, if you're like me,
and you draw a swizzle-- I suggest the swizzles.
They're very nice little things.
But any time you draw a swizzle on your graph,
you have backtracked once.
You could even write BT next to the swizzle,
and go back and count those, or even just count the swizzles
at the end.
You've got it.
You got the answer.
Because they often ask, how many times have you backtracked?
All right.
So good questions, everyone.
So anyway, we backtracked from C. Nothing at E. We go back.
We were at F. So we were at SBHF.
We go to J. It's the only choice.
At J, we can only go to?
AUDIENCE: I.
PROFESSOR: And at I, we can only go to?
And we win.
It's not an optimal search, so as soon as we see anything
with a G on the queue, boom.
Winner.
All right.
And we're done.
We did it.
That wasn't too bad.
For those of you who are vaguely interested in seeing
how I would do it the really super fast way,
it goes something like this.
All right.
ABC.
A comes first.
Only D. Backtrack.
All right.
B comes first.
H. F comes first.
E. C. Nothing.
Backtrack.
We came that way.
JIG.
So that's the really fast way to do depth-first search.
Don't do that, kids.
We don't like-- well, maybe you can.
If you get it right, we're not going
to take off points usually.
Generally, when we say draw the goal tree below,
it's just assigned partial credit.
However, we are pretty strict about that.
If anything is wrong, except for maybe, like, OK,
you write everything exactly right, and forget G at the end.
If anything that's not completely understandable
is wrong, you will probably lose all of the points,
and it'll be a lot of points if you don't draw the goal tree.
I will emphasize drawing the goal tree is a good idea.
All right.
So now let's do a breadth-first search.
Before we do the breadth-first search on this tree,
I will tell you guys that there is also a fast way
to do the breadth-first search which is less risky,
and it really depends on how nice they
are about what they ask for.
In this case, the breadth-first search question
asks, what path does Mark find using breadth-first search?
Rather than saying, what nodes does
he expand in order, or anything like that.
That is important.
If that question is asked you, there
is a trick that will let you solve it very, very quickly.
In fact, faster than depth-first search.
You can solve it by inspection in about 30 seconds.
Does anyone know what the answer is?
What path did he find?
AUDIENCE: [CHATTER]
PROFESSOR: That's correct.
So the answer is?
On this graph, the answer is?
AUDIENCE: SBHIG.
PROFESSOR: SBHIG.
That's the answer.
You would have your five points.
Did people see that?
It doesn't always work, so we're going to actually solve it.
But did everyone see that sometimes you
can get away with not doing it?
Because breadth-first search is guaranteed
to give you the path, as we heard correctly, with the least
number of jumps, and if there are more than one that tie
with the least number of jumps, you can just lexicographically
figure it out, in this case with actual dictionary order.
But SBHIG is the only one.
Let's do an actual breadth-first search though,
so we can feel better about ourselves.
OK.
So you've got S, and S goes to, as we saw before, ABC.
Maybe that doesn't have to go quite so high.
All right.
As we saw before, S goes to ABC.
And you already told me that A goes to D,
and you told me that B goes to H. But what does C go to?
E. That's right.
As you can see, we're expanding it
level by level, left to right.
All right.
So SAD, were does SAD go to?
SAD goes to nowhere.
It's dead.
SBH.
Now, wait.
You might say, wait a minute.
Patrick said that we're using this weird dictionary
order where E is at the end that comes before H. That's
our tiebreak order, but it turns out
that breadth-first search and depth-first search
don't sort in any way.
It's very important.
They don't sort the paths that are currently on the queue.
So you're going to just go left to right, left to right,
left to right.
And only at each node are you going to break ties
in lexicographic order.
All right?
So SBH.
H goes to, as we already know, F and I. E, we
think we already know, but we don't
quite because this is E coming from the other direction.
E, this time goes to F. That's right.
Well, actually, you guys do already know it.
All right.
Great.
Now we come over here.
HF goes to, as we already know, E and J.
I goes to, as we don't already know, HI goes to G and J.
That's right.
And as it turns out, by an implementation detail,
we're done.
Questions?
Does it not expand depth at all?
Now this is an implementation detail.
It's perfectly sane and reasonable
to make a breadth-first search that
likes to finish its entire level that it's working on.
However, in our implementation, and we
would have seen this if we had been pedantic and drawn
out the entire queue-- that's another reason why
drawing out the entire queue is, as I said, more reliable.
In our implementation, since it's not an optimal search,
the moment anywhere on the queue,
you add something with a G at the end, you finish.
And because of the fact that the way breadth-first search does
its mojo, is that it adds everything
to the end of the queue.
That's how it does it level by level, right?
It adds it to the end of the queue, instead of the front.
Well, then you'll add it to the end of the queue,
and then you will have it on the queue with a G.
So you won't have to do SCEF.
Another question?
AUDIENCE: I'm just wondering, so the breadth-first search,
there was no backtracking [INAUDIBLE] had no other--
…

Need subtitles from another video?