This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Grid search
Loading...
来自 Rice University 的课程
Principles of Computing (Part 2)
212 个评分
从本节课中
Searching and Data Structures
This week, we will explain the importance of searching. We will also explore various data structures and learn about inheritance.
与讲师见面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
Welcome to class.
In this lecture.
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.
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.
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.
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.
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.
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.
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.
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.
If we happen, unfortunately to end up landing south of
our target and sailing south, we're going to be in bad shape.
Okay.
So, what we'll look at next is a different
method for doing 2D search that's going to avoid this difficulty.
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.
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.
The way we implement this is we have
an underlying grid that actually stores the yellow cells.
The orange cells on the boundary of the fire are actually stored in a cube.
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.
Those that are unburned, we add to the queue.
And then when we're done, we basically take this cell and turn it yellow.
That simple algorithm allows to kind of visit all the cells
in the grid in a very nice, kind of outwardly growing manner.
So, let's now take a look at the code and see how this works.
Let's look at the code that implemented the demo that we just experimented with.
Here's the code.
We've implement, imported, a grid class.
We've imported a provided queue class and we imported the gooi.
Empty cells are going to be unburnt cells, full cells are going to be burnt cells.
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.
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.
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.
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.
The, the search that we're doing here is actually
applicable to a much wider range of mathematical structures.
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.
The beautiful thing about Breadth-First Search is this also works on graphs.
And in fact, there's a whole wide range of graph algorithms.
And that'll be a major topic that
you're going to look at inside algorithmic thinking.
