Core: TSP Brute-Force Algorithm

Loading...

Из курса от партнера University of California San Diego

Advanced Data Structures in Java

899 оценки

University of California San Diego

Advanced Data Structures in 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.

Из урока

Route planning and NP-hard graph problems

In this week, we'll go beyond the problem of finding a path between two points, and focus on problems requiring overall path planning. For example, if you wanted to go on errands and visit 6 different locations before returning home, what is the optimal route? This problem is actually a really well known problem in computer science known as the Travelling Salesperson Problem (TSP). Attempting to solve the problem will lead us to explore complexity theory, what it means to be NP-Hard, and how to solve "hard" problems using heuristics and approximation algorithms. We'll end the week by showing how reformulating a problem can have a huge impact: making something which was effectively unsolvable before, now solvable!

Core: Traveling Salesperson Problem (TSP)5:28

Concept Challenge: An algorithm for TSP7:18

Core: TSP Brute-Force Algorithm3:36

Core: TSP Algorithm Running Time8:19

Познакомьтесь с преподавателями

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]

All right, so Mia showed you a greedy algorithm to try and

solve this traveling salesperson problem that didn't quite work.

It didn't find the optimal solution for all graphs.

So in this video, we're going to look at a different algorithm that hopefully will

work a little better.

So by the end of this video, you'll be able to describe a brute force algorithm

to solve this traveling salesperson problem.

So again, here's our graph.

Here's our graph of eight cities.

We wanna start and end in San Diego, and we wanna find the minimum cost tour that

visits each city exactly once, and then comes back to San Diego.

Here's again, our graph represented as this adjacency matrix,

where each entry in the matrix is the distance between the city in the row and

the city in the column.

So what is our approach here?

Instead of greedily choosing the next best edge,

which could get us into these dead ends that Mia talked about,

where you'd be forced to take these really high weight, high cost edges.

What we're gonna do is we're going to allow our algorithm to

just try all possible tours,

just try all possible paths through the cities that start and end in San Diego.

So that's our approach.

It's pretty simple, we'll try them all,

we'll just pick the on that's minimum cost.

This is what's known as a brute force solution

because we're not doing anything tricky, we're just gonna pound it out.

We're gonna say,

all right I'm gonna tackle this problem basically the hard way.

I'm just gonna try everything and then pick the best.

And it's a very straightforward approach, and a good approach, as we'll see,

for some description of good.

We'll also see it has its limitations.

So let's give you an example of how this brute force solution is going to work.

It's pretty straightforward.

We're just gonna pick one path through the cities, from San Diego back to San Diego,

calculate its cost by adding up all the distances along those edges.

And then say, okay, the cost of this initial path from San Diego to Lima,

to Paris, to Cairo, to Perth, to Bejing, to Johannesburg,

to Chennai, and back to San Diego is 72,211 kilometers.

So that is currently our best path.

But it's just our first path, so let's try another one.

Let's switch the last two cities, calculate the cost of that path.

Well that one's only 67,115 kilometers, so that's one better.

So we'll record that one as our best path so far.

We'll do another switch, switch around some more cities.

This is a new path.

We'll calculate that cost, which is 70,016 kilometers.

That one's not better than the one we had before.

So, we'll keep the one that we had before as our best so

far, and so on and so forth.

So we're just gonna generate all of the different paths that exist,

keep track of the best one at each point and at the end

of the day once we've considered all the paths, we'll have the best.

And so this works.

It's gonna find us the best path.

And in this case, I implemented a solution for this problem, this brute force

solution, and I found that the best path is actually to go from San Diego to Lima,

to Paris, to Cairo, to Johannesburg, to Perth, to Chennai, to Beijing and

then back to San Diego.

And that has a total path cost of 55,242 kilometers.

All right, so this works great, but

the problem is how long is it going to take?

You might be thinking, mm I don't know there seems to be a lot of possible paths

we can take between these cities.

Is this really a feasible solution?

And if you have this concern you'd be right.

So in the next video we're gonna consider the running time of the solution,

as well as the greedy solution that Mia presented.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play