Genetic Algorithm To Solve 3-sat Problems

The 3-SAT problem is basic NP - Complete questions, may abstractly come out from the very many actual problem, very many questions may represent the restraint satisfies the question, it in logical domain and so on inference, artificial intelligence expert system, database safeguarding and retrieval, VLSI design and examination has the broad application, its broad application background urges the people to conduct the thorough careful research to it. Solves the SAT problem the classical algorithm is the solution may the satisfying question classical algorithm be the complete algorithm and the local search algorithm (Local Search). Because branching recollection algorithm and local search algorithm each has his good points, in order to make up for one' s deficiency by learning from others' strong points, Crawford (1,993), Bu and Bai (1,997) and so on proposed separately the local search algorithm and the branching recollection algorithm union mentality, and obtained the good result.We mainly study the 3-SAT problem from the fast solution algorithm angle, Solves the 3-SAT problem using the evolved computation thought, uses the genetic algorithms to solve the 3-SAT problem specifically, its target mainly seeks the good heredity operator to enhance the algorithm the efficiency, as far as possible found Xie Huoji the superior solution (to cause is as soon as possible true value which 3-SAT the clause are as far as possible many), "main work as follows:1. Pair of 3 - SAT problem carries on the reasonable code design, with the unidimensional array representation solution binary code string, the ingenious use two-dimensional array carries on the code to the sentence, m clause code corresponds m to have 6 elements the unidimensional arrays.2. Aims at the specific construction of data, has designed a highly...