Loading...

Core: Class Design

Course video 34 of 63

This week you'll get the backbone of your map search engine up and running. In previous courses, including the previous courses in this specialization, you've probably been given most of the classes you needed to complete the assignments. But learning how to design classes from scratch is a key skill that you will need as you become a more sophisticated Java programmer. This week we'll give you the tools you need to create a robust and elegant class design for your map search engine. We'll introduce a similar problem and show you how it can be represented as a graph. Then we'll introduce two core search algorithms: depth-first search and breadth-first search. Finally, we'll turn our graph problem into a set of Java classes. Your task on the programming assignment this week will be to do the same thing, but in the context on the map search engine!

Java 高级数据结构

加州大学圣地亚哥分校

课程 3（共 5 门，Object Oriented Java Programming: Data Structures and Beyond 专项课程）

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

查看授课大纲

您将学习的技能

Graphs, Search Algorithm, Graph Algorithms, Graph Data Structures

教学方

Leo Porter
Assistant Teaching Professor
Mia Minnes
Assistant Teaching Professor
Christine Alvarado
Associate Teaching Professor

脚本

[MUSIC]

All right, so now that we've seen a graph representation for

maze world, let's actually turn that into some Java classes.

So last week, Mia, talked to you about two core representations we can use for

a graph, adjacency lists and adjacency matrices.

And she showed you Java code for each.

But it turns out that when you're actually going to represent a real world problem

with the graph.

And we wanna get beyond representing just integers as the vertex values,

things get a little bit more complicated.

So, even if you understood everything that Mia did last week, this week's assignment

of implementing your own graph classes will still likely be pretty challenging.

So, the goal of this video is to walk you through an example of taking a problem and

turning it in to some Java implementation, of this graph and these graph algorithms.

All right, so again, we're working with a problem that's slightly

different from the problem that you'll be working with on your assignment this week.

On your assignment this week, you'll be looking at cities, and roads, and

intersections, and connecting them.

And then finding paths which would be essentially driving directions

from one point in the world to another.

Here, we're just talking about a very constrained problem,

which is this little two dimensional grid world,

where the robot is trying to get from one place to the goal, the gold in this case.

And our goal of this video is to turn this problem into Java classes, so

that we can solve it.

So in doing your class design, when you start within a blank slate and

a problem to solve,

there's some questions that you consider that can help you plan your classes.

And what classes you're going to need, and what methods and

data each of those classes should have.

So, you want to start by thinking about what am I trying to do with this graph?

What is the goal here of this graph representation?

Another important question to consider is,

what is the ratio of graph vertices to edges?

That can help you decide between an adjacency list representation and

an adjacency matrix representation.

Another question to consider is how to I need to access the vertices in my graph?

What is the user gonna be using in order to access the different

nodes in the graph?

We need to do those operations fast.

And then finally a question you might wanna think about is, what properties,

if any, about nodes and edges do I need to store in my graph?

So, let's look at that first question.

What am I really trying to do with this graph?

Well, we know that we're trying to find pads to the graph, and

in particular, here's the output of the program that I'm trying to write.

I wanna be able to print out the maze, so there's the maze, the horizontal dashes

are empty spaces, they're the nodes in the graph, and then the stars are the walls.

Those are the nodes that don't actually appear in the grid at all.

They're not in my graph.

And then, I wanna be able to do depth research and

print out the path that was found using those little Os.

And then, I wanna be able to do breath research and

print out the path that breath research found, again, using those little Os.

So, that's my goal.

So, I'll definitely need a class to represent the whole graph,

the maze itself.

And I know now what methods, or

at least some of the methods I'm going to need to put into that class.

I'll need a method to do depth research, a method to do breath research, and

a method to somehow print out the graph.

Now, these aren't the only methods that I'm gonna need, but they'll give me

a starting point to think about, what do I need to put into this graph.

So, the next question becomes what data do I need to store in this class?

Well, obviously I need to store some representation of the vertices and

the edges in this graph.

So, that's our next question to consider.

Should I use an adjacency list representation or

an adjacency matrix representation?

Which is better for this particular graph, and this particular problem?

So take a minute to think about Which representation is better here?

All right, hopefully you determined that an adjacent list representation is much

better for this problem, because we've got a very sparse graph.

Each node in our graph is going to have at most four edges going out of it, and

that's an extremely small number relative to the size that this

graph could potentially be.

So adjacency lists are gonna make the most sense.

So the next question becomes how?

How do I put that adjacency list representation into my maze class?

So one thing that we might think about doing is,

Mia was using just numbers to represent each vertex in the graph,

but, we're probably gonna need a little more information for this problem here.

So instead of just using a number to represent each node because it's not even

clear how we would number the nodes in this case.

I am going to create a class that represents each node.

And my class now is capable of storing some information about each node.

Like it's row and it's column and

the grid and perhaps the display character that it's gonna print out.

When we do that printing of the graph with the path.

And then I'll have some getters and setters for those internal variables.

Now, how am I going to store those nodes in my maze class, such that

I get both the node stored away, as well as some information about the edges?

Well, we could just take that example that Mia used and extend it, so

that instead of a HashMap linking integers to lists of integers,

I'll have the HashMap linking MazeNodes to lists of Mazenode's.

So, each MazeNode is going to go in as a key and then the list that's associated

with in the hash map is the list of all of its neighbors.

That will represent the edges.

So this is good.

This is fine.

We can definitely use this implementation.

There's just one problem,

which is that if we think about how we're trying to access these notes.

We're try to call duck first and breath first search, giving a start position and

a goal position.

But unfortunately the user of these methods is not going to

know what Maze Node at the start position is.

They're going to be representing a star position in terms of the row and

column where the robot's supposed to start and

the goal as well in terms of the row and column.

So somehow, we need to get from a row, column representation

to the node representation so that we can start doing our search to the graph.

So we need quick access to translate a row and column into a node.

And this hash set really isn't gonna do that because in order to do this we

have to essentially iterate through all the keys and the hashmap, and

look at each particular node to see if it matched the row and the column.

That's gonna take order n where n is the number of nodes in our graph.

That's not really a good thing, we'd rather do this in constant time.

So instead of using this hash map to store the nodes,

what I'm gonna do instead is use a two dimensional array to store these nodes.

So now I can have instant access to anywhere in the grid, and if that position

doesn't have a node, then I'll just store null in that two dimensional array.

So, the key point here is that we want to make common operations that we

know are gonna happen fast.

But at the same time we don't need to go overboard here.

So, do this within reason.

Consider which operations are really important and try to make those fast.

All right. So we can represent the nodes in this way.

But now we've lost the edges, right?

That hash map representation before was implicitly encoding the edges.

We don't have that anymore.

So, the question becomes, where should I put them back.

I could put them back here in to the Maze class just where I lost them before,

but there's another place I can put them.

Since, I'm representing each node as an object, I can put them over here,

in the MazeNode class, which is better well, not really one or the other.

It's really up to you.

This is just a sort of judgment call on your part.

Which do you like better.

That's a deciding decision you can make.

The decision that I made is to put them over here in the maze node class.

Each maze node is going to store a list of its neighbors, and

you'll be able to access the nodes that are connected to a particular node from

the node class itself, the maze in our class.

All right!

So that's really all there is to our class design, and now we've also got a whole

bunch of other methods that help load the data from a file, that actually do

the [INAUDIBLE] in-depth research, that do the printing, and so on and so forth.

So we really want you to go check out our code.

We've provided you all the code that we've done.

This'll be a good example for you to follow.

It has some parallels,

to what you're going to be doing in your assignment this week.

And what are you gonna look for when you're looking at this code?

Well you wanna look for things like do the objects make sense?

Do they kinda all hang together?

Are the interfaces clean, are we not exposing private data or

data structures that we shouldn't be?

Is it easy and fast do the operations that you need to do a lot, and

are methods short and relatively easy to read?

And I will tell you now.

I'll foreshadow the next video.

Not all of these criteria are perfectly satisfied.

There's some room for improvement in our code as it stands.

So the next video, we're going to critic these codes and make some improvements.

关于 Coursera

课程、专项课程和在线学位均由全世界一流大学和教育机构的顶尖授课教师教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取