Simulation DNA Algorithm Model of Satisfiability Problem

摘要

This paper puts forward simulation DNA algorithm of satisfiability problem (SAT) based on sticker model. And the key operation of simulation DNA algorithm is batch separation operator. This paper rapidly reduces the calculation scale of simulation DNA algorithm by using two methods. One method is to improve batch separation operator and to simplify batch separation operator set directly by introducing 0 element and deriving element. Research on complexity of simulation DNA algorithm of SAT shows that the calculation scale of simulation DNA algorithm of SAT is determined by the calculation order of separation sets. Therefore, the other method is to put forward selecting separation set problem for the first time and to solve it. Based on less-than relation between separation sets, this paper gives heuristic algorithm for selecting separation set problem, which can minimize the scale of batch separation operator set. It is the above two methods that make simulation DNA algorithm of SAT a more rapid, practical, effective and exact algorithm of SAT. Two examples also explain the practicality and effectiveness of simulation DNA algorithm of SAT.