Photo from wikipedia
The knapsack problem is an import NP-complete problem in combinatorial optimization. In order to reduce the complexity of the problem, we provide a search computing model based on DNA origami… Click to show full abstract
The knapsack problem is an import NP-complete problem in combinatorial optimization. In order to reduce the complexity of the problem, we provide a search computing model based on DNA origami to solve it. In this paper, we map the choice of each item to the directed path on the origami base of DNA. Then the solution of the problem is mapped to find a directed path to maximize the total value of items in the knapsack. Hybrid chain reaction and fluorescence detection techniques are used to generate solutions satisfying constraints. Lastly, we use Visual DSD simulation software to verify the validity of the model. Compared with other models through simulation, this model can automatically search the solution of the problem, and really reduce the complexity of the problem to linear.
Journal Title: Materials Express
Year Published: 2019
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!