【摘 要】
:
DNA计算的海量存储和巨大并行运算能力,使其成为NP完全问题和其它难解问题的潜在解决方案之一,在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。DNA计算的特点使
论文部分内容阅读
DNA计算的海量存储和巨大并行运算能力,使其成为NP完全问题和其它难解问题的潜在解决方案之一,在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。DNA计算的特点使其在复杂的调度问题上有了新的解决方案,许多复杂的调度问题均基于难解的NP完全数学问题,DNA计算的并行运算潜力为这些调度问题提供了可能,倍受关注。另一方面,DNA计算模型尚不似传统计算机中的通用,求解一个问题的DNA计算模型或算法通常很难不作修改地用于其它类似问题的求解,因此,不管基于DNA计算的何种模型,目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入,现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。本文采用Chang等提出的DNA计算模型对于多处理机独立任务调度问题,采用粘贴模型解空间及Adleman的生物操作集合,给出了一种新的该类问题的DNA计算模型及相应的独立任务调度算法。同时本文对如何减少DNA解空间问题做了一些尝试。从电子计算机中传统并行计算和并行处理的模型出发,将传统并行处理的策略和DNA计算的特点相结合,将电子计算机并行计算中的具有普适性的分治算法设计技术应用于求解子集和问题的DNA计算中,提出一种求解子集和问题的质粒DNA算法,理论分析表明:新算法在不提高算法的时间复杂度的前提下,可将求解子集和问题所需的DNA链数从穷举算法的O(2n)减少至O(2n/2)。
其他文献
生物信息学已成为能够改变科学发展的决定性力量之一,网格计算为生物信息应用提供了强大的计算和存储平台。然而,网格应用首先需要解决服务集成、资源异构、作业管理和调度等
近些年来,人们收集数据、存储数据的能力得到了空前的提高,我们可以轻而易举地获得海量数据,在这些海量数据背后隐藏着许多重要的信息,理解它们已经远远超出了人的能力,这就
运动目标跟踪是计算机视觉研究领域的重要课题之一,也是近年来备受研究者关注的前沿方向。运动目标跟踪的目的是通过从含有运动目标的图象序列中跟踪运动目标,并对其行为进行理
随着信息加速膨胀,人们发现越来越难找到自己需要的信息。搜索引擎的诞生,在一定程度上缓解了这个矛盾。但是,搜索引擎返回的结果太多,而且有时候结果并不是用户所需要的。问
在过去的几年中,无线传感器网络迅速发展,受到工业界和学术界的普遍关注。数据聚集作为无线传感器网络的关键技术之一,能够在很大程度上减少传感器节点的通信量,节约节点的电
随着以Web服务为基础的面向服务的体系结构的发展,如何有效的联合自治的、分布的、不同功能的Web服务构建新的企业业务应用成为新的热点问题。利用Web服务组合技术,企业业务
在统计机器翻译领域,基于短语的方法是最为成熟和稳定的方法,但是目前已经很难再有改进的余地。对于语料库中曾经出现过的短语,短语模型可以给出比较准确的翻译,这种翻译包括
为了能够更好地理解互联网内部的动态行为及其相关因素,建立有效的Internet链路延迟模型意义重大。Internet链路延迟建模对于分析和预测网络性能,从而更好地完成网络协议设计
中国是地质灾害的多发国家,尤其是滑坡灾害,一旦发生降雨,一些地方就很容易发生滑坡,对人们的生命造成危害,对财产造成损失。因此,如何高效的对区域滑坡灾害进行预防,是一个
人脸识别是模式识别、计算机视觉、人工智能等领域知识的一个重要应用,也是当前热门的研究课题之一。基于主成分分析(PCA Principle Component Analysis)的Eigenfaces算法是