Core: TSP Algorithm Running Time

Loading...

From the course by University of California San Diego

Advanced Data Structures in Java

891 оценки

University of California San Diego

Advanced Data Structures in Java

891 оценки

Course 3 of 5 in the 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.

From the lesson

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

Meet the Instructors

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

now it's time to figure out how long does that brute force approach take

to solve the traveling salesperson problem and how long does a greedy approach take?

So by the end of this video you'll be able to analyze the running time for

both of these algorithms.

Just to remind you of that brute force approach,

what we're going to do is we're gonna just generate every single path

through the cities, calculate their distance, keep track of the best one.

So and we said it works, but

we're a bit concerned that maybe it was gonna take a long time.

Because there might be a lot of these paths to consider.

So let's take a look at the algorithm a little more formally and

some pseudocode here.

So here's the algorithm.

We initialize our best path and our best distance variables.

And then we have this central loop, and the loop is just gonna execute

as long as there are more permutations of cities, different paths to consider.

Inside the loop we'll just calculate the distance of the current path and

if that current path distance is less than the best distance we've seen so

far we'll keep track of that as the best path and

we'll keep track of that distance as the best distance.

When the loop finishes we'll have a hold of the best path and we'll just return it.

So in our analysis, of course, we have a loop, we just need to figure out first

how much is happening inside the loop and then how many times is the loop executing.

So that if statement there and

what's inside the if statement, that's just constant time.

But the one piece we have to worry about inside the loop is this one right here.

How long does it take to calculate the best distance of a particular path?

Well that's just order n because we basically just need to figure out along

each edge between the cities, what is the distance, and add them all together.

So we've got an order n operation inside the loop.

Now it's time to think about how many times does this loop run?

And the answer to that question is going to be the answer to

how many different permutations are there?

So let's think about this question.

So we wanna figure out how many different permutations or

how many different paths through these cities could we possibly have.

So I'm gonna leave this for a question for you to try to answer.

All right, now that you've had a chance to think about this on your own

let's go over how many different permutations we could have here.

The first question we want to ask is how many different cities can we start from?

Well, there's just one.

We said we're going to start and

end in our hometown, which in this case is San Diego.

The next question is how many cities could we go to from there?

Well if we take away San Diego,

because we're not going to go to San Diego, we've got seven cities remaining.

So we could go to any of those seven cities next.

Then we ask from the first city we go to how many cities can we go to after that?

So let's just arbitrarily assume that we go to Cairo next.

And then ask the question, from Cairo how many cities could we reach?

Well there are six remaining cities to go to so we could reach six cities next.

So we've got the start of some potential paths through our cities.

And I want to pause for

a moment here to think about how many starting pads do we have so far?

Well for each of these first seven cities, that we could pick,

we could then go to six different cities from that first city.

So we have seven cities we could start from, and

for each of those seven cities, there are six options for where to go next.

So in total we have 7 times 6 possible starts to our paths.

So we have 42 starts so far.

And then each of those 42 paths is going to expand in many different ways.

So as we go from city to city to city, we're going to multiply

the number of choices we have at each point by however many paths we had before.

Because each of those paths can expand out in the same number of directions.

So let's continue.

We know that after we have six cities considered, then next time we're going to

have five cities consider, then four, then three, then two, then one, and

finally one remaining city for our hometown back to San Diego.

So overall what we have is 1 x 7 x 6 x 5 x 4 x 3 x 2 x 1..

And this is equal to 5040 paths or

in mathematical notation you may have seen the factorial function.

This is 7 factorial.

7 factorial is just 7 x 6 x 5 x 4 x 3 x 2 x 1.

For any n the factorial function is n x n- 1 x n- 2 x n- 3,

all the way down to times 2 times 1.

So here we have 7 factorial different paths to consider.

In general, if we have n cities, where one of those cities is our hometown,

we're going to have n-1 factorial permutations to try.

So this allows us to go back to our algorithm and fill in the missing details.

We know that this loop is going to run over all the different permutations, and

their n-1 factorial of those permutations.

If we multiply that by the order n work we do inside the loop,

we get that overall this algorithm is order and factorial.

Okay, that looks simple enough.

How bad is that really?

Well, let's think about the factorial function.

How bad it is the factorial function?

How fast does it grow?

At first, it doesn't seem so bad, right?

Seven factorial was only around 5000.

So maybe it's not so bad.

Well, if we look at some values of n, as n gets big,

we can see that it actually is really, really bad.

So 10 factorial is already starting to get pretty big at 3.6 million or so.

By the time we get to 19 factorial,

we're at 1.22 x 10 to the 17 which is roughly the age of the universe.

Up to 23 factorial,

we've got a number that's equal to the number of stars in the universe.

And by the time we get to 59 factorial,

we have a number that's equal to the number of atoms in the known universe.

That is a huge number, totally unreasonable.

And that's only 59.

That's 59 nodes in a graph.

You've been working with graphs that have thousands of nodes in them.

So clearly, we're not going to be able to use this brute force approach

on the graphs you've been working with.

So this brute force algorithm only works for very small graphs and

won't be practical for anything even remotely bigger than small.

Which brings us back to our greedy algorithm.

Now our greedy algorithm isn't optimal in all situations.

But is it fast?

Let's see.

So here's the greedy algorithm.

We're gonna build our path from city to city.

And at each city we're just gonna make the greedy choice and

choose the edge that's smallest to a node that hasn't yet been visited.

So there's the algorithm right there.

We're gonna apply the same analysis technique.

We're going to look at the loop, itself.

How many times does the loop run, and then how much work is done inside of that loop?

So it's fairly straightforward to calculate how many

times the loop runs because there are n minus 1 cities

that we need to consider inside that loop if we subtract out the home town.

So that loop is going to run n minus 1 times.

But how long does it take to do the work that's inside the loop?

The step that we care about here,

the most important step is how to select the closest city to visit next.

Well if you think about it from any city it's a fully connected graph so we have n

minus wind nodes that we could visit, and we need to figure out what's the closest

one that hasn't yet been visited, and that could take at most n minus 1 steps.

So that's about an order n operation.

So putting this all together we have n-1 times the loop is going to run

order n steps each time inside the loop, and

overall our total algorithm time is going to take order n squared.

Phew, n squared much better than n factorial.

So although the greedy algorithm doesn't always find the best solution

sometimes it does.

And it's much, much faster than that brute force approach.

It's practical for even large problems.

And the better news is that sometimes we can even improve on the greedy algorithm.

Not necessarily make it optimal, as Leo's going to talk to you about next, but

at least make it better but keep it really fast.

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

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

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

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

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

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