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.

Â