首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到15条相似文献,搜索用时 171 毫秒
1.
图的最大权团的DNA计算   总被引:6,自引:0,他引:6  
马润年  张强  高琳  许进 《电子学报》2004,32(1):13-16
给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.  相似文献   

2.
李肯立  周旭  许进 《电子学报》2008,36(11):2096-2101
随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3n)减少至O(2n),改进了3-着色问题同类文献的研究结果.  相似文献   

3.
随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman—Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3^n)减少至O(2^n),改进了3-着色问题同类文献的研究结果.  相似文献   

4.
图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。  相似文献   

5.
吴雪  赵艺 《电子与信息学报》2007,29(11):2693-2697
该文基于分子生物技术提出了一种求解最大加权独立集(MWIS)问题的DNA算法.MWIS是最大独立集(MIS)的母问题,而MIS是著名的NP完全问题.该算法的关键技术是基于变长的DNA序列来对所给图中的加权顶点进行合理的编码,并在建立初始完备数据链中采用并行重叠放大(POA)技术,然后应用变性、退火、聚合酶链式反应(PCR)、酶切反应和凝胶电泳等一系列的DNA生物操作和计算生成可行解和分离出所要求的最大加权独立集.最后给出了该算法的计算机模拟仿真结果,得到了所给问题的最大加权独立集,对算法的可行性进行了验证和总结.  相似文献   

6.
DNA计算的研究进展与展望   总被引:19,自引:3,他引:16       下载免费PDF全文
高琳  许进  张军英 《电子学报》2001,29(7):973-977
DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法,它开创了以化学反应作为计算工具的先例,为NP-完全问题的解决提供了一种全新的途径,具有广阔的应用前景.DNA计算的两个主要特点是计算的高度并行性和巨大的信息存储容量.本文首先介绍了DNA计算的基本思想;然后综述了DNA算例及其模型;分析了DNA计算的特点及其与遗传算法的类比关系;指出了DNA计算目前存在的问题;最后对DNA计算的发展前景进行展望.  相似文献   

7.
基于生化反应原理的DNA计算由于在解决一类困难问题,特别是NP-完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义。利用在基于表面的DNA计算中采用荧光标记的策略,提出了一种基于DNA计算的一类特殊整数规划问题最优解的求解算法,新算法利用荧光猝灭技术,通过观察DNA分子表面的荧光来排除非解。算法分析表明,新提出的基于DNA计算的求解算法具有编码简单和错误率低等特点。  相似文献   

8.
TN4,0224 2004060525图的最大权团的D NA计算/马润年,(2}张强,(4}高琳,(3}许进(空军工程大学)11电子学报一2004,32(1)一13一16给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP一完全问题,没有非常有效的算法.1994年Adieman博士首先提出用DNA计算解决NP一完全问题,使得NP一完全问题的求解可能得到解决.文中给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据HeadT等的实验手段,文中提出的算法是有效并且可行的.…  相似文献   

9.
最小顶点覆盖问题的改进粘贴模型   总被引:2,自引:0,他引:2  
DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法。它开创了以化学 反应作为计算工具的先例,具有广阔的应用前景。本文简单回顾了DNA计算的发展,并简要介绍了分子计算的一 种模型--粘贴模型。最后我们利用粘贴模型的基本原理,运用荧光标记技术,提出了最小顶点覆盖问题的表面技 术解决方案。  相似文献   

10.
该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法.利用DNA折纸术可以构建出具有特定形状的DNA折纸结构.这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构.利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案.该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度.  相似文献   

11.
该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度。  相似文献   

12.
Channel assignment for cellular radio using simulated annealing   总被引:9,自引:0,他引:9  
The channel assignment problem, i.e. the task of assigning the channels to the radio base stations in a spectrum-efficient way, is an NP-complete optimization problem occurring during design of cellular radio systems. Previously, this problem has been solved by graph coloring algorithms. An alternative approach is presented. The problem is solved using simulated annealing, which is a general approach to combinatorial optimization. The algorithm has been successfully applied to practical radio network planning situations. One major benefit of the approach consists in the enhanced flexibility it gives to the engineer  相似文献   

13.
靳碧鹏 《电讯技术》2011,51(6):87-90
提出了一种地形分块加速绘制算法.算法递归地将地形划分为多个大小相等的地形块,通过统计地形块中目标分布的稀疏度以及无目标地形块所占的比例,寻找最优的地形分块方式.此外,提出了一种利用Diamond-Squares算法生成随机纹理,并融合顶点颜色为地形着色的方法,渲染的地形真实感强、层次分明.最后,介绍了防撞雷达三维显示中...  相似文献   

14.
建立了阅读器网络的图模型,阐述了阅读器网络拓扑结构固定和可随机改变情况下对解决阅读器冲突问题的不同要求。对于动态阅读器网络应用中的阅读器冲突问题,基于图着色方法提出了一种自适应分布式的颜色选择算法,这种算法能降低相邻阅读器冲突概率,并且使获得特定百分率的成功传输所需的总时隙数最少。  相似文献   

15.
潘理  郑红  刘显明  杨勃 《电子学报》2016,44(8):1858-1863
冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP(Non-deterministic Polynomial)完全的.提出极大冲突集动态枚举算法,该算法基于当前标识的所有极大冲突集,利用Petri网实施局部性,仅计算下一标识中受局部性影响的极大冲突集,从而避免重新枚举所有极大冲突集.该算法时间复杂度为Om2n),m是当前标识的极大冲突集数目,n是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至On2).极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号