Traveling Salesman Problem

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

309 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

309 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

NP-complete Problems

Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Brute Force Search5:42

Search Problems9:44

Traveling Salesman Problem7:57

Hamiltonian Cycle Problem8:09

Longest Path Problem1:42

Integer Linear Programming Problem3:08

Independent Set Problem3:07

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

How I feel is hard problem is the Traveling Salesman Problem.

In this case, making it a graph with vertices that we know

the distance between a, two vertices.

Together with this graph, we are given a budget, b, and

our goal is to find a cycle in this graph that visits each vertex exactly once and

has total lengths at most b.

Finding a short cycle visiting all the given points is a usual task solved

by delivery companies.

For example, this is how an optimal cycle looks like if we need

to deliver something into 15 biggest cities in Germany.

And those application is drilling holes in circuit boards.

Assumes that we have a machine that needs to visit

some specific places in a circuit board to drill in these places.

Of course we would like our machine to visit all these

places as fast as possible.

And for this we need to find a cycle that

visits all those places whose length is as short as possible.

Note the following subtlety.

The travelling salesman problem is of course an optimization problem.

Usually we are given just the graph and

our goal is to find the optimal cycle that visits each vertex exactly once.

That is a cycle of minimum total weight, of minimum total lengths.

At the same time, in our statement of this problem, we also have a budget B.

And our goal is to check whether there is a cycle that visits every vertex

exactly once, and that has total lengths at most B.

We did it to ensure that this is a search problem.

Indeed, it is very easy to check whether given a solution, it is indeed a solution.

For this, we need to check that what is given to us is a sequence of vertices that

forms a cycle, that means it's each vertex exactly once, and

has total lengths it must be.

It is easy to do, we just trace the cycle and

check that it's lengths is at most b, right?

However, it is not so clear for an optimization version.

If you are given a cycle,

how are you going to check whether it is optimal or not.

Once again, we stated the decision version of

the travelling salesman problem to ensure that this is a search problem.

At the same time, in terms of algorithms, these two versions of this problem.

I mean an optimization version where we need to find an optimal cycle and

a decision version where we need to check whether there is a cycle of

total length at most b.

These two problems are hardly different.

Namely, if have an algorithm that solves optimization problem,

we can of course use it to solve the decision version.

If we have an algorithm that finds an optimal cycle, we can of course use it to

check whether there is a cycle of links that must be or not, and vice versa.

If we have an algorithm that for every b checks whether there is

a cycle of lengths that must be, we can use it to find that optimal value of b.

By using binary research.

Namely, we first for example check whether there is an optimal cycle of lengths 100.

If yes, we check whether there is an optimal cycle of lengths 50.

If there is no such cycle we then check whether there is an optimal,

whether there is a cycle of lengths at most 75 and so on.

So it might, eventually we will find the value of b

such that there is a cycle of lengths b but there is no cycle of smaller lengths.

At this point, we find, we have found the optimal

length of a cycle that visits each vertex exactly once.

And this is done by calling our algorithm a logarithmicn umber of times.

And the only way to solve the traveling salesman problem is to check

all possible n factorial permutations of other vertices.

This will give an algorithm whose running time is roughly n factorial.

And this is where we quickly draw in function.

For example, already for n equal to 15 and

factorial is about 10 to 12.

Which means that this algorithm is completely impractical.

There is a better algorithm because running time is still exponential.

It is based on dynamic programming and we will see it later in our class.

It's running time is n squared times 2 to the n, where n is the number of vertices.

So it is still exponential but it is much better than n factorial.

In fact, we have no better algorithm for this problem, unfortunately.

So this is the best upper bound that we can prove.

In particular, we have no algorithm that solves this problem in time,

for example 1.99 to the n.

At the same time,

there are algorithms that solve this problem in practice quite well.

Namely, even when n is equal to several thousands.

It is usually sold by heuristic algorithms.

So such algorithms solve practical instances quite well.

In practice, however, we have no guarantee on the running time of such algorithms.

And also, there are approximation algorithms for this problem.

For such algorithms, we have a guarantee, guarantee on the running time.

At the same time, what they return is not an optimal solution, but

the solution which is not much worse than optimal.

For example, in the approximation algorithms that we will study later can

find in polynomial time the cycle which may not be optimal but

it is guaranteed to be at most two times longer than an optimal one.

It is instructive to compare the Traveling Salesman Problem

with the Minimum Spanning Tree problem.

Recall that in the Minimum Spanning Three Problem, we are given a graph, or

just a set of cities, and our goal is to connect all the cities to each other

by adding n minus 1 edges of minimum possible total lengths.

For example, the minimum spanning tree for

this set of six cities might look like as follows.

So added five edges to connect all these six cities.

Now we can see the travelling salesman was for

the same set of cities.

So for a moment, assume that in the traveling salesman problem,

we need to find not a cycle but a path, okay?

Then in this case, the optimal path for

this set of six cities might look like this.

Note that in this case, this path, what we're looking for

in optimal paths is also a 3, right?

So this is a 3 with 5 edges that spans all the vertices.

This means that the travel and salesman problem is a problem that we get

from the minimum spanning tree problem by posing an additional restriction

that the tree that we're looking for should be actually a path, right?

So this is emphasized here.

And by posing this additional restriction to the minimum spanning tree problem.

We get a problem for which we know no polynomial time algorithm.

So once again, for this problem.

For the minimum spanning tree problem,

we have an algorithm whose running time is almost linear.

For this problem, we have no polynomial time algorithm.

We have no algorithm whose running time is quadratic or cubic or

even something like n to the one to 1,000.

This is a very difficult problem, resulting from the minimum spending

tree problem, by posing some additional small restriction.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play