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.

Traveling Salesman Problem

Advanced Algorithms and Complexity

与讲师见面