Core: Geographic Maps

Loading...

來自 University of California San Diego 的課程

Java 高级数据结构

890 個評分

University of California San Diego

Java 高级数据结构

890 個評分

課程 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.

從本節課中

Finding shortest paths in weighted graphs

In the past two weeks, you've developed a strong understanding of how to design classes to represent a graph and how to use a graph to represent a map. In this week, you'll add a key feature of map data to our graph representation -- distances -- by adding weights to your edges to produce a "weighted graph". Although this might seem like a small change, the algorithms that work for unweighted graphs may prove ineffective for weighted graphs. To address this problem, you'll explore more advanced shortest path algorithms. First, you'll see how to find the shortest path on a weighted graph, then you'll see how to find it more quickly. In the project, you'll apply these ideas to create the core of any good mapping application: finding the shortest route from one location to another.

Core: Shortest Path with BFS3:28

Core: Geographic Maps4:12

Core: Dijkstra's Algorithm8:56

Concept Challenge: Performance of Dijkstra's Algorithm8:02

Core: A* Search Algorithm5:14

When I struggled: Tackling large programming projects1:26

When I Struggled: Remembering classical algorithms0:31

與講師見面

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

[MUSIC]

In the last video, we started looking at Breadth First Search.

And what we're gonna do next is apply shortest path algorithms

to geographic maps.

So in this video, you should be able to represent a geographic map as a graph with

more details than we've talked about in the past.

And you should be able to explain why Breadth First Search has some limitations

when we're working with graphs that have weighted edges.

So let's take an example graph, what they have here is essentially some of

the cities in the West Coast of the United States focusing in on San Diego and

La Jolla which is where we're at.

So this is essentially a graph, we have the cities here represented as vertices.

We have rows that connect the cities as our edges, and

this is essentially a working graph.

But if you look at this carefully,

you're gonna recognize that there's something essentially missing.

What I want you to do is just pause for a few seconds and

think about what might be missing from this graph.

So when you're thinking about this,

you almost certainly identify the fact that this graph is missing distances.

In fact, there's kind of this joke within the United States that if you live in

the East Coast and you ever visit the West Coast,

you think everything on the West Coast is right next to each other.

We have friends coming from the East Coast, visiting us in San Diego and

they always tell us, while we're there we'll just pop over to San Francisco.

San Francisco's a long ways from San Diego, you don't just pop over there and

likewise I've done this when I visited a friend in London.

I remember telling him I'd really like to go visit Munich and

he said the same thing, Munich isn't close to London, it's some distance away.

So unless you actually have distances on your graph,

we're gonna have some real problems.

And we can see this essentially if we pull up a map from Google Maps,

you can tell that La Jolla and

Tijuana are essentially right next to San Diego, further away is Los Angeles.

Way up to the Northwest is San Francisco, and way out to the Northeast is Las Vegas.

So what we're gonna do is essentially add these distances to our graph.

So what I'm gonna do here then is from San Diego to La Jolla is about 12 miles, so

I put 12 there, La Jolla to Los Angeles is 112 miles and so on.

And, right now, my distances are strictly miles, but we could do something

different if we wanna think about this as essentially the weight of the edge.

What I could do to improve this would essentially take into account, say,

speed limits.

So 112 miles at a 25 mile per hour speed limit is very

different than 112 miles at a 75 mile per hour speed limit.

Likewise, if you're going to go through Los Angeles on

say a Friday afternoon at 4 PM, it's gonna be really really slow because of traffic.

So what we might wanna do is augment this to take into account traffic.

Lastly, San Diego to Tijuana is a very close distance, but

depending on the time of day,

trying to cross the border from San Diego to Tijuana can take a fair amount of time.

So what we wanna do is essentially augment this graph,

and essentially improve it with these other cost metrics.

But we'll save that for later, for

right now, let's just stick with the distances in terms of just raw miles.

My question to you, is if we use Breadth First Search, like we have before, what

would I find for essentially the shortest path from San Diego to San Francisco?

All right, what I'm hoping in taking the in-video quiz,

is that you recognized Breadth First Search is gonna look for the shortest path

essentially just in terms of number of edges, not really distances.

And as a result, what it's gonna find is a path from San Diego to Las Vegas

to San Francisco is two steps away, so essentially the shortest path.

But this is a really long distance, this is 901 miles.

There's no way, if you're trying to drive from San Diego to San Francisco,

that you'd drive through Las Vegas unless you wanted to stop and

say, play poker at a casino.

If you're gonna go straight from San Diego to San Francisco,

you're gonna go through La Jolla,

then through Los Angeles, up through Bakersfield and into San Francisco.

So, how could I have done better?

How could I have made it so I found that shorter path from San Diego through

La Jolla through Las Angeles up to San Francisco?

Well, we'll figure out how to do that with a new algorithm that's coming next.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

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

通過 App Store 下載

通過 Google Play 獲取