Sat question
Author: ESSAYS Cui Tao
Abstract: This article tries to discuss a computer scientific problem, SAT problem. And thereby launched, showing some basic ideas for the charm of computer algorithms, analyzing and designing computer algorithms. Finally, a algorithm and program implementation of the evolution calculation of a SAT issue is given.
Keywords: sat problem, combination explosion, climbing method, A algorithm, evolutionary calculation
Sat question saying (1)
Preface
Computer is a science. Scientific causing problems; computer science is also facing a large number of issues, especially in NPC issues. They have not been solved very well. If you carefully review them, you will find the urgent and difficult, and beautiful.
In numerous NPC issues, there is a "seed" called other problems, that is, SAT issue. The SAT problem is the famous computer scientific puzzle proposed by COOK.
Cook's Theorem Satisfibility IS NP-Complete,
SAT issues are difficult to standard, so they can be called NPC issues.
We do not prove the COOK theorem (see Note 1), the SAT is as follows.
Description of the problem
SAT issues or satisfaction issues, we have to understand it, look at some concepts first.
Sentence: For a limited number of logical variables (or its non-¬) or (∨), such as sentences
C1 = x1 ∨¬X2 ∨X3 ∨ ¬X4,
Each logical variable can be used true or false, and 1 and 0 are represented by 1 and 0. The value of a sentence can be obtained by a set of representations of logical variables. For example, an assignment of X1, X2, X3, X4 is: 0001, then the value of C1 is 1 (true), which assignment is true assignment.
For a collection of logic variables A = {x1, x2, ..., xn}, the finite sentence set is f = {C1, C2, ..., CM}. How to determine if there is a assignment on A, make all the sentences in F true? This is the SAT problem. E.g
F1 = {(x1 ∨X2 ∨X3), (¬X1∨x2), (¬X2∨x3), (¬X3∨x1), (¬X1 ∨¬X2 ∨ ¬ 3 3)},
It can be proved that F1 is not satisfied.
But for a general set f, it is not so easy to judge.
Preliminary analysis of problems
Sets of logical variables a = = {x1, x2, ..., xn}, ie | a | = n, finite sentence collection is f = {C1, C2, ..., cm}, ie | f | = m. Let's discuss how to use a computer algorithm to solve this problem. Regarding the algorithm, here is a limited time downtime (see note 2).
This is a problem with the logic background, the problem of problem solution space, the collection of 0/1 strings using the length of N is very natural. If this collection is Ω, if s ∈ω, there is a 0/1 string of the length N, which is recorded as S = (0 | 1) ^ n.
Obviously we want to determine if you can find a s * ∈ω, where s * is a true assignment.
Collection ω is not an infinite set, obviously | Ω | = 2 ^ n. If you use the exhaustive method, it is solved, but the time efficiency of the algorithm is O (2 ^ n), the exponential growth, which makes our computer fail to take the consumption of the scale growth. Such a large search space, the computer is not finished in the waiting time, producing a combined explosion problem. As shown below:
This kind of search path, I am afraid that there is no solution to the problem, everyone does not know "where the year is the year". What should we do? How can I get as fast as possible search paths, close to our problem? According to the intuition, we need some restrictions that make our search activities close to the problem in a smaller space, and take a straight search path. Of course, it is best to come straight to the problem, even if you jump to the target, but you know, most of you can't do it. General, we hope to be so:
However, this search is limited, how do you find each question? In Figures 1 and 2 we also give two parameters α (n) and β (N), which are the function of the scale N of the problem, indicating the speed of the solution, and the quality of the search restriction, the general, It is not like the border in the figure is linear.
This is the core problem of this article. We use SAT issues as an example to launch the magic and hardships of the computer algorithm world.
Further analysis of the problem
Although the SAT issue has a logical background, the mathematical model can be described in the drawing. Think about it, each assignment can be considered as a state as the node in the figure. Then the collection ω is the junction set in the figure. Considering the potential of the collection Ω, we imagine this picture, not all draw it, such as:
Asside, you can define it yourself.
For example, in the ultra-foundation network, the encoding (0/1 string) of the adjacent (0/1 string) is only one different, and the algorithm that can be easily selected is an E cube routing algorithm. He can be defined by it. In the figure (RI, RJ) of the figure, there is only one bit difference when the RI and RJ encoding are only. and many more.
Regardless of how to define, we can easily think that our algorithm is from a (some) nodes, take a short path, reach a special node of (some) special nodes ---- Solution of the problem!
On this mathematical model, some measures are easy to use, such as depth priority search and width priority search. However, we prefer that the search can be restricted, avoid some path appearance! We suspect that this can be helpful to our problems.
The simplest strategy is that whenever we want to go to the next node, you must give it a judgment, a evaluation value. If this value is less than the current node, we do not consider extending this path to the node.
In fact, this is the basic idea of climbing the mountain. The so-called "climbing" is an image. The key, this evaluation function, in addition, the basic thinking of the mountain climbing is good, but there are some problems. As shown below:
First of all, when the evaluation value of many junctions is the same, it means that we have come to a "flat", how to get out of "flat", or judgment that the top is the highest point? Secondly, there will be many "local mountain peaks" that is not a single peak, and they represent the local best solution representing the problem, but how to identify this "local mountain peak" trap, not "top peaks"?
In order to avoid these problems, our ideas can be done like this. Since it only considers that the next node is still not enough, we add some restrictions, in order to expect more information, it is more convenient to search. For example, go to a "flat" or "local mountain peak", we will look forward to "top peak", look at the gap. Then determine the following steps. This idea is a strategy that is commonly used in artificial intelligence. Some algorithms that are inspired, such as A algorithms, A * algorithms, are all. We look at the SAT problem.
For F, any s∈ω, we set up
F '= {CI | CI is true, Ci∈f, 1 <= i <= m},
A simple mountain climb function is
f (s) = | f '|,
Set the return and algorithm to return to the exit, you can write a climbing method with returning to the way.
Similarly, we can consider adding inspiration information. As shown below, set the collection
F1 '= {CI | CI is true, Ci∈f, 1 <= i <= m},
F2 '= {xi | xi∈A and Xi appear in CJ without appearing in CK, where CJ ∈F-F1', CK ∈F1 ',
1 <= i <= n, 1 <= j, k <= m},
Then the dissipation function is f '(s) = | f1' |,
The inspiration function is h (s) = | f2 '|,
The evaluation function is f (s) = f '(s) h (s),
According to this, the A algorithm solves can be written (see Note 3).
In fact, the key to these algorithms is the selection of the evaluation function. It is a very difficult thing to find a good evaluation function. The evaluation functions we give here are not necessarily optimal. However, through such step analysis, it is desirable that the reader can understand how the computer algorithm is solved. We tend to believe that a good algorithm is designed, and the combination of image thinking and mathematical knowledge requires theoretical analysis and experimentation. We also tried to show you this.
We also have to discuss more fast search strategies.
Reproduction of the problem
For S = (0 | 1) ^ n itself, we can use the diagram to describe, which will be more convenient to use the search strategy in the figure. However, the string itself is also a good mathematical object, especially in evolutionary calculations, this time we discuss it by "string".
We don't give the definition of the calculation, but then the above ideas, come and see this SAT problem; as much as possible, we need everything "water to the stream."
Looking for a problem in a very large search space, we say that we hope to provide a limit to speed search speed. In the above discussion, essence is on the model of the chart, a node, a node approach target. It seems that there is a jealousy, "even jumped to the target", and our subconscious is blocked. I mourn, the subconscious is hidden, sometimes it is a shackle.
Think about it, use a random search strategy, we search for a S, if it is not a solution, turn the S to another S 'according to some kind of random control mechanism, and do it. If this random strategy is convergent, we can solve the problem of "jumping" to the problem as fast as possible.
This "change" process is the key to the strategy. How to express it in mathematics? As the image and effective, the facts have chosen the evolution characteristics of nature, let's watch a picture:
Is it very interesting? In this way, our "change" can borrow biological terms, it is hybridization and variation. For example, for S1 = 010-100-11,
S2 = 110-000-10,
After hybridization can be:
S1 '= 010-000-11,
S2 '= 110-100-10;
After the variation may be:
S1 '' = 010-101-11.
As the theoretical analysis of mathematics, we use model theory, etc., analyze this "change" convergence and performance. But this idea is indeed a very good idea. The author is always surprisingly beautiful and effective solutions. When the beginning of the human brain, what will be like! Always I can't help but try to simulate, we also intend to remind readers to develop such habits.
This idea is the idea of evolution calculation. Evolution calculation is an essential feature of simulating nature, while using a self-organized intelligence calculation on a computer algorithm.
We will continue to discuss this idea next time.
Note 1:
The proof of this theorem uses the conclusions of the logical logic. In fact, as long as it is proved that any NP problem can be converted to a satisfactory problem, the time has a polynomial boundary, which can prove.
Note 2:
I have discussed the problem of the algorithm without stopping the problem of the algorithm. So here, this is said that if you are interested, please refer to:
http://www.9cbs.net/develop/read_article.asp?id=19193
http://www.9cbs.net/develop/read_article.asp?id=20317
Note 3:
It can be demonstrated that H (T) and H * (T) do not have a relationship: H (t) <= h * (t), so this algorithm is a algorithm.
