Core: DFS, Part 1

Loading...

来自 University of California San Diego 的课程

Java 高级数据结构

899 个评分

University of California San Diego

Java 高级数据结构

899 个评分

课程 3（共 5 门，Specialization 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.

从本节课中

Class design and simple graph search

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!

Core: Intro to Class Design4:48

When I struggled: Building useful classes1:03

In the Real World: Design patterns1:19

Core: DFS, Part 16:14

Core: DFS, Part 24:39

Support: Developing Small Examples to Test Your Code6:40

When I struggled: Data structures jargon1:06

When I struggled: The right data structure for the job1:17

Concept Challenge: Performance of DFS and BFS5:58

与讲师见面

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

All right, now it's time to get the robot to the gold.

In order to do that, we're going to look at some fundamental algorithms for

searching graphs.

So by the end of this video, you'll be able to perform an algorithm called

Depth-first Search for searching a graph you'll be able to implement that

algorithm, and you'll also be able to describe how the abstract data type stack

works as well as how a stack is used in depth research.

So let's go back to our graph representation.

Here it is.

And remember that our goal is to take a robot which exists at some location in

this world, and get it to the gold.

Now I drops the background with the walls and the grid and

everything because we really don't need that anymore.

Our task is fully defined by the graph that you see here.

So how are we gonna get the robot from where it starts to the gold?

Well in order to do that, we need to really search for

a path from the robots starting point to the gold.

We're going to look at two different ways to perform that search.

The first is called Depth-first search and the second is called Breadth-first search.

We'll look at Depth-first search first.

Now, before we start looking at the search I want to say that there's lots

of different ways we can play around with this problem here.

We're talking about a robot in a world.

It might be the case that while the robot is searching,

it's actually physically moving through the world.

Or it might be the case that it has a copy of the map before hand, and

it's doing all of its planning before it starts moving.

And which situation the robot is in,

is going to effect which algorithm it chooses to ultimately find it's gold.

We're not gonna get into those details quite yet

in this video but you have the opportunity to explore some of these details

a little bit later on in this course.

So, in order to search this graph let's be a little bit more abstract.

So I'll represent the robot's starting position with this vertex labelled X or

sorry not X,S, and

I'll represent the robot's goal position with that vertex labeled G, for goal.

And then just so I can have a little bit more concreteness,

I'm gonna give all these other vertices in the map letters, so I can talk about them.

Ok.

So now we're ready to begin.

And let me just show you how a Depth-first Search on this graph is going to work.

So the robot starts at position S, and

then what it's going to do is it's going to search all the way deep

along a single path until it gets stuck, or it reaches its goal.

And only then will it decide to go in a different direction.

And the way the robot is going to explore from any particular node it has to be very

methodical in its exploration is it's first gonna try to go

up if that's a possibility and if it's not it's gonna try to go left and

if that's not a possibility it will try to go down and

if that's not a possibility only then it will try to go right.

So let's look at how a Depth-first Search with that order of exploration will work

so robot starts at position X.

Or S.

And it goes up to position I.

So now it's at position I.

It's exploring from I.

So it'll again try to go up.

It can go up, it goes to H.

It tries again to go up.

It can go up, it goes to D, now from D, it can look and see, well, I can't go up,

there is no edge that will lead me up.

So let me try going to the left.

It tries to go left, and it can, and it reaches position C.

It tries to go up, it can't, it goes left, position B.

It tries to go up again, it can't, so it goes left, it goes to position A.

And then from A is says, well let me try to go up, no edge up,

let me try to go left, no left edge, so what does it do?

It goes down.

It goes down to E.

Now it's sitting here exploring from E, and from E it's going to try and

go up, and there is an edge up from E, and so it's going to say, hey,

maybe I should go to A.

But should he go back to A?

Well,no because A is already been explored.

We don't wanna go back to A because if we're going back to A we'll get start in

a loop, going A, E,A ,E, A,E and that'll be no good.

We'd never get any closer to our goal.

So we have to keep track of the fact that we've already seen A and

we don't wanna go back there, so if we do that, then the robot will notice okay,

I've already been to A, so let me try some other direction.

Let me try going down.

And sure enough it goes down and it reaches the goal.

So you'll notice that the robot really just tried to continue to pursue one path,

deeper and deeper and deeper until it got to the goal.

So that's why this algorithm is called Depth-first Search first.

Because it searches deep, as deep as possible.

However it's not always that simple.

So lets modify the graph structure just slightly and try this search again.

So we're still gonna start at position S and everything is gonna start the same.

So we're gonna start searching up, we go to I To H, to D, to C,

to B, to A, but now we're at A, and the robot's kind of stuck.

So my question for you is following this depth-first mantra, what do you think

is going to be the next unexplored node that gets explored using this algorithm?

Okay, if you said F, then you were right, and look at how that happens.

So right now the robot is all the way over there in A, exploring from A, but

it's stuck, there's no place to go from A.

So what it's going to do is it's going to backtrack.

It's going to say, well what about from B?

Where could I have gone from B that I maybe didn't go?

And from B, it's gonna see oh, I could have gone down.

So let me try going down to F.

Well F is a dead end too.

So at this point, it's gonna do the same thing, it's gonna backtrack.

It's gonna say B, anywhere else I can go?

No, not anywhere that I haven't been.

So let me try C.

No, D?

No, H?

I, S, aha.

Now from S, I've got new possibilities.

So it's going to go out from S to L, to K, to J, and ultimately reach its goal.

So you can see the Depth-first Search did find the goal, but

it went all the way to the end of that A and F path before it came back to S and

started exploring down the path that would actually lead it towards its goal.

So that's the major of Depth-first Search.

It's going to go all the way deep before it backtracks and

tries to go in a different direction.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

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

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

通过 App Store 下载

通过 Google Play 获取