基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2q/2),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.     

子集和问题的O(1.414n)链数DNA计算机算法

随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.     

基于质粒分子数子集O（1．414^n）DNA计算机算法

文章提出了一种求解背包问题的新的基于质粒DNA计算机算法.本算法的DNA链数可达到亚指数的O(1.414n),其中n为背包问题的维数.将提出的算法与已有文献结论进行的时比分析表明:本算法将穷举算法中所需的DNA链数从O(2n)减少至O(1.414n),因此利用本DNA计算机算法在试管级水平上能将可破解的背包公钥的维数从60提高到120,显示出了一定的优越性.     

一种改进的最大团问题DNA计算机算法(英文)

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n）,同时文中算法还具有高效的空间利用率及容错能力的优点．     

精确覆盖问题的O(1.414~n)链数DNA计算机算法

DNA计算机的可扩展性问题是近年来生物计算领域的重要研究重点之一.根据精确覆盖问题DNA计算求解过程中的并行计算需求,将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法.算法由初始解空间生成算法Init()、冗余解删除算法IllegalRemove()和并行搜索器ParallelSeacher()共3个子算法组成.与同类算法的性能比较分析表明:本算法在保持多项式生物操作复杂性的条件下,将求解n维精确覆盖问题的DNA链数从O(2n)减少至O(1.414n),从而将DNA计算机在试管内可求解的精确覆盖问题集合的基数从60提高到120,改进了相关文献的研究结果.     

基于分治的背包问题DNA计算机算法

DNA计算机研究的重要内容是关于如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数。本文将分治策略应用于背包问题的DNA分子计算中,提出了一种新的DNA计算机求解背包问题的算法。背包问题的算法由咒位并行减法器、咒位数据搜索器和其他的4个子算法组成。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

一种基于DNA计算的指定结点路由算法

带指定结点约束的路由问题是一个NP难问题,该问题是电信行业路山智能化和交通电力运输等领域的关键问题之一.基于DNA计算的高度并行性,文中提出一种将电子计算机与DNA计算机相结合的方法求解指定结点路由问题.算法由转化算法Transform()、首末结点搜索切割算法FirstEndSearcher()、转化图结果搜索算法DNASearcher()和结果读取算法ResultReader()共4个子算法组成.分析表明:算法的电子计算机部分缩小了问题结点和边的规模,从而使解决问题所需的DNA分子链数数量级从O((n-2)!)减少至O((m-2)!)(n≥2为图中结点数,m≥2为图中指定必经结点数).算法的DNA计算机部分采用了有针对性的DNA编码新方案,提高了边权值编码的信噪比,通过一系列生物操作,筛选出问题的精确解.和单纯DNA超级计算或电子计算机指定结点路由算法相比,文中算法可显著扩大理论上待求解问题的规模.     

一种最大匹配问题DNA计算算法

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.     

一种加群Z上离散对数问题的DNA计算算法

加群Zp+上离散对数问题在公钥密码系统分析中具有非常广泛的应用。研究一种加群Zp+上离散对数问题的DNA计算算法。算法主要由解空间生成器、并行乘法器、并行加法器、解转换器及解搜索器组成。其中解空间生成器借鉴传统计算机中3表算法的思想,将解空间的生成分为3个部分来完成,极大减少了非法解的搜索空间。本算法的生物操作时间复杂度为O(k2),需要O(1)个试管数、O(2k)条DNA链,最长DNA链长为O(k2)(其中k为加群上离散对数问题群阶p的二进制编码位数)。最后,通过DNA计算通用的试验方法对算法进行了仿真,验证了算法的可行性和有效性。     

Molecular Verification of Rule-Based Systems Based on DNA Computation

Various graphic techniques have been developed to analyze structural errors in rule-based systems that utilize inference (propositional) logic rules. Four typical errors in rule-based systems are: redundancy (numerous rule sets resulting in the same conclusion); circularity (a rule leading back to itself); incompleteness (deadends or a rule set conclusion leading to unreachable goals); and inconsistency (rules conflicting with each other). This study presents a new DNA-based computing algorithm mainly based upon Adleman's DNA operations. It can be used to detect such errors. There are three phases to this molecular solution: rule-to-DNA transformation design, solution space generation, and rule verification. We first encode individual rules using relatively short DNA strands, and then generate all possible rule paths by the directed joining of such short strands to form longer strands. We then conduct the verification algorithm to detect errors. The potential of applying this proposed DNA computation algorithm to rule verification is promising given the operational time complexity of O(n*q), in which n denotes the number of fact clauses in the rule base and q is the number of rules with longest inference chain.     

DNA-based algorithms for learning Boolean formulae

We apply a DNA-based massively parallel exhaustive search to solving the computational learning problems of DNF (disjunctive normal form) Boolean formulae. Learning DNF formulae from examples is one of the most important open problems in computational learning theory and the problem of learning 3-term DNF formulae is known as intractable if RP NP. We propose new methods to encode any k-term DNF formula to a DNA strand, evaluate the encoded DNF formula for a truth-value assignment by using hybridization and primer extension with DNA polymerase, and find a consistent DNF formula with the given examples. By employing these methods, we show that the class of k-term DNF formulae (for any constant k) and the class of general DNF formulae are efficiently learnable on DNA computer.Second, in order for the DNA-based learning algorithm to be robust for errors in the data, we implement the weighted majority algorithm on DNA computers, called DNA-based majority algorithm via amplification (DNAMA), which take a strategy of ``amplifying' the consistent (correct) DNA strands. We show a theoretical analysis for the mistake bound of the DNA-based majority algorithm via amplification, and imply that the amplification to ``double the volumes' of the correct DNA strands in the test tube works well.     

旅行商问题的DNA算法

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。