Research On Solving MSP Problem Of Special Form And Structure

Since Steve Cook proved the first NP-complete problem,many NP-complete problems have been discovered one after another.At present,with the SAT problem as the root node,more than four thousand NP complete problems have formed a huge resolution tree.NP-complete problems are found in computer science fields such as artificial intelligence,databases,programming languages,and computer networks,and its research has important research significance and application value.This paper aims at a NP-complete problem,namely the MSP problem,to study its structural properties,and conjecture that a special structure can simplify the algorithm proof.Guided by simplified proofs,we have an in-depth understanding of the characteristics of MSP problems from the perspectives of definitions,algorithms,proofs,and resolutions,and propose a special form and structure of MSP problems.When conducting research on SAT problems by analogy,we also carry out research on 2-SAT problems,3-SAT problems,k-SAT and max-SAT problems with special structures.MSP problems with special forms and structures are also of great significance and can further promote the original Study of the problem.The subject is supported by the National Natural Science Foundation of China project "Research on Complexity of NP Complete Problem Solving".The main work of this paper is as follows:First of all,from the perspective of my own understanding,I will introduce the definition and related concepts of the MSP problem.At the same time,the ZH algorithm is introduced,and the steps and various operators of the ZH algorithm are described in detail.It also added content that attributed SAT issues to MSP issues.From the perspective of a special form,the MSP problem is studied from the side,and a special form and structure of the MSP problem is proposed.And on this basis,explain the special meaning of the special structure.A proof of the NP completeness of the MSP problem with a special structure and form is also carried out.Applying the ZH algorithm to the special structure MSP problem proposed in this paper,a new proof is given.In the new proof of the algorithm for solving the MSP problem with special structure,the conditions of the input graph required in the proof of the general form of the MSP problem solving algorithm are simplified,making the proof of some conclusions easier.The correctness of the ZH algorithm for solving the special structure MSP problem is verified by experiments.The specific method is to solve the problem instance of the MSP problem with the special structure,and compare it with the backtracking method to verify the correctness of the algorithm.