This article originated from personal public account: TechFlow, original is not easy, for attention
Today is the 16th in our series on algorithms and data structures, and the fifth in our series on dynamic programming.
The content of today’s article is a very common branch of dynamic programming — state compression dynamic programming. Many people are afraid of state compression, but in fact, it is not that difficult. I hope my article today can take you to learn this classic application.
Binary state
When we talked about multiple backpacks, we talked about binary representation for multiple backpacks. Using the nature of binary, many items are divided into a few items, into a simple zero backpack to solve. Today’s state compression also relies on binary, but I personally find today’s binary applications easier to understand.
Many applications of binary depend on the concept of sets, and we all know that in a computer, all data is stored in binary form. An int integer is four bytes, or 32 bits, and we can represent up to 2.1 billion different numbers by combining zeros and ones on those 32 bits. If we think of the 32 bits as a set, then each number should correspond to a state of the set, and each state of the number should be different.
For example, in the figure above, we list five binary bits. We set two of them to 1 and the rest to 0. So if we do this calculation, we get the number 6, so 6 represents the state 00110. There is a one-to-one correspondence between numbers and states, because every integer converted to binary is unique.
That is, an integer can be converted into a binary number, it can represent a state of a set, and there’s a one-to-one correspondence between the two. This is very important, and it’s the basis of everything that follows.
State transition
The binary representation of an integer can represent the state of a binary set, and since it is a state, it can be transferred. From this, we can draw another very important conclusion — we can represent transitions between states by adding and subtracting integers.
Using the example above, we have five binary bits. Suppose we use these five binary bits to represent five balls, which are numbered from 0 to 4. In this way, you can think of the number 6 as representing the state in which you picked up balls 1 and 2.
If we take ball number 3 at this time, then the state of the set will change, which can be represented by a graph:
In the figure above, the fan’s pen represents a decision. For example, taking the no. 3 ball is a decision. Under the influence of this decision, the state of the set changes. The number represented by the set after the shift is 14, which is the change from the previous set 6 plus the shift, which is equal to
To summarize, we use binary zeros and ones to represent the state of a binary set. The state in which an object may simply exist or not exist. Since the binary zeros and ones can be converted to an int integer, that is to say we use integers to represent the state of a set. In this way, we can represent the change in the state of the set by adding and subtracting integers.
And that’s the essence of state compression, compression, is to compress a collection into an integer, because the integer can be an array subscript, and that makes coding easier.
Travel agent problem
Now that we understand the meaning of state compression, let’s take a look at a classic example, the famous traveling salesman problem.
The background of the traveller question is very interesting. It says that there is a businessman who wants to travel and trade. There are several one-way roads connecting different places. A businessman starts from one place and wants to travel all over the country in the shortest distance. What is the shortest distance required to travel? In this case, we’re assuming that the merchant starts at position 0 and still ends up at position 0.
Let’s take a look at this picture to get a feel for it:
Suppose our merchant starts at zero and wants to travel around and then come back to zero again, what is the shortest distance he has to travel?
This is a fairly simple diagram, but if in the extreme case where all the points are connected, for each point, there are n minus 1 possibilities for where it can go next. So the total number of paths that I could take is n factorial. This is a very large value and is clearly unacceptable. This is why we say that the traveling salesman problem is an NP-hard problem.
NP problem
Now that we’re talking about NP problems, let me tell you a little bit about the definition of NP problems.
Many new algorithms are confused by these concepts, and yes, they all sound the same. It’s easy to get confused. Let’s start with the simplest one, the P problem.
A P problem can be considered a solved problem, and the definition of a solution is that it can be donePolynomial in time complexityTo solve. The polynomial is the same thing as the polynomial
The NP problem is not the inverse of the P problem, where N cannot be understood as No, just as noSQL does not mean non-SQL. NP problems refer to problems where the solution can be verified within a polynomial.
Let’s say we’re given a sorted sequence and we’re told whether it’s ordered or not, it’s easy, we just walk through it. For example, factorization of large integers, it’s hard for us to do factorization, but it’s much easier for us to determine if a factorization is the right solution, and we can just multiply them and compare them.
Obviously all P problems are NP problems, and if we can find a solution in a polynomial, then of course we can also verify that the solution is correct in a polynomial. But is it the other way around, is it something that can be verified in polynomial time, that can be solved in polynomial time by some algorithm? Is it that we haven’t thought of algorithms yet, or that solutions don’t exist in the first place?
The above question is the famous question of whether NP=P is true, which is still a mystery, some people believe it is true, some people do not believe it, and it is considered one of the biggest problems of the 21st century.
To prove the problem, scientists have come up with another way: to make rules. So, for example, to solve equations, it’s very easy for us to solve equations of one variable, but it’s a little bit harder to solve equations of two variables. If we figure out how to understand a binary equation, then inevitably can also be used to avoids solving an equation, because we only need to make another unknown equals 0 is a yuan a equation.
In the same way, we can take NP problems, make them harder, make them more difficult, and make them a final problem. Since this ultimate problem is all NP problems transformed, as long as we come up with an algorithm to solve the ultimate problem, then, all NP problems are solved. For example, if we come up with an algorithm to solve an n-element equation, then this kind of problem is solved. The resulting problems are called NP-complete problems, also known as NPC problems.
Let’s look at a classic NPC problem, the logic circuit problem.
Here is a logical circuit. Assuming we know that its output is True and we know the structure of the circuit, can we be sure that we can find a combination of inputs that produces a final output that is True?
It is obviously a NP problem, because we can directly plug the solution into the circuit to calculate, we can verify that the solution is correct, but it is very difficult to get the answer. It is rigorously proved that all NP problems can be obtained by transformation, which means that if we find a solution that can solve the problem within a polynomial, then we have solved all NP problems.
Finally, there is the NP-hard problem, and the NP-hard problem means that all NP problems can be transformed into nP-hard problems, but it is not an NP problem, which means that we cannot tell whether the solution is correct in polynomial time.
For example, the traveling salesman problem is an NP-hard problem, because even if we are given a solution, there is no way to quickly determine whether the given solution is correct or not. We have to go through all the cases. The complexity of our verification is beyond polynomial, so it’s not an NP problem, it’s harder than an NP problem, so it’s an NP-hard problem.
State compression solution
So having said NP, let’s go back to the algorithm itself.
Since we’re going to use dynamic programming to solve this problem, we can’t get rid of states and decisions. As mentioned earlier, we can use binary to represent the state of a set as an integer. It is easy to think of this state as a state in dynamic programming, but this is not true.
Transfer between pure collection without restrictions, such as the case before we have to take the no. 1 and no. 2 ball, as long as it is the rest of the ball behind can take, but is not the same as the traveling salesman problem, suppose that we have been to the 0 and 1 at the two places, we are currently in position 1, we are unable to use between 2 and 5 of the attachment to update the status, Because we can only start from position one right now. That means there’s a limit to the decisions we can make.
So we can’t just take the state of the set as the state, but to make sure that the order of movement between the locations is correct, we need to add one dimension, which is the current position. So the real state is the state of the position that we walked through before, plus the position that we’re in, the combination of those two.
Once the state is determined, the decision is very simple. All the locations that the current location can go to that have not been to before can constitute the decision.
We said before, in the dynamic programming problem,Complexity is equal to the number of states times the number of decisionsAnd the number of states is zero
Let’s take an example. If n=10, n! = 3628800,
Finally, we implement the following algorithm:
import math
if __name__ == "__main__":
inf = 1 << 31
The adjacency matrix stores edge weights
d = [[inf for _ in range(10)] for _ in range(10)]
# Test data
edges = [[0.1.3], [1.2.5], [2.3.5], [3.4.3], [4.0.7], [4.1.6], [0.3.4], [2.0.4]]
for u, v, l in edges:
d[u][v] = l
Initialize to an approximate infinity
dp = [[inf for _ in range(5)] for _ in range((1 << 5)))
dp[0] [0] = 0
# traversal state
for s in range(1, (1 << 5)) :
for u in range(5) :
# Traversal the decision
for v in range(5) :
# this point must not have been visited
if (s >> v) & 1= =0:
continue
dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])
print(dp[(1 << 5) - 1] [0])
Copy the codeIn the code style of ACM competitions, we usually use U to represent the beginning of an edge and V to represent the end of an edge. So the first triple loop iterates through all the states, and the second double loop enumerates the starting and ending points, i.e. all the edges. We’re traversing the last edge that we moved before the current state, which means the current point is V, and the previous point was U, so the previous state was S minus
If you’ve read the previous article, you’ll see that this is a dynamic programming that goes backwards. We enumerate the current state and all sources of the current state to find the optimal solution to the current state. For those unfamiliar with this concept, check out the other articles on dynamic programming.
There are two details in this code. The first detail is that we did not make a legal judgment on U, so it is possible that u is illegal. For example, there are only two points 2 and 3 in our set, but we enumerate the strategy from 4 to 5. This is fine, because we started with all the states being infinite, and only the legal states are not infinite, and since we want to end up with as small a result as possible, the illegal states are not used to update.
The second detail, which is slightly more subtle, is that we set dp[0][0] = 0 at initialization. That means we’re starting at the empty set, not at zero. Because the number of states that have been traversed at 0 is 1, of course we can set it to 0 already visited, starting at 0, in which case we can’t go back to 0 because each point can’t be visited again, and to get the correct result we also need to add the cost of going back to 0.
Analyze will find the first point is the basis of the second point, if we all judge when enumeration strategy for u point is legal, so there was no way to implement this algorithm, because for an empty set, all points are not visited, also are illegal status, we can’t find a visited u as the starting point of decision.
It doesn’t matter if you don’t understand the above method, I’ll add a slightly simpler method:
# We have traversed from 0
dp[1] [0] = 0
for s in range(2, (1 << 5)) :
for u in range(5) :
U must already be traversed
if (s >> u) & 1= =0:
continue
for v in range(5) :
if (s >> v) & 1= =0:
continue
dp[s][v] = min(dp[s][v], dp[s - (1 << v)][u] + d[u][v])
ans = inf
Plus the distance back to zero
for i in range(5) :
ans = min(ans, dp[(1 << 5) - 1][i] + d[i][0])
print(ans)
Copy the codeIn this case, we’re starting at state 1, which means we’re looking at position 0 as the current point, and we’ve already traversed it, so it’s marked as a 1. The problem is that there’s no way to get back to zero, because you can only go to a point once, so at the end you have to find the optimal path to get back to zero.
The value of (1 << n) -1 is the value of 1 from 0 to n-1, indicating that all n positions have been traversed. And then we go through all the starting points back to zero, and we find the closest one. This is a little easier to understand than the one above, but with a few more lines of code, but a little easier to understand. I suggest that if you have trouble understanding the first piece of code directly, you should understand the second piece of code first, and then figure out why the first piece of code is true.
conclusion
I don’t know how many of you managed to see this, but dynamic programming is really hard, and it’s understandable that it’s hard to understand when you first learn it. But it’s the kind of problem that’s hard to get started with, but easy once you figure it out. And you can see from the amount of code, I used thousands of words to describe the algorithm, it was written only a dozen lines.
Dynamic programming algorithms have always been like this, the code is not long, but each line is the essence. From this point on, its cost performance is really quite high.
Well, today’s article is all of these, if you feel that there is a harvest, please feel free to point attention or forward, your help is very important to me.
