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.
Independent Sets in Trees
Loading...
Do curso por University of California San Diego
Advanced Algorithms and Complexity
220 classificações
University of California San Diego
220 classificações
Curso 5 de 6 em Specialization Data Structures and Algorithms
Na lição
Coping with NP-completeness
After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We first show that some special cases on NP-complete problems can, in fact, be solved in polynomial time. We then consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.
Conheça os instrutores
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Michael LevinLecturer
Computer Science
Daniel M KaneAssistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil RhodesAdjunct Faculty
Computer Science and Engineering
The next complicated problem that we're going to solve is called independent set.
And the corresponding special case for which we are going to design a linear time
algorithm is when an input graph is actually a tree.
A real life application of this problem is the following,
assume that you are organizing a company party.
And you would like to invite to this party as many people
as possible with a single constraint.
You know that no person is going to enjoy your party if he or
she is invited together with his or her direct boss.
The mathematical model of this problem is the following.
You are given a tree, and you would like to find in this tree a subset
of vertices of maximum possible size, such that no two of them are adjacent.
Okay, such that there is no edge between any two of them.
So to give an example, consider the following tree.
In this tree, there is an independent set of sides five shown here on the slide.
There is also another independent set of size six.
And an independent set of maximum size is shown here, and it has size seven.
So our goal is to find efficiently,
an independent set of maximum possible size, in any tree.
As we've discussed before, this problem can be solved with a simple algorithm.
The corresponding safe move in this case is the following.
Take into a solution all the leaves.
To prove that this algorithm is correct, we need to show that this step is safe,
mainly that they always exist an optimal solution consistent with this step.
In other words, that there exists a solution which contains all the leaves.
To prove this, we usually argue as follows.
We can take any solution, and we will transform it without
decreasing its size so as to get a solution which contains all the leaves.
In particular, if we start with an optimal solution, I mean,
with the solution of maximum size.
We will transform it into a solution whose size is at least
the size of the initial solution,
which means that this new solution is optimal, and it is also a valid solution.
This will prove that the statement is correct.
Well to explain how to transform it we, as usual, consider a toy example.
So consider such a solution.
So the blue vertices here are selected into an independent head.
So we see that there are three leaves that are not included into our solution.
So let's just take them into our solution.
This will force us, also, to exclude all their parents but the crucial
observation is that this does not decrease the size of the current solution.
And the current solution is still a valid solution because for
each of these leaves we excluded their parents.
So this way, we get a solution of the same size, that includes all the leaves.
And this proves that taking all the leaves in the solution is a safe move.
The corresponding algorithm is quite simple.
So, given that tree, you repeat the following while the three is not empty.
Take all the leaves in the solution, then you remove from the tree all the leaves
together with all its parents, and then you return the constructed solution.
The running time for the current algorithm is if it is carefully implemented.
In particular, you might want to do the following.
For each vertex, you keep track of the number of its children.
You actually do not remove anything from the tree itself.
But you keep track of the current number of children for each vertex.
So when you remove a vertex,
you decrease by one the number of children of each parent.
And you also maintain a queue that contains
the vertexes of the do not have any children currently.
So each iteration you know all the leaves of the current.
This is are the exactly the vertexes with no children.
Now let's generalize the problem.
Assumed that you are still organizing a company party, but
now instead of maximizing the number of people at the party,
you are going to maximize the total fun factor of your party.
Namely, each person is assigned some non-negative fun factor, and
you would like to maximize the total fun factor of all the invited people.
The mathematical model now is the following, you are given tree
with weights on vertices, and you would like to find an independent
set in this tree whose total weight is as large as possible, okay?
To give an example, again, consider the following tree.
One independent set in this tree is shown here in the slide.
Its total weight is 17.
And an optimal one has total weight of 18.
As you see, it doesn't include all the leaves.
So this problem cannot be solved by the same algorithm.
We need to design a new algorithm for this problem.
The new problem can be solved with a dynamic programming technique.
When we have a problem on trees, it is very natural to try to
define sub-problems for subtrees of this tree, and this is what we are going to do.
For vertex v, denote by D(v),
the maximum weight of an independent set in a tree rooted at the vertex v.
Then there are basically two cases.
Either we include v into, into our solution, or we do not include it.
If we include it contributes the weight of this vertex to the total factor.
And we also cannot take any of its children in the solution because
otherwise it will not be an independent set.
However, we can take anything from the subtree's root at its grandchildren.
And particular, we are maximizing the total fun factor, so
we would like to solve the problem optimally for all these subtrees.
So, if we included what we can get, the maximum total fun
factor that we can get is the weight of the vertex v plus the sum of
all the optimal solutions for overall grandchildren w of v.
On the other hand, if we do not include v in the solution,
then we can solve the same problem independently for all its children.
So the second case corresponds
to the situation when we do not include v into our solution.
And in this case, so this is our vertex v and
this is, we do not include that into your solution.
Then we can just solve it optimally for all its subtrees.
And we can then take the sum of all these vertices.
So since they state in the independent subtrees,
the result in union of all the vertices.
Is that we get from our subproblems is also an independent set into wall tree.
We're going to use dynamic programming to implement the corresponding algorithms.
Which uses direct relation that we've just discovered.
Namely, the Function FunParty, for the vertex v,
is going to compute the optimal answer for the subtree rooted at v, when
we only go in to compute it if we haven't computed the corresponding value before.
This is checked in the first if D(v) is still equal to infinity.
So, at this point we assume that the niche earlier, D(v),
is equal to infinity to all vertices.
So, if we haven't computed this value before we start computing it.
Then we check whether the vertex v is a leaf.
If it is a leaf, then the answer is obvious.
Then the obvious routine is to take this vertex into a solution.
So the optimal answer is just the weight of this vertex.
Otherwise, we need to compute its value recursively.
We do this through grandchildren and children of the current vertex.
The first case is when we take the vertex v into a solution.
So first we initialize the variable m1
with the weight of the current, of the current vertex.
And then derive through all grandchildren of the vertex v,
this is done in these two loops.
And we add to m1 the optimal answer for each grandchildren.
We then proceed to the second case when we do not include v into solution.
So m0 is initialized to 0, and then for all children u of vertex V.
We need to add the optimal value for the corresponding children.
This is down here.
Okay, then we just select the maximum of the result into values and
assign this value to D(v).
And finally, we return D(v).
The running time of this algorithm is also the goal of society of the tree
and this is why.
For each vertex there is just one serious call to FunParty.
By serious, I mean a call which actually is inside this.
Which gives rise to some computation, because after the first time when we
are inside this loop for the vertex v, we will store the value in D(v) and
then for any further call for FunParty(v) we just return the value immediately.
Okay we just return it here.
Note also that the value of D(v) is important for
us only when we compute, only when we solve for
sub problem can respond in to its parent and to its grandparent.
Meaning that we will have only a constant number of
calls to FunParty of v for each vertex v.
We now show the result of applying this algorithm to our previous example.
So in this tree we start to fill it in from the leaves to the root.
So for each leaf, the value is computed in an obvious way.
For example, for this subtree the answer is 1.
For this subtree the answer is 2.
And for this subtree the answer is also 1.
For this subtree we need to make a decision.
Either we take this vertex in which we gain 7, or
we don't take it, in which case we can get 1 from here,
2 from here and 1 from here, which gives us 4.
7 is better.
So an optimal independent set in this case, has total weight 7.
For this vertex, its optimal value is 2 because it is a lift, and for this vertex,
again, we need to select whether to take this vertex into a solution or not.
If we can take it, then we cannot take the vertexes 7 and 2 it's children.
So the value of the solution will be 6 plus
the values of its grandchildren which are these.
So the values of its grand children are 1, 2 and 1.
So 6 + 1 + 2 + 1 = 10.
So this corresponds to the case when we takes the root of
the current subtree into solution.
On the other hand, if we don't take it into solutions than the maximum that we
can achieve is 7 in this subtree, and 2 in this subtree, which gives us 9.
10 is better than 9, so 10 is the optimal answer for this subtree.
In a similar fashion, we get 5 here and we get 3 here.
Now for this vertex, again we need to select
whether is better to include it into the solution or it is better to have waited.
If we included the itinerary solutions and the maximums that we can we get a 3 plus,
in this case if we included into solution we can not use it's children,
but we can use anything in the subtree rooted by it's grandchildren.
So we can get 2+3+7+2.
So this gives us 3+2+3+7+2,
which is equal to 17.
Right, if on the other hand we do not include it,
then we can get anything we want from the subtrees through it's children.
This will give us 5+3+10.
5+3+10=18 which is better so
we conclude that 18 Is the best we can do for this toy example.
So this concludes the lecture for the special cases of complete problems.
Let me remind you the main idea once again.
The fact that your problem is incomplete does not exclude the possibilities that.
Some special cases that arise in practice of this problem can be efficiently solved,
and we've just seen two such examples.
Despite of the fact that the satisfiability problem is difficult,
in the general case its special case is, namely, if all the clauses
of a formula contain at most two literals can be easily solved in minimal time.
The second example was about independent set.
This problem is hard in general, so given a graph, it is difficult to implement
an algorithm which always finds an optimum size independent set of a graph.
But, if you know that all of your graphs that are right in your
application are trees, then it is easier to implement a linear
time algorithm that will find an optimal answer quickly.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
