
Korean: 
오늘 우리는
검색에 대해 알아볼 겁니다
또 검색에 대해 강의를 한다니
여러분이 질색할 것 같네요
컴퓨터 공학과 수업을 듣는 학생들은
이미 601 강의에서 들어 봤을 겁니다
그리고 이론 수업에서도 다시 나올 겁니다
근데 우리는 좀 다른 목적을 가지고 할 거예요
검색에 대한 다양한 직관을 기르는 것에
중점을 두고 진행하겠습니다
그리고 우리 머릿속에서 
일어나는 사고과정으로서의
검색에 대해서도 잠깐 
이야기를 하고 싶습니다
마지막쯤에 가능하다면
지금까지 이 강의에서
한 번도 보여줄 수 없었던
데모를 보여줄 겁니다
왜냐하면 이 작업은 
지난봄에서야 완성되었거든요
오늘 아침에 제가 내용을 좀 더 추가했는데
걱정되지만 어떻게 될지 봅시다

English: 
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.

Korean: 
자 여기 케임브리지가 있어요
여러분도 당연히 알겠죠
어떤 시작점 S에서 목적지 G로
가고 싶다고 가정해봅시다
여러분은 택시를 부르고
최적의 경로로 가길 바랄 겁니다
이렇게 길을 찾아갈 수도 있습니다
별로 좋지는 않죠
이번에는 시작점을 여기로 옮겨 봅시다
실제로 뉴욕에 이런 기사들이 있었어요
아주 좋은 경로는 아니죠
도둑놈의 경로죠
이번에는 탐색 방법을 정직한 초보 기사가
사용할만한 방법으로 바꿔봅시다

English: 
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.

English: 
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.

Korean: 
나쁘지 않네요
이번에는 만약에 택시 기사가
박사 후 연구를 세 번이나 
마친 어떤 물리학 박사였다면
탐색 방법이 어떻게 
달라질지 함께 봅시다
실제로 가는 것이 아니고
기사가 생각하는 과정을 보여주는 겁니다
가능한 모든 경로 중 
최선을 선택하는 것이죠
아까 도둑은 정말 별로였죠
초보 기사는 나쁘지 않았어요
하지만 최적은 아니었죠
이것이 바로 세 번의
박사 후 과정을 마친
물리학 박사가 찾은 최적의 경로입니다
이게 다 어떻게 되는지 알고 싶나요?
답은 당연히 예스겠죠

Korean: 
여러분들이 지금까지 
이런 문제를 풀기 위해
사용했던 방법과는 다른
방법에 관해 얘기할 겁니다
만약에 제가 여러분에게
S에서 G로 가는 경로를 
찾아달라고 했다면 여러분은
몇 초 만에 괜찮은 
경로를 찾았을 것입니다
최적은 아니지만 꽤 좋을 거예요
여러분의 눈을 사용해서 말이죠
이것이 어떻게 되는지를
다루지는 않을 것입니다
왜냐하면 우리는 모르거든요
하지만 문제 풀이에 있어
시각을 사용한다는 것은
우리 지능에서 중요한 부분입니다
지도에서 경로를 찾는 것 같은
일상적인 문제를 해결하는데
인간의 시각계가 어떻게 
기여하는지 이해하기 전까지는
우리는 인간 지능을 
완벽하게 알 수 없을 겁니다
안타깝게도 이런 내용을 다룰 수 없습니다
어떻게 해야 할지 모르기 때문이죠
알아가는 중입니다
하지만 아직은 모릅니다
케임브리지 예시를
사용하지 않을 겁니다
한 시간에 담기에는 너무 많은 내용입니다
우리는 여기 이 지도를 사용할 것입니다

English: 
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

English: 
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

Korean: 
여기는 몇 개의 중요한 
점만 표시되어 있습니다
여러분도 쉽게 눈으로 이 그래프에서
경로를 찾아낼 수 있습니다
하지만 프로그램은 눈이 없고
시각에 의존하는 어떠한 알고리즘도
없기 때문에 다른 방법을 씁니다
우리가 다룰 첫 번째 탐색 방법은
영국박물관 방법입니다
사실 이건 영국 전체는 아니더라도
영국박물관에 대한 모욕일 수도 있어요
왜냐하면 이 방법에서는 모든 
가능한 경로를 찾기 때문이죠
칠판에 모든 가능한 경로를 그려보면
도움이 되겠네요
영국박물관 탐색부터 해봅시다
시작점 S에서 A나 
B로 갈 수 있는 것은
당연한 얘기입니다
벌써 중요한 퀴즈 문제가 나오네요
이런 문제가 퀴즈에 나오면

Korean: 
여러분은 탐색의 과정을 
보여주는 사전식 순서의 트리를
그려야 할 것입니다
따라서 S 아래 있는 노드들은 
알파벳순으로 정렬되어야 합니다
이렇게 하면 질서정연하니까요
이제 A에서 우리는 
B나 D로 갈 수 있습니다
여러분의 퀴즈를 위해
한 가지 더 알려주자면
보통 검색을 할 때는
자기 꼬리를 물지 않습니다
예를 들면 여기 A에 있을 때
S로 돌아갈 수도 있습니다
하지만 경로에서는 자기 자신으로
되돌아가는 것을 허용하지 않습니다
이미 경로에 있는 점으로 돌아가
지나간 곳을 다시
가는 경우는 없습니다
만약 B를 먼저 선택하면
A나 C로 갈 수 있습니다
트리가 점점 커지고 있네요
S, A, B를 보면

English: 
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.

Korean: 
C로 간 후 E로 가는 방법뿐입니다
S, A, D는 자기
꼬리를 물지 않게 하려면
G밖에 갈 수 없네요
S, B, A의 경우 D를 
지나서 G로 가는 방법뿐입니다
마지막으로 S, B, C는
E밖에 갈 수 없습니다
자 여기 가능한 모든 경로를 
담은 트리가 완성되었습니다
가능한 모든 경로를 
찾는 어떤 프로그램을 돌려도
똑같은 결과가 나올 것입니다
이것을 어떻게 만드는지를 
정확히 설명하지는 않습니다
정확히 알 필요가 없거든요
똑똑하다고 일이 줄지는 않습니다
왜냐하면 모든 것을 찾아내야 하니까요
이것이 영국박물관 탐색의 트리였습니다
지금까지 뭘 했나요?
지도로 이것저것 했죠

English: 
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.

Korean: 
어떤 지도를 보여주었습니다
그럼 여러분은 이제 검색은
지도에 관한 것으로
생각할 수도 있습니다
한 걸음 더 나아가기 전에 
하나만 짚고 넘어가겠습니다
검색은 단순히 
지도에 관한 것이 아닙니다
검색은 선택에 관한 것이죠
제가 지도를 사용해서 설명한 이유는
이해시키기 쉽기 때문입니다
하지만 검색은 지도가 아니라
어떤 결정을 해야 하는 상황에서
선택하는 것에 관한 것입니다
따라서 오늘 이야기할 내용은
어떤 지도를 탐색할 때 
해야 하는 선택에 관한 것입니다
다른 것을 탐색할 때는
다른 선택을 할 수 있겠죠
마지막에 시간이 있으면
인문학에서는 문제를 해결하기 위해
어떻게 검색을 
사용하는지 보여줄 겁니다
저것은 영국박물관 알고리즘입니다
검색은 지도에 관한 것이 아닙니다
중요한 포인트는 검색은
선택에 대한 것이라는 겁니다

English: 
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.

English: 
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.

Korean: 
오늘은 지도에 관한 검색을 다룹니다
우리가 다룰 첫 번째 
실질적인 검색 방법은
깊이 우선 탐색입니다
깊이 우선 탐색의 요점은
오로지 앞으로만 
계속 나아간다는 것입니다
여기 S에서 여러분은 
A나 B를 선택할 수 있습니다
일반적으로 왼쪽 가지를
항상 먼저 따라 내려갑니다
따라서 S에서 A로 갑니다
A에서는
B로 가거나 D로 갈 수 있습니다
사전 순을 따라 적는 겁니다
다음은 C로 갈 수 있습니다
그다음은 E로 갈 수 있죠
안타깝게도 더 이상 길이 없네요

English: 
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.

Korean: 
어떻게 하죠?
막다른 길에 도달해버려 
지금까지 한 건 소용이 없어졌어요
물론 전혀 소용이 없는 건 아닙니다
왜냐하면 전에 가장
마지막으로 선택을 했던 곳으로
돌아가 다른 가지를 
선택할 수 있으니까요
이런 과정을 후진(back-up)이나 
백트래킹(backtracking)이라고 합니다
여기가 막다른 길인 것을 깨닫고
트리를 따라 위로 되돌아가면
우리가 D대신 B를 
선택했던 곳으로 옵니다
우리는 여기로 돌아가 
다른 길을 선택합니다
S, A, D 그리고 G로 갑니다
목적지에 도착했네요
여기에 우리의 기본적인 탐색 방법들을
발전시키기 위한 
표를 채워볼 것입니다
탐색을 발전시키는 방법 중에는
방금 말한 백트래킹이 있습니다

Korean: 
백트래킹은 영국박물관 
알고리즘과는 상관이 없었습니다
모든 가능성을 계산하니까요
경로를 찾았다고 멈추지 않았습니다
깊이 우선 탐색에서는 
백트래킹을 사용하는 것이 좋아요
왜냐하면 아래로만 내려가다 보면
목적지로 가는 길을
놓칠 수 있으니까요
자 이런 질문을 할 수도 있습니다
깊이 우선 탐색에서는 
항상 백트래킹을 사용하나요?
교과서들을 보면 
두 가지 모두 가능합니다
걱정 마세요
만약 퀴즈에서
검색에 관한 문제가 나오면
여러분이 백트래킹을 
써야 하는지 명시해줄 겁니다
선택 사항 같은 겁니다
깊이 우선 탐색에서 이 선택 사항을
사용하지 않는다면 바보 같겠지만
그래도 이 두 가지 개념을 분리하여
선택적인 추가 사항이라고 해두죠
지금까지가 깊이 우선 탐색이었습니다
깊이 우선 탐색이 있다면 자연스럽게

English: 
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

English: 
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

Korean: 
너비 우선 탐색도 있겠죠
이 방법에서는 트리를 
한 단계 한 단계 완성해가다
어느 순간 한 단계를 쭉 훑어보면
목적지에 도달하는 경로를
완성했다는 것을 깨닫게 됩니다
자 한 단계씩 보면 
S에서는 A나 B로 갈 수 있고
A에서는 B나 D로 갈 수 있습니다
그리고 B에서는 A나 C로 갈 수 있죠
알겠죠?
한 층 한 층 채워나가는 겁니다
아직 목적지에 
도달하는 층이 없기 때문에
계속 채워나가야 합니다
여기 꽤 큼직한 트리가
만들어지는 것을 볼 수 있습니다
계산하고 있는 경로의 수가
상당히 많습니다
다음 단계에서 B는 C로, D는 G로

English: 
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.

Korean: 
A는 D로, C는 E로 갑니다
이번 층을 훑어보면
G에 도달하는 것이 있습니다
깊이 우선 탐색에서 
경로를 찾았던 것처럼
너비 우선 탐색을 
사용해서 경로를 찾았습니다
왜 G에 도달했는데 탐색을 계속하는지
궁금할 수 있어요
구현의 세부 사항이죠
한 구현을 예시로 봅시다
어떤 식으로 구현해도 상관없지만
지금까지 몇 가지 
탐색 방법을 배웠으니
속도를 좀 내기 위해
방금 배운 탐색 방법을 적용해봅시다
첫 번째는 깊이 우선 탐색입니다 짠
도둑놈의 경로를 찾는 탐색이었죠
그리고 너비 우선 탐색도 있었죠
아직 해보지는 않았지만
어떻게 될까요?
빠를까요, 느릴까요?
좋은 경로를 줄까요?
나쁜 경로를 줄까요?
모르겠으니 함께 해봅시다
굉장히 많은 탐색을 하기 때문에
속도를 좀 높였습니다

English: 
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

Korean: 
정말 많은 경로를 계산합니다
마침내 경로를 하나 찾았습니다
최적일까요?
아닌 것 같네요
오늘은 최적 경로 말고
적당히 좋은 경로에 대해서만
얘기할 것입니다
시작점을 여기 가운데로 옮겨봅시다
너비 우선 탐색이 멍청할 것 같나요?
제 생각에는 좀 멍청할 것 같아요
함께 봅시다
왼쪽을 많이 탐색하네요
여러분의 눈은 절대 이렇게 안 하겠죠
속도는 좀 늦춰서 봅시다
중앙에서 시작했기 때문에
더 짧은 경로를 찾습니다
하지만 왼쪽을 
탐색하는 데 많은 시간을 씁니다
꽤 바보 같죠
하지만 실제로 이렇게 동작합니다
자 이제 우리 표에 
두 가지 탐색 방법이 있습니다
이 탐색이 어떻게 동작하는지
보이는 순서도를 만들어 볼 거예요
이렇게 하면 여러 탐색을 구현할 때

Korean: 
어떤 작은 차이점들이 있는지
알기 쉬울 겁니다
지금부터 우리는 일종의 대기 리스트
혹은 큐를 만들어 볼 것입니다
지금부터는 큐라고 하죠
현재 고려 중인 경로들이
들어있는 큐를 만들어볼 것입니다
우리의 알고리즘이 
가장 첫 번째로 할 일은
이 큐를 초기화하는 것입니다
우선은 이 알고리즘으로
깊이 우선 탐색을
이 문제에 적용해 볼 겁니다
경로를 표현하기 위해
어떤 방법이 필요할 텐데
잠시 제 자신을 
LISP 프로그래머라고 생각해야겠습니다
왜냐하면 LIST의 S-표현식을
사용할 것이거든요
시작할 때 여기 경로가 한 개 있어요
이 경로에는 S 노드만 있습니다

English: 
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.

Korean: 
이 자체가 경로인 거죠
이렇게 큐를 초기화한 후 다음은
큐에 있는 첫 번째 
경로를 연장할 것입니다
S를 연장하면 두 개의 경로가 나옵니다
S에서 A로 가는 것과 
S에서 D로 가는 것이 있습니다
큐에서 가장 첫 번째 경로를 빼 오고
경로를 연장하면서 만들어진
새로운 두 경로를 큐에 넣습니다
첫 번째 경로를 연장했으니 이제
길어진 경로 두 개를
큐에 다시 넣어야 합니다
참고로 빼온 첫 번째 경로가 목적지에

English: 
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

Korean: 
도달하는지 여기서 확인합니다
만약 아니면 연장하는 것이죠
그리고 이 경로들을 
큐에 넣어야 합니다
따라서 큐에 넣는
연산을 추가합니다
첫 번째 절차가 끝났으니
한 번 더 해봅시다
이 첫 번째 경로를 꺼내서
연장할 것입니다
새로운 경로들을 
어디에 넣어야 할까요?
깊이 우선 탐색을 하고 
있다고 가정한다면 말이죠
저는 방금 만들어진 
경로를 계속 활용하고 싶어요
탐색 트리를 따라서 
밑으로 쭉 내려가며 보는 거죠
방금 만든 경로를 
계속 따라가고 싶다면
경로를 어디에 추가해야 할까요?
큐의 제일 뒤?
아니겠죠 그럼
오래 기다려야 할 테니까요
큐의 앞부분에 넣는 게 좋을 겁니다

English: 
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.

Korean: 
깊이 우선 탐색의 경우
큐의 앞부분에 넣을 것입니다
따라서 (S, A, B)와 
(S, A, D)는 여기에 추가합니다
이건 (S, B)여야 했네요
(S, B)는 그대로입니다
아직 가능성이 있으니까요
하지만 그 앞에 새로운
경로 두 개를 추가했죠
큐 앞에서 첫 번째 경로를 빼서
목적지에 도달하지 
않는다는 것을 깨닫고
연장하여 만든 경로를
도로 큐에 추가한 것이죠
이 예시를 끝까지 해봅시다
(S, A, B)를 꺼내고
그다음은 C밖에 없으니
(S, A, B, C)를 추가합니다

English: 
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.

English: 
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.

Korean: 
물론 (S, A, D)와 
(S, B)는 큐에 그대로 있습니다
다시 큐 앞에서 꺼내
(S, A, B, C, E)로 만들어 넣고
(S, A, D)와 (S, B)는 그대로 둡니다
큐에서 첫 번째 경로를 빼봐도
아직 목적지에 도달하지 않았습니다
연장하고 싶지만 할 수가 없죠
막다른 길에 도달했습니다
따라서 이번에는 큐의 첫 번째를 꺼내
큐를 짧게 만들 뿐입니다
거의 다 했습니다
큐에서 (S, A, D)를 꺼내고
(S, A, D, G)를 추가합니다
(S, B)는 물론 그대로 있습니다

Korean: 
이번에 상황을 다시 보면,
그러니까 첫 단계로 돌아가면
실제로 이 경로가 
목적지에 도달한다는 것을
깨닫고 끝내는 거죠
매번 프로그램이 돌 때 
큐를 우선 초기화하고
목적지에 도달하는지 보고
만약 아니라면 연장된 경로를 만들어
큐 어딘가에 추가합니다
그리고 이 단계로 다시 돌아갑니다
사실 여기서 탐색이 
끝났는지 확인하기 위해
여러 조건을 테스트하겠죠
깊이 우선 탐색은 이렇게 동작합니다
만약 여기서 너비 우선 탐색을 한다면
처음부터 다 다시 해야 할까요?
아니죠
똑같습니다
이 코드에서 딱 한 줄만
바뀌면 됩니다
여기서 깊이 우선 탐색을
너비 우선 탐색으로 바꾸려면
무엇을 다르게 해야 할까요?
타냐?
타냐: 큐에 넣는 위치를 바꿔요
큐 어디로?
위치를 바꾼다
탄야: 뒤에 넣어요

English: 
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?

English: 
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.

Korean: 
뒤에 넣는다
너비 우선 탐색을 하기 위해서는
큐의 뒤에 넣으면 됩니다
만약 우리가 비효율적인 
탐색 방법에 그냥 만족하고
찾아낸 경로가 얼마나
좋은지 신경 쓰지 않았다면
여기서 끝났겠죠
하지만 우리에게는
탐색의 효율성이 중요합니다
그리고 좋은 경로를 찾기 원합니다
따라서 우리는 방법을
좀 더 탐구해봐야 합니다
여러분이 알아챘을지 모르지만
아까 봤던 너비 우선 탐색은
굉장히 멍청합니다

English: 
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.

Korean: 
왜 이 알고리즘은 멍청할까요?
카이, 어떻게 생각해?
카이: 우리가 목적지에서
가까워지는지 알 수 없습니다
분명히 이 방법은 우리가 목적지에
가까워지는지 멀어지는지 알려주지 않죠
이 문제는 좀 이따가 해결할 겁니다
하지만 더 심각한 이유가 있습니다
왜 멍청할까요?
이름이 무엇인가요?
딜런: 딜런입니다
딜런: 같은 노드를 두 번 봅니다
딜런은 같은 노드로 가는 경로를
여러 번 연장한다고 합니다
딜런이 이야기하는 게 무엇인지 알아봅시다
여기서 A를 연장합니다
하지만 여기 위에서 이미 했었죠
여기 아래서 B로
가는 경로를 연장하지만
이것도 이미 했었습니다

English: 
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.

Korean: 
여기서 C를 거쳐 가는 
경로를 연장할 수도 있지만
여기에 이미 C를 
거치는 경로가 있습니다
따라서 모든 경로가 중복되고 있습니다
그런데도 다시 계산하고 있습니다
굉장히 멍청한 거죠
지금부터 우리의 알고리즘을
조금 수정해볼 거예요
큐의 첫 번째 경로를
연장하지 않을 것입니다
그 경로의 마지막 노드가 
이미 연장된 적이 있다면 말이죠
뭘 하려는 것이냐면
어떤 경로가 있을 때

Korean: 
이걸 연장하는데
경로에는 마지막 노드가 있겠죠
만약에 이 마지막 
노드로 도착하는 경로를
전에 연장한 적이 있다면
다시 하지 않을 겁니다
따라서 우리가 연장한 경로들의
마지막 노드에 대한 정보를
어떤 리스트에 저장해야겠죠
이해하셨나요?
마지막 노드만 신경을 쓴다는 점이
이상하게 들릴 수 있을겁니다
만약에 한 경로가 어떤 노드로 끝나는데
이미 전에 똑같은 노드로 
끝나는 경로를 연장한 적이 있다면
또 하지 않는 겁니다
시간 낭비니까요
알겠죠?
실제로 이게 도움이 되는지 봅시다
이번에는 확장 리스트를 사용합니다

English: 
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.

Korean: 
여기 가운데 시작점이 있죠
아까 한 탐색을 다시 해봅시다
굉장히 오래 걸리네요
여기 보면 103개의 
경로를 큐에 넣습니다
이번에는 필터를 
적용하고 다시 해봅시다
훨씬 적네요
속도를 올리고 
이번에는 여기서 출발해봅시다
전에 했을 때 굉장히 오래 걸렸었죠
이번에는 이 리스트를
사용하면 짠, 끝났네요
왜냐하면 이미 확인한 마지막 노드를

English: 
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

Korean: 
또 확인하는 바보 같은 짓을
하지 않았기 때문입니다
하지만 절대로 하면 
안되는 것은 아닙니다
이것도 일종의 선택 사항이죠
영국박물관 알고리즘에는
도움이 되지 않습니다
영국박물관 알고리즘은
무엇을 해도 나아지지 않아요
깊이 우선 탐색에서는?
도움이 됩니다
너비 우선 탐색은요?
됩니다
너비 우선 탐색에서 
백트래킹을 할까요?
아니요 여기서 
백트래킹은 도움이 되지 않습니다
좋아요 거의 다 해갑니다
중앙에서 출발할 때는 여전히 
바보 같은 짓을 한다는 것만 빼면요
너비 우선 탐색과 깊이 우선 탐색 모두
왼쪽으로 탐색해 나갑니다
우리의 눈은 절대 그렇게 하지 않겠죠

English: 
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.

English: 
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

Korean: 
따라서 이제 우리가 해야 할 것은
우리가 어디로 나아가는지를 인지하면서
더 좋은 탐색 방법을 알아내는 것입니다
일반적으로는 우리가 가고 싶은 곳에
더 가까워지는 것은 좋습니다
일반적으로 만약에 
목적지로부터 더 가까워지는 노드와
그리 가깝지 않은 
노드 중 선택할 수 있다면
우리는 항상 목적지에 
더 가까운 것을 선택하겠죠
이 메커니즘을 
지금까지 한 것에 추가하면
우리는 새로운 검색 방법을 얻게 됩니다
바로 언덕 오르기(hill climbing)입니다
깊이 우선 탐색과 비슷하지만

English: 
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

Korean: 
어휘 순으로 우선순위를 매기는 대신
목적지와 얼마나 
가까운지로 순서를 정합니다
저렇게 큐를 사용해서 하는 법을
아까 열심히 설명했었죠
이미 문제를 경험했으니
지금부터는 무시할 것입니다
좋은 방법이 아니기 때문이 아니라
모든 것을 다 적으면
더 헷갈릴 수 있기 때문입니다
예시에 따라서 
잘 안 될 수도 있어요
따라서 큐에 관한 부분은 잠깐 빼놓고
오직 우리의 목적지까지 얼마나
더 가까워졌느니만 따져볼 거예요
언덕 오르기 탐색에서는 
깊이 우선 탐색에서 한 듯
A와 B로 시작합니다
똑같이 부모 노드 아래 어휘 순으로
적어나갑니다
이 중에 어떤 것이 
목적지에서 더 가까운가요?
여기서는 B가 A보다 더 가깝습니다
따라서 깊이 우선 탐색에서 한 것처럼

English: 
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.

Korean: 
A를 따라가는 대신 목적지와 더 가까운
B를 따라 내려갈 것입니다
B에서는 A나 C로 갈 수 있습니다
B는 목적지로부터 
6 만큼 떨어져 있고
A는 완벽하게 그리지는
않았지만 7 이상 떨어져 있죠
눈이 아닌 숫자에 의존한 겁니다
자 이제 다음을 보면
A와 C에서 목적지까지의 거리는
대칭적이기 때문에 비슷합니다
이때는 어휘 순으로
순서를 정할 겁니다
S, B, A에서 D로 갑니다
이제는 어떤 게 
목적지까지 더 가까운가요?
선택의 여지가 없죠
하지만 목적지에 도착하게 됩니다
이것이 바로 언덕 오르기 탐색입니다
이번에는 백트래킹을 하지 않았습니다
이것은 최적의 경로도,
최고의 방법도 아닙니다
이것은 최적의 경로도,
최고의 방법도 아닙니다

Korean: 
하지만 적어도 백트래킹은 하지 않았습니다
항상 이런 것은 아닙니다
그저 이 예시에서 그랬을 뿐입니다
언덕 오르기 탐색이 더 빠를 것 같나요?
그럴 것 같네요
이것들을 하나씩 추가할 때마다
어떻게 되는지 봅시다
우선 전에 사용했던 큐를 비웁시다
이렇게 확장된 리스트를 비웠습니다
그리고 비교를 위해 깊이 우선 탐색을
한 번 더 해볼 겁니다
48개의 경로를 큐에 넣으면서 
굉장히 꼬불꼬불한 길을 찾아냅니다
이번에는 언덕 오르기 탐색입니다
어떤가요?
좀 더 곧은 경로가 나올까요?
더 적은 경로를 저장할까요?
짠
이 방법을 안 쓸 이유가 없겠죠?
만약 여러분이 목적지에 가까워지는지
알려주는 휴리스틱이 
있다면 사용하는 게 좋겠죠

English: 
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 think it will produce
a straighter path, fewer
enqueueings?
Boom.
You wouldn't not want to
do that, would you?
If you've got some kind of
heuristic that tells you that
you're getting close to the
goal, you should use it.

English: 
Now, it's easy to modify my
example over there so that
getting close to the goal
gets you trapped in a
blind alley on e.
That's easy to do.
But that's just an artifact
of the example.
In general, you want to go along
a path that gets you
closer to the goal.
So, that's 23.
I don't know, let's see if using
the extended list filter
does any good.
Yeah, still 23.
So, in that particular case
the extension list didn't
actually do us any good, because
we're driving so
directly toward the goal.
OK, that's that.
Now, let's see, is there
any analog to--
well, we might say that this
is yet another way of
distinguishing the searches.
And that is, is it an
informed search?

Korean: 
이 예시를 간단히 수정해서
목적지에서 가까워지게 가다 보면
E에 갇히게 할 수도 있어요
이건 쉽죠
하지만 이 예시에서만 그럴 뿐이죠
일반적으로는 목적지에 가깝게 해주는
경로를 따라가고 싶을 것입니다
여기서 23개이지만
혹시 연장하는 경로를 필터링하는 게
도움이 되는지 봅시다
여전히 23개네요
이 상황에서 확장 리스트를 사용하는 것은
도움이 되지 않았습니다
왜냐하면 목적지를 
향해 바로 나아가니까요
자 여기까지 봤습니다
이것이 바로 각 검색 방법들을
이것이 바로 각 검색 방법들을
구분짓는 방법일 수 있습니다

English: 
Is it making use of any kind
of heuristic information?
Certainly, a British Museum
is not, Depth is
not, Breadth is not.
And now let's consider what
we got for Hill Climbing.
Do we want to use
backtracking?
Sure.
Do we want to use an
enqueued list?
Sure.
And it is informed, because it's
taking advantage of this
extra information.
It may not be in your problem.
It's not often the case you've
got this information in a map.
Your problem may not have any
heuristic measurement of
distance to the goal.
In which case, you
can't do it.
But if you've got it,
you should use it.
Oh, yeah, there's one more.
And I've already given it away
by having it on my chart.
It's called Beam Search.
And just as Hill Climbing is
an analog of Depth-first
Search, Beam Search is a
complement or addition of an
informing heuristic to
Breadth-first Search.
What you do is you start
off just like
Breadth-first Search.

Korean: 
이것은
정보 탐색(informed search)일까요?
어떤 휴리스틱을 사용하고 있나요?
영국박물관 알고리즘은 아니고
깊이 우선이나
너비 우선 탐색도 아닙니다
이번에는 언덕 오르기 탐색을 봅시다
백트래킹을 쓸까요?
물론이죠
큐를 쓸까요?
물론이죠
그리고 이건 정보 탐색입니다
추가적인 정보를 사용하니까요
문제에 따라 없을 수도 있어요
보통 지도에는 이런 
정보를 찾을 수 있습니다
다른 문제에서는 
목표까지의 거리를 알 수 있는
휴리스틱이 없을 수 있어요
그럼 쓸 수 없죠
하지만 있다면 사용해야겠죠
그리고 한 가지 더 있습니다
여기 표에 이미 적어두었지만
빔 탐색(Beam Search)입니다
언덕 오르기 탐색이 
깊이 우선 탐색과 유사했듯이
빔 탐색은 너비 우선 탐색에서
추가 정보를 사용하는 
휴리스틱을 더한 것입니다
시작은 너비 우선 탐색과
똑같습니다

English: 
But you say I'm going to limit
the number of paths I'm going
to consider at any level to
some small, fixed number,
like, in this case,
how about two.
So, I'm going to say that
I have a Beam of
two for my Beam Search.
Otherwise, I proceed just
like Breadth-first
Search, b, d, a, g.
And now I've got that stupid
thing where I'm duplicating my
nodes, because I'm forgetting
about the enqueued list.
But to illustrate Beam Search,
what about I'm going to do now
is I'm going to take all these
paths I've got at the second
level, and I'm only going
to keep the best two.
That's my beam width.
And the best two are the two
that get closest to the goal.
So, those four, b, c, a,
and d, which two get
closest to the goal?

Korean: 
하지만 이번에는 매 단계에서
탐색할 경로의 수를 적게 제한합니다
여기서는 두 개로 제한해보죠
이럴 때 빔 탐색에서의
빔의 너비가 2라고 표현합니다
그 외에는 너비 우선
탐색과 똑같이 합니다
B, D, A, G를 그대로 적습니다
우선은 큐를 제대로 
사용하지 않는다고 가정하면
중복되는 노드가 있는 상황입니다
하지만 빔 탐색을 보여주기 위해서
두 번째 단계에 있는 경로 중에서
두 개만 선택할 것입니다
이걸 빔 너비라고 하죠
가장 좋은 두 개는
목적지에서 가장 가까운 거겠죠
B, C, A, D 중에 어떤 두 개가
목적지에서 가장 가깝나요?

English: 
Now, b and d.
These guys are trimmed off.
I'm only keeping two
at every level.
Now, going down from b and
d, I have, at the next
level, c and g.
And now I've found the goal.
So, I'm done.
We could do that here, too.
We could choose a Beam
Search, not bad.
Let's see, let's try this
thing from the middle.
Let's slow my speed
down a little bit.
Now, are we going to see
anything going off to the left
like we did with ordinary
Breadth-first Search?
No, because it's smart.
It doesn't say, I want to go to
a place that's further away
from my goal.
Now, let's see, maybe we can go
back to our algorithm now

Korean: 
여기서는 B와 D입니다
따라서 나머지 가지는 지워버립니다
매 단계 두 개씩만 남기는 겁니다
자 이제 B와 D에서 따라 내려가면
다음 단계에는 C와 G가 있겠네요
목적지에 도달했으니
끝났습니다
프로그램으로도 돌려봅시다
빔 탐색을 선택해서 돌려보면
나쁘지 않습니다
이번에는 중앙에서 출발해봅시다
속도를 조금 낮춰서 해보죠
왼쪽을 탐색하는지 봅시다
너비 우선 탐색에서는 그렇게 했었죠
아니요
현명하게도 목적지에서 더 멀어지게
가려고 하지 않습니다
이번에는 우리의 알고리즘으로 돌아가서

Korean: 
큐 동작 메커니즘과
언덕 오르기 탐색에 관해 얘기해봅시다
이번에도 같은 기본 검색 메커니즘에서
한 줄만 바꿔서 사용할 수 있을까요?
가능합니다
이번에는 새로운 경로를 
큐의 어디에 추가할까요?
언덕 오르기 탐색과 비슷하겠죠?
큐의 앞에다 넣을 겁니다
하지만 뭔가 더 합니다
그게 뭘까요?
크리스찬, 뭐라고 생각하나요?
휴리스틱을 사용하고
싶다는 걸 염두에 두면
큐의 앞에 넣을 거지만
추가로 무엇을 해야 할까요?
학생: 거리를 확인한다?
거리를 확인한 후
어떻게 정렬할까요?
학생: 가작 작은 걸 앞에?
맞아요 가장 작은 것을
앞에 둘 수 있어요
우리는 정렬을 합시다
정렬해두면 모든 게 말끔하겠죠

English: 
and talk about that enqueueing
mechanism and
talk about Hill Climbing.
Can I use the same basic search
mechanism, just change
that one line again?
Yes.
How do I add new paths to
the queue this time?
Well, it's very much like
Hill Climbing, right?
I want to add them
to the front but
with one little flourish.
What's the flourish?
[? Krishna, ?] what
do you think?
Remember, I want to use my
heuristic information.
So, I not only add them to the
front, but amongst the ones
I'm adding to the front,
what do I do?
AUDIENCE:Check the distance?
PATRICK WINSTON: Check
the distance.
And how do you arrange them?
AUDIENCE:[? You ?]
[? keep the ?] minimum
[? first. ?]
PATRICK WINSTON: Yeah, you
can put the minimum
first if you like.
But let's sort them.
We'll sort them, that will
keep everything straight.

English: 
So Hill Climbing is
front-sorted.
And, finally, how about Beam?
What do we do with Beam Search
to add them to the queue?
Well, it doesn't matter where we
add them, because all we're
going to do is we're going
to keep the w best.
So, with Beam, we'll just
abbreviate that by
saying keep w best.
Now, you have some of the basic
searches in you're toolkit.
There's one more that's
sometimes talked about.
We've got Depth, Breadth, Best,
and Beam, one more is
Best, Best-first Search.

Korean: 
언덕 오르기 탐색은
앞에서부터 정렬합니다
그렇다면 빔 탐색은요?
빔 탐색에서는 큐에 
넣기 위해서 뭘 할까요?
사실 어디 넣는지는 상관이 없어요
왜냐하면
베스트 w개만 남기니까요
따라서 빔 탐색은
베스트 w개를 넣는다고 적을게요
이 정도면 이제 검색에 대한
기본 지식은 갖췄다고 할 수 있어요
마지막으로 가끔 
나오는 하나가 더 있는데
깊이 우선, 너비 우선, 
최선 우선, 그리고 빔 탐색 중
최선 우선 탐색이 남았네요

English: 
It's a variant where you say,
I've got this tree.
It's got a bunch of paths that
terminate in leaves.
Let me just always work on
the leaf node that's
closest to the goal.
It can skip around a little bit
from one place to another.
Because as it pursues one path,
it may not do very well
in some other path
quite distant.
And the tree will become
the best one.
We've actually seen an instance
of that in then
integration program.
It's capable of skipping all
over the place, because it's
always taking the easiest
problem in the search tree, in
the and/or tree, working
on that.
That's Best-first Search.
You can do these sorts
of things in
continuous spaces, too.
And you've done the
mathematics of
that in 1802 or something.
But in continuous spaces, the
Hill Climbing sometimes leads
to problems or doesn't
do very well.

Korean: 
이것은 조금 다른데요
여러 가지를 갖는 트리가 있을 때
목적지와 가장 가까운
단말노드(leaf node)에만 주목합니다
그렇기 때문에 탐색 중
옮겨 다닐 수 있습니다
한 경로를 따라가다 잘 풀리지 않고
어떤 멀리 있는 다른 경로가
최선이 되어 있을 수도 있으니까요
이런 상황을 이미 integration program에서
본 적이 있습니다
여기저기 옮겨 다닐 수 있는 이유는
항상 현재 보고 있는 트리에서
가장 쉬운 문제만을
찾아다니기 때문이죠
이게 최선 우선 탐색입니다
이런 걸 연속 공간에서도
똑같이 할 수 있습니다
이런 수학적인 개념은
아마 전에 다뤘을 겁니다
하지만 언덕 오르기 
탐색을 연속 공간에서 적용하면
잘 동작하지 않을 수도 있습니다

English: 
What kind of a problem can you
encounter in a continuous
space with Hill Climbing?
Well, how would you do
Hill Climbing in
a continuous space?
Let's say we're in the
mountains, and a big
fog has come up.
We're trying to get to the
top of the hill before
we freeze to death.
And we take a few steps north,
a few steps east, west, and
south using our compass.
And we check to see which
direction seems to be doing
the best job of getting
us moving upward.
And that's our Hill Climbing
approach, right?
We have explored four directions
we can go and pick
the best one.
And from there, we pick four,
try all those, pick the best
one, and away we go.
We've got ourselves a Hill
Climbing algorithm.
What's wrong with it?
Or what can be wrong with it?
Sometimes it works just fine.
Yes.
SPEAKER 1: You might get stuck
in a local maximum.

Korean: 
연속 공간에서 언덕 오르기를 하면
어떤 문제가 생길 수 있을까요?
아니 우선 연속 공간에서
언덕 오르기를 어떻게 적용할까요?
여러분이 산속에 있는데
짙은 안개가 꼈다고 가정해봅시다
여러분은 얼어 죽기 전에
산꼭대기로 가고 싶어요
여러분은 나침판을 보면서 동서남북으로
이리저리 발자국을 옮겨봅니다
그러고는 어느 방향으로 가는 게
산꼭대기를 가는 데 
가장 좋은지를 봅니다
이게 언덕 오르기 방식이죠?
우선 갈 수 있는 네 방향을 탐색하고
가장 좋은 걸 선택합니다
또 조금 나아가서 가능한 방향을
탐색해보고 선택합니다
언덕 오르기 탐색을 하는 거죠
하지만 뭐가 문제인가요?
뭐가 문제가 될 수 있죠?
잘 동작할 때도 있는데 말이죠
학생: 지역 최댓값(local maximum)만 찾게 됩니다

English: 
PATRICK WINSTON: We might get
stuck in a local maximum.
So, problem letter a is that if
this is your space, it may
look like that.
And you may get stuck
on a local maximum.
Is there any other kind of
problem that can come up?
Well, it all depends on what
the space is like.
Here's a problem where the
space has local maxima.
Now, a lot of people have
been killed on Mt.
Washington when the
fog comes up.
And they do freeze
to death, why?
The reason they freeze to death
is the Hill Climbing
fails them, and they can't
get to the top
to the ranger station.
And the reason is that there
are large lawns on the
shoulders of Mt.
Washington.
It's quite flat.
So, it's the telephone
pole problem.

Korean: 
지역 최댓값만 찾게 될 수도 있습니다
따라서 첫 번째 문제점은
여러분이 이렇게 생긴 공간에 있다면
그러면 지역 최댓값밖에
도달하지 못한다는 겁니다
또 다른 문제점이 있을까요?
물론 보는 공간에 따라 다르겠죠
방금처럼 지역 최댓값이 
있는 공간이라면 문제가 되죠
워싱턴 산에서는 
짙은 안개가 끼는 날이면
많은 사람들이 실제로 얼어 죽습니다
왜일까요?
그들이 죽는 이유는 
언덕 오르기 방법을 쓰면
결국 산꼭대기에 있는 관리소에
도달하지 못하기 때문입니다
그 이유는 워싱턴 산에는 언덕마다
넓은 들판 같은 공간이 많습니다

English: 
That space looks like this.
Well, this isn't what Mt.
Washington looks like.
But it's the telephone
pole problem.
So, when you're wandering
around here, the idea of
trying a few directions and
picking the one that's best
doesn't help any, because
it's flat.
That can be a problem
with Hill Climbing.
Now, there's one more problem
with Hill Climbing that most
people don't know about.
But it works like this.
This is a particularly
acute problem in
high dimensional spaces.
I'll illustrate it
here just in two.
And I'm going to switch from
a regular kind of view to a
contour map.
So, my contour map is going to
betray the presence of a sharp

Korean: 
전봇대 문제(telephone 
pole problem)가 있는 거죠
그리자면 이렇게 생긴 공간입니다
워싱턴 산이 이렇지는 않지만
전봇대 문제를 보여주는 겁니다
여기서 헤매고 있을 때
사방을 돌아다니며 가장 좋은 
방향을 찾는 것은 소용이 없습니다
납작한 들판이니까요
언덕 오르기는 이런 
문제가 있을 수 있습니다
언덕 오르기에는 사람들이 잘 모르는
문제점이 또 하나 있습니다
이런 식으로 생깁니다
이건 고차원에서 생기는
심각한 문제인데
여기서는 이차원으로 봅시다
지금부터는 일반적인 지도가 아닌
등고선 지도를 그릴 거에요
이 등고선 지도에는 
45도 선을 기준으로 존재하는

Korean: 
뾰족한 산마루를 표현할 겁니다
자 이제 어떤 문제가 생길지 보이죠
어떤 문제냐면 여러분이 
사방으로 조금씩 가보면
모두 내리막길이기 때문에
꼭대기에 있다고 착각할 수도 있습니다
여기 있을 때 북쪽으로 가면
등고선을 따라 내려가게 됩니다
남쪽으로 가보면
역시나 등고선을 따라 내려갑니다
서쪽과 동쪽으로 가봐도 
모두 내려가는 길뿐입니다
사실 여러분은 여기 이 
산마루를 올라가야 합니다
이 등고선이 여기서 
가장 높은 곳이니까요
따라서 때로 속을 수 있어요
갇힌 것은 아니지만 자신이
꼭대기에 있다고 속는 것이죠
사실 이는 무언가를 모델링한 겁니다
이 수업은 지식을 어떻게 
모델링하는 지에 대한 수업입니다

English: 
bridge along the
45 degree line.
Now you see how you can
get in trouble there.
You get in trouble, because
if you take a step in each
direction, every direction
takes you downhill.
And you think you're
at the top.
So, suppose you're right
here and you go north.
That takes you down over
a contour line.
If you go south, that
also takes you down
over contour lines.
Likewise, going west and east
all appear to be taking you
down, whereas, in fact, you're
climbing a ridge.
And that contour line is the
highest that I've shown.
So, sometimes you
can get fooled--
not stuck, but fooled-- into
thinking you're at the top
when you're actually not.
Now, this is a model
something.
This subject is about modeling
intelligence.

English: 
And this is a kind of algorithm
you frequently need
in order to build an
intelligent system.
But do we have any kind of
Search happening in our heads?
If we're going to model what
goes on inside our heads, do
we have to model any kind of
searching in order to do the
kinds of things that
we humans do?
I suppose so.
Anytime we make a plan, we're
actually evaluating a bunch of
choices and seeing
how they work.
Let me see if I can illustrate
it another way.
This is a system that I showed
you a little bit of last time.
And, shoot, I might as well
review one or two things here.
I showed you a Macbeth story.
This is the story
I showed you.
And if you had this in a
humanities class, the simplest

Korean: 
이런 알고리즘은 똑똑한 시스템을
만들기 위해서 자주 쓰입니다
하지만 우리 머릿속에도 
검색 과정이 있지 않나요?
만약 우리 머릿속의 
과정을 모델링한다면
사람이 하는 일을 시키기 위해서
우선 어떤 검색 과정을 
모델링해야하지 않을까요?
해야겠죠
우리가 어떤 계획을 세울 때
우리는 사실 여러 
선택지를 평가하는 겁니다
또 다르게 설명해보도록 하죠
이건 저번 시간에 제가
살짝 보여줬던 시스템입니다
잠시 뭔가 다시 
확인해봐야 할 것 같네요
저번에 맥베스 이야기를 보여줬죠
여기 이 이야기였죠
만약 교양 수업에서 다뤘었다면

English: 
questions that might be asked
is why did Macduff kill
Macbeth down there
at the bottom?
Did I demonstrate the answering
of questions last
time, or just the development
of the graph?
I can't remember.
But we'll do it again, anyway.
This is somewhat stylized
English.
Just so you'll know,
it doesn't have
to be stylized English.
This is English that's made
available to the Genesis
system by way of something
called Story Workbench.
There's no free lunch.
Either you can use your human
resources to rewrite the plot
in third grade English.
Or you can use your human
resources to take a more
natural, adult-type version of
the story and decorate it with
annotations that make it
possible to absorb it.
Just this summer, in a miracle
of summer [? Europe, ?]
[? Brit ?]
[? van ?]
[? Zijp-- ?]
one of you--
connected these two
systems together.
So, we can now work with stories
that are expressed in
pretty natural English.

Korean: 
가장 쉽게 할만한 질문은
왜 맥더프가 맥베스를
죽였는지 일 것입니다
저번 시간에 질문에
답하는 걸 봤었나요?
그래프를 만드는 것만 했나요?
기억이 안 나지만 다시 해봅시다
이 글은 어느 정도 정형화된 영어입니다
하지만 꼭 정형화되어야
하는 건 아닙니다
이 글은 제네시스(Genesis)의
스토리 워크밴치(Story 
Workbench)에서 가져온 것입니다
공짜는 없죠
누군가를 시켜서 
내용을 초등학교 저학년
수준으로 요약해오라 하거나
아니면 좀 더 자연스럽고
성인 수준의 글로 정리한 후
주석을 추가해 내용을 더 깊이
이해하도록 만들 수도 있습니다
놀랍게도 이번 해 여름
브릿벤지라는 한 학생이
이 두 시스템을 합쳤습니다
따라서 이제 우리는 일반적인 영어로
적힌 글로 작업할 수 있죠

English: 
Everything in our system is
expressed in English,
including common sense
knowledge--
like if somebody kills
you, you're dead--
but more importantly, for
today's illustration, that
reflective level knowledge,
that knowledge about what
revenge is.
Here you are.
You're in the humanities class,
and someone says,
what's really going
on in the story?
Not the details of who
kills whom, but is
there a Pyrrhic victory?
Does somebody have a success?
Is there an act of revenge?
These are all kinds of things
you might be asked about in
some kind of humanities class.
So, let me fire up the
genesis system.
Pray for internet
connectivity.

Korean: 
여기 이 시스템에는
모두 영어로 표현됩니다
누군가를 죽이면 죽는다는
기본 상식부터
오늘 보게 될 중요한
사색적인 개념들까지 말입니다
예를 들면 복수 같은 개념이죠
여러분이 교양 수업에 있는데 누군가
이야기 내용에 관해 묻습니다
누가 누굴 죽였는지와
같은 세부 사항들 말고
피로스의 승리(Pyrrhic victory)가 있었는지
누가 성공했는지
누가 복수를 하였는지
교양 수업에서는 이런 질문을
다루게 되겠죠
우선 제네시스 시스템을 켜겠습니다
연결이 잘 되었으면 좋겠네요

English: 
Launch the system on a read of
that Macbeth story that I
showed you just a moment ago.
At the moment, it's absorbing
information about background
knowledge, and about reflective
level knowledge,
and all that sort of thing.
It's building itself
this thing we call
an elaboration graph.
It's not quite there yet.
It's still reading background
knowledge.
Now it's reading Macbeth.
It's building it's elaboration
graph, the same thing you saw
last time, except not quite.
Do you see that stuff
down at the bottom?
Those are higher level concepts
that it's managed to
find in the Macbeth story.
So, its found a revenge.
How did it do that?
It searched.
It had a description of what a
revenge is, and it looked to

Korean: 
시스템을 가동하고 아까 보여줬던
맥베스 이야기를 읽게 해봅니다
현재 배경지식과 사색적인 지식을
받아드리고 있습니다
이제 정교화 도표(elaboration graph)를
만들어가는 중입니다
아직 아니네요
아직은 배경지식을 넣고 있어요
이제 맥베스를 읽네요
정교화 그래프를 만들고 있어요
저번에 본 것과 조금 비슷하지요
여기 밑에 보이나요?
이게 멕베스를 읽으면서
찾아낸 포괄적 개념입니다
여기 복수도 찾았네요
어떻게 했을까요?
탐색한 것이죠
복수가 무엇인지 알고 있었고

Korean: 
그래프에서 이에 맞는 패턴이 있는지
찾아본 것이죠
직접 알려준 정보와
이전에 입력한 인과 규칙들로
복수라는 개념을 
충분히 찾아낼 수 있는
정교화 그래프를 만든 것입니다
피로스의 승리는 좀 더 어려운데
여기서 피로스의 승리를 찾아냈다면
여러분은 A를 받았을 거예요
여기 있네요
여러분들이 볼 수 있게
확대해볼게요
피로스의 승리가 뭔지 알죠?
처음에는 순조롭게 돌아가는 듯하다가
결국 나쁘게 끝나는 상황입니다
맥베스는 여기서 왕이 되고 싶어 하고
실제로 왕이 됩니다
하지만 안타깝게도 결과적으로
살해를 당하죠
따라서 피로스의 승리인 것이죠
이 모든 것이 그래프를 사용해
탐색하여 나온 결과입니다

English: 
see if that pattern
was exhibited in
the elaboration graph.
So, in a combination of things
that were said explicitly and
things that were produced by
knee-jerk if/then rules, the
elaboration graph was
sufficiently instantiated that
the revenge pattern
could be found.
That's interesting, Pyrrhic
victory is a little harder.
You'd probably get an a if you
said, oh, there's a Pyrrhic
victory in here.
There it is.
So, I'll blow that up a
little bit so you can
see what that is.
You know what a Pyrrhic
victory is.
It's a situation where
everything seems to be going
good at first, and
then not so hot.
So, Macbeth wants to
be King down here.
And eventually that leads
to becoming King.
But too bad for Macbeth, because
eventually he gets
killed in consequence.
So, it's a Pyrrhic victory.
All that produced by Search
programs who are looking
through this graph.

Korean: 
이제 이런 걸 할 수 있다면
훨씬 더 많은 것도 할 수 있겠죠
보고서를 적거나
더욱 나아가 질문에 답할 수 있겠죠
왜 맥더프는 맥베스를 죽였나?
대소문자는 크게 상관없어요
기계: 상식적으로는 맥베스가 맥터프를
기계: 화나게 했기 때문에 죽인 것이고
기계: 사색적인 수준에서는
기계: 맥더프의 실수이자 
복수와 피로스의 승리를 위해
기계: 죽인 것 같습니다
말투는 굉장히 기계적이죠
하지만 내용은 알겠죠?
어떻게 상식적인 
수준의 이유를 알았을까요?
다른 프로그램처럼 
목표를 위한 트리를 만들고
답을 찾는 겁니다
트리에서 주변에 연결된 것들을
열심히 탐색하는 것이죠
사색적인 수준의 
답은 어떻게 했을까요?
탐색해서 찾은 정보를 가지고

English: 
Now once you've got the
capability of doing that, of
course, then you can find
all sorts of things.
And you can report
them in English.
But, more interestingly, you
can answer questions.
Why did Macbeth--
it cares not a hoot about
capitalization.
ARTIFICIAL INTELLIGENCE: On a
common sense level, it looks
like Dr. Jekyll thinks Macduff
killed Macbeth because Macbeth
angered Macduff on a
reflective level.
It looks like Dr. Jekyll thinks
Macduff killed Macbeth
as part of acts of mistake,
Pyrrhic victory, and revenge.
PATRICK WINSTON: Pretty
corny speech output.
But you see the point.
How did it get the stuff on
the common sense level?
The same way all those programs
that build goal trees
report, answers the questions.
It's just looking locally around
in the connections in
the goal tree.
How did it get the stuff on
the reflective level?
By reporting on the searches
that produced information--

English: 
it does that by looking for
higher level thoughts about
its own thoughts and reporting
in which of those higher level
thoughts the incident we asked
about actually occurs.
So, let's see, just for fun, we
might be interested in why
Macbeth murdered Duncan.
Wouldn't this be handy if you
hadn't actually read the play,
and here it is, you've got
to write that paper?
ARTIFICIAL INTELLIGENCE:
On a common sense
level, it looks like--
PATRICK WINSTON: I'll pull the
plug on that, because that's
just annoying.
Yeah, pretty good, Macbeth wants
to be King, and Duncan
is the King.
Let's see, why did Macbeth
become King?
Oh, it won't answer
the question
unless I spell it right.

Korean: 
그러니까 자신이 찾아낸 
포괄적인 개념들을 보고
우리가 한 질문과 연관이 있는 개념을
찾아내는 것입니다
자 재미 삼아 하나 더 해봅시다
왜 맥베스는 던컨을 죽였나?
실제로 여러분이 글을 써야
하는데 연극을 읽지 않았다면
도움이 되지 않겠어요?
기계: 상식적으로는....
소리가 조금 거슬리니
소리 없이 보겠습니다
나쁘지 않네요
맥베스는 왕이 되고 
싶었고 던컨이 왕이었으니까요
왜 맥베스는 왕이 되었나?
오타가 있었네요
그럼 답을 하지 못합니다

Korean: 
지난봄까지만 해도 
이런 걸 보여줄 수 없었어요
사실 저번 주까지도 불가능했었죠
오늘 아침에도 조금 손을 봤어요
왜냐하면 이제 막 언어 음성 출력을
파서에 연결해서 영어로 말하도록
하는 과정에 있거든요
따라서 이건 저 말고는
아무도 본 적이 없는 것이었습니다
오늘 수업은 여기서 마무리하도록 하죠

English: 
I wouldn't be able to show that
to you until last spring.
In fact, I wouldn't have been
able to show you this today
until last week with a
tweak this morning.
Because we've just now connected
the language output
to, of course, [? Cass's ?]
parser system, which is running
in reverse, in order
to generate that English.
So, that's something that has
never before been seen by any
eyes but me.
So, that will conclude what
we have to do today.
