کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430032 | 687781 | 2014 | 23 صفحه PDF | دانلود رایگان |
• The PATS problem asks to find a set of tiles that self-assembles a given pattern.
• Our exhaustive PS-BB algorithm uses a search tree in the lattice of grid partitions.
• Our heuristic PS-H algorithm finds small solutions significantly faster than PS-BB.
• Answer Set Programming performs well for patterns with a small optimal solution.
• The PS-H algorithm generates not only small but also reliable tile sets.
The Pattern self-Assembly Tile set Synthesis (PATS) problem, which arises in the theory of structured DNA self-assembly, is to determine a set of coloured tiles that, starting from a bordering seed structure, self-assembles to a given rectangular colour pattern. The task of finding minimum-size tile sets is known to be NP-hard. We explore several complete and incomplete search techniques for finding minimal, or at least small, tile sets and also assess the reliability of the solutions obtained according to the kinetic Tile Assembly Model.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 1, February 2014, Pages 297–319