0:16

We're going to talk about using grids to do Spatial Search.

And now when I mean Spatial, we're going to think

of our grid as modeling some kind of geometric domain.

And then building a search that moves through

the cells in the grid to locate some objective.

0:33

We'll start off by exploring why 1D search is easier than 2D search.

So, we'll do, kind of, interesting example of doing a 1D search.

Then, I'll show you, kind of, a similar example in 2D

and try to help you understand why doing 2D search is hard.

0:49

Then we'll look at some code I've provided that actually does 2D search

on a grid and then we'll finish off the lecture by talking kind

of about a fundamental algorithm for moving over grids and talk a little

bit about how this extends to graphs,

which are the subject of algorithmic thinking.

[BLANK_AUDIO]

All right, I promised you an example of a one dimensional spacial search

and kind of to illustrate why it's easy to do one dimensional searching.

So last summer I took my family to Europe and we spent a few days in Paris.

And one of the highlights of the trip was to walk down the Champs Elysees.

1:29

And my daughter, who is a teenager, was very excited

because there was an Abercrombie and Fitch on Champs Elysees.

So we said here is how we will find it.

We will start at the Arc de Triumph and walk down the

street and eventually we will have to pass by the Abercrombie and Fitch.

So let's just try to do that in Google Maps.

[INAUDIBLE] Arc de Triomphe.

Let's click, let's click, let's click, and there I am.

Oh, good, I'm in Google Street View.

And there it is, the Arc De Triomphe.

And straight ahead is the the Champs de Elysees.

So let's just start walking.

We walk down a little bit, and let's stop and look around.

And now big bus, excellent.

And, let's keep walking, keep walking.

See if we see anything interesting.

I see a few shops, nothing promising though.

Let's walk some more.

let's walk some more.

Let's walk more time, take a look.

Mm, still nothing that looks interesting.

Let's walk again, walk again, let's take a look.

Excellent, this [INAUDIBLE] bus [INAUDIBLE] Let's walk

a few more times, and continue onward.

A gravy truck.

Let's see what else, look around, see if I find anything interesting.

Oh great.

McDonald's.

We found McDonald's.

Well, it turns out that the Abercrombie and

Fitch was a fair bit further down the avenue.

But this points out that there's really a simple

strategy for finding something that's on a one-dimensional path.

You just traverse the path, and eventually you

have to pass by what you're looking for.

What I'll show you next is an example of why 2D Spatial Search is difficult.

2:53

Okay, I promised you an example of why 2D search is difficult.

So let's imagine we're 500 years ago.

So the first thing I'm going to go here and do is I'm going to turn off the map.

So we're sitting here, this is Paris.

If we kind of scroll over here a little bit, here's the English Channel.

We've heard the news that, to the west, there's a vast expanse of unexplored land.

So we're excited and we're going to pop in our

ship and we're going to sail west and find that land.

3:20

And in fact, we've heard news that there's a

colony at Plymouth, which is very close to Boston.

And so we want to sail to that colony.

So, here we go.

We're sailing west, we're sailing west, we're sailing west.

3:31

We're sailing along.

That's a lot of ocean there.

We're sailing west.

And then, we come to the next land.

Hm.

That doesn't look familiar to me and which way do we need to go?

North or south?

I'm going to guess we go South.

Let's go south.

I'm getting nervous here.

Let's get going.

Oh, wait a second, wait a second, this looks familiar.

Let's turn on the map.

And, sure enough, there's Boston, there's New York.

We've been successful.

3:49

This search points out the difficult of searching in two dimensions.

Before we just walked on a simple one-dimensional path and we

just checked to make sure if we passed what we needed.

Here, when we sailed west, kind of the best stretch

we could hope for is to kind of aim

maybe to the north of where we're hoping to

land and then, sail south and look for our target.

4:28

I promised you an example of a 2D search that would

avoid the difficulties of the 1D strategies that we used previously.

So here I've got an interactive demonstration of how this works.

This is going to model the way a fire burns.

So I can go over the canvas and I can click.

And what I've done is I've essentially set a few of the cells on fire.

4:49

Now, if I click the step button, I can cause the fire to spread.

And so you can see here that every time I click

step, I take one of the orange cells, it's kind of the

boundary of the fire, and I look at the four neighboring

cells, and check to see if I can, the fire can spread.

So as I click this, you can see that the fire spreads outward.

And it spreads outward in an interesting manner, it kind of spreads outward

in kind of a uniform speed, it's

not fingering outward in one particular direction.

This is an example of a search called a Bedford search

and that's what we'll talk about for the rest of the lecture.

We can actually do ten steps at a time and we can

watch and the four fires will actually merge to form a single fire.

5:40

On each step, every time we click the step button, we dequeue

an element off the queue, we check to see for its four neighbors.

Which of those neighbours are not yellow?

They haven't been burned.

6:33

The class wildfire, really just a subclass of our provided grid class.

There are a couple things to notice in initializor that are interesting.

We're using this particular syntax here to actually call the

initializer for the grid class to set up our grid.

We have an auxiliary queue which represents the boundary of the fire.

6:54

Kind of moving on down.

We have a few methods that allow us to manipulate that boundary queue.

And, really the most important method is down here, update_boundary.

This is the method that's called whenever you click the step button in the demo.

The way this works is it dequeues an element from the boundary queue.

It computes the four neighbors, so it's going to be a list.

You can uncomment this and get the eight neighbors if you'd like.

You might, might be worth experimenting with the demo with this uncommented.

And for each of those neighbors, we check the following.

We check to see if it's unburnt, if the cell's empty.

If it is unburnt, we set it to be burnt and we added it to the boundary.

7:32

This is the entirety of how the search works.

It's very important that you understand this code.

Spend some time experimenting with it, play with it.

You're going to use this code in this week's mini project.

You really need to understand how this works.

Okay, let's finish things off by talking a little

bit about kind of mathematically how Breadth-First Search works.

7:52

Let's finish off lecture and talk a little bit more about Breadth-First Search.

So here we have a page in the

math notes that talks more about Breadth-First Search.

It's going to talk about a little higher level,

we're not going to specialize it for the Wildfire demo.

But the fundamental idea is the same.

We have a grid, it'll have cells that either visited

or unvisited, that correspond burnt or unburnt in the wildfire demo.

And we'll have a cue that's going to kind

of correspond to the boundary of the search.

here, we have a high level description of the

algorithm for Breadth-First Search, this is basically pseudo code.

But you should really see the body of update boundary sitting right here.

We take our queue, we dequeue something.

We make it to current cell.

We look at all the neighbors of the cell that can be either four or eight.

We check to see if its not visited.

That would be unburnt.

If it is, we make sure it's visited, that would correspond to being burnt.

And then we add those cells back onto the boundary.

If you look at this outer loop here, the, the way the search works is, we

just continually pull things off the front of

the queue, until, the boundary queue is empty.

That means we've searched every cell in the grid.

9:12

The grids that we're working with this week are actually

an instance of a more general mathematical creation called a graph.

So a graph is a collection of notes and edges.

We can kind of visualize graphs in the following way.

We have these circles with numbers.

Those are the notes in the graph, and then we have edges that join adjacent notes.

This is really what's going on in a grid.

We have cells, those correspond to the nodes, and

then adjacent cells are basically paired up by edges.