Target algorithm prediction method for Boolean satisfiability problem based on graph

Abstract

The invention discloses a target algorithm prediction method for Boolean satisfiability problems based on a graph, and the method comprises the following steps: designing a graph structure, inputtingthe original definition of each Boolean satisfiability problem in a problem set, outputting related graph structure representation, and constructing a graph structure data set corresponding to an original problem; building a conversion model from a graph structure to a document structure, and building a document data set corresponding to the original Boolean satisfiability problem; building a document vectorization model, and building a group of vectors corresponding to the original Boolean satisfiability problem; and selecting a classification model or a regression model, and training the model to enable the model to learn to predict a target algorithm of the Boolean satisfiability problem. According to the method, the powerful representation capability of the graph is utilized, the original representation of each SAT problem is converted into the logic representation of the graph, effective features are learned from the graph in an unsupervised mode, and finally target algorithm prediction of the problems is learned and applied according to the features.

Description

technical field [0001] The invention belongs to the technical field of computers, and in particular relates to a target algorithm prediction method for analyzing a Boolean satisfiability problem using a graph structure. Background technique [0002] The decision problem is a classic problem in the computer field, and it is also a problem that exists widely in the real world. It is similar to the following problem description. Given all the inputs required by the problem, the output is yes or no. In general, the output of the problem is determined to be yes. How to obtain the input that satisfies this output is our goal. According to the difficulty of the problem, decisive problems are divided into P, NP, NP-Complete and NP-Hard grades. The P problem is the simplest deterministic problem, which can be solved in polynomial time. However, for the other three classes of problems, there is no algorithm that can solve it in polynomial time in a broad sense. They can only be solve...

AI Technical Summary

Problems solved by technology

[0003] The Boolean satisfiability problem (SAT) is the first proven NP-Complete problem. Most of the algorithm prediction research based on this problem is manual analysis of the problem and manual construction of features, which is very time-consuming and labor-intensive. , and the subjectivity of the researcher will also bring some bias into the construction of the problem characteristics

Later, a method based on neural network can automatically learn the characteristics of the problem and summarize the rules predicted by the algorithm. The defect of the input format, it does not help us to save considerable cost, nor is it possible to help people understand the law behind the algorithm prediction

Images