Dynamic Programming 9 (Tree, Minimum Vertex Cover)
Many problems related to trees can be solved with dynamic programming. Many problems that cannot be solved in polynomial time in simple graphs can easily be solved with dynamic programming in tree graphs because there are no cycles in trees. In this episode we will look at one such classic problem called minimum vertex cover.
Let’s say there are some roads in a city, now we want to put a guard at every turn or junction. If a guard is posted at a junction, he can single-handedly guard the roads connected to the junction. Now you have to say the minimum number of guards needed to guard all the roads?
Let’s see an example.
The method on the left side took us 3 guards but on the right side I showed that it can be done with 2 guards.
These roads and junctions we call edges and vertices or nodes in graph theory. Then the problem is to guard the edges by placing a guard at the lowest vertex or node.
This is an NP-hard problem for general graphs, that is, we do not know any polynomial solution. But if the graph is a tree, we can easily solve the problem with dynamic programming. A graph is a tree if it contains n−1
There will be ta nodes.
8 in the image above
The solution is shown for a tree of nodes.
Subproblem or state determination
To solve this problem we need to make 2 observations:
If a node is not guarded, all nodes connected to it must be guarded, otherwise all roads will not be covered. For example 1 in the image above
If I had not put a guard, then 0,3,4
Of course, guards had to be posted.
Placing a guard on a node does not necessarily guard the nodes connected to it, but sometimes it can be beneficial. For example 1
After placing a guard at 4 it is possible to cover all the roads but in this case 4
By placing this guard, there is more profit.
As before we try to define a function. Naturally, the first thing that comes to mind is f(u).
Which means we are currently on which node. But if you think about it, you will see that we need another information, that is whether there is a guard on the current node or not. When we move from one node to another node, we can use the information about whether the current node has a guard or not to decide whether the next node needs a guard or not.
Several NP-Complete/NP-Hard problems can be solved using bitmasks. It’s not that difficult if you know how to use bitmask. Before reading this article you need to know how to do bit manipulation so that you can read this article. No need to know graph theory to solve this problem.
Today we will solve the famous traveling salesman problem with bitmask. The problem is that you are given some cities and roads as a graph. You must travel from the first city to all the cities exactly once and return to the first city. The question is the minimum distance you can do the work?
In the graph in the figure there are n=4 cities and the optimal path is 0−>1−>2−>3−>4−>0, the total distance is 15
The traveling salesman problem is of NP and NP-hard groups, i.e. the problem is NP-complete. This means we don’t know any polynomial solution to this problem. All solutions are of exponential complexity.
First we start finding subproblems like any other DP problem. We have f(i)
Let us define a function which is i
Distance from the th city to the last city by traveling all intermediate cities. But the problem is that one cannot visit the same city twice, so we need to know which cities we have visited so far. This is where bitmask will help us.
We know that an integer has 32 bits. We will use these bits to indicate which cities we have visited and which cities we have not visited. If i
If I go to the th city, I will turn on the bit i.e. 1
I will make This integer is called bitmask.
Now we can add another parameter to the function: f(i,mask)
. The i means which city you are currently in, mask
It will contain information about which cities you have visited.
5 in the example above
There is a city, so it will take 5 bits. We will use the last 5 bits of 1 integer. At the beginning we are in city 0 and have only traveled to that city. Then the mask will be binary 00001, ie the empty 0th bit will be on.
Now what if you go from 0 to 3?
Now we have also turned on bit number 3. Binary 01001 can be written as 9 in decimal, so the current state is f(3,9).
You understand what is happening by now. We are i
Adjacent from the th city will go to cities that I have not traveled to before and turn on the bit of that city when I go. Our answer is to get the minimum result.
What is the way to turn on th bit? It is explained in detail in the link given at the beginning of the article. Let me remind you one more time. The rule for turning on the i-th bit of a number x is to perform an OR operation with a number whose i-th bit has a 1 but all other bits are zero.
If you want to check whether the i bit is 0 or 1 then AND with a number whose i th bit is 1 and all other bits are zero. If the result is positive then that bit is on.
Actually back to the problem. We need to solve the f(0,1) problem. Recursion ends when f(0,2n−1) is reached. Where does 2n−1 come from? Having n bits on means that all the cities are finished, and the number of which the first n bits are on and the rest are off is 2n−1. For example 23–1=7 in binary is 111.
With means the distance between the two cities.
Assuming w while writing the code
is an n×n array, w[i][j] contains the distance of i and j, if there is no direct path, you can put infinity.
How many numbers can be represented with ta bit? Two options for each bit, total possibilities 2n. That means the value of mask can be from 0 to 2n. That means there are n×2n states. The total complexity for the inner loop will be O(n2×2n).
. Not very good complexity, but not bad at all as an np-complete problem (google Branch and Bound for better algorithms).
Whenever n is seen in any problem
Pretty small and all your item states seem to be saved, will see if that can be solved with a bitmask. It’s not always possible, but now that you have a new problem-solving tool, what’s wrong with trying it?
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel