下载  >  开发技术  >  其它  > 论文研究-分子计算算法求解SAT问题的仿真实验 .pdf

论文研究-分子计算算法求解SAT问题的仿真实验 .pdf 评分

分子计算算法求解SAT问题的仿真实验,陈程,余文,分子计算作为一种新型的计算方式,凭借其高度的并行性和巨大的信息存储能力为NP完全问题的解决提供了全新的方法。但与电子计算机�
山国利技论文在线 http://www.paper.edu.cn 以,我们可以将衣1中每行存储在矩阵中,将矩阵这种数据结构作为运算单位实现“空间 并行性”是可行的。根据上面的基本思想,我们按照表⊥构造出以下6个1×64的矩阵: ⅹ1[000000000000000000000000000000001111111111111111…1] ⅹ2=[000000000000000011111111111111110000000000000000…1 3=[000000001111111100000000111111110000000011111111…1 X4[00001lIIo000IlI10000lIl10000ll10000Il1100001111…1 X5-[001100110011001100110011001100110011001100110011…1 X6=[010101010101010101010101010101010101010101010101…1 显然,6个1×64矩阵经过逻辑运算以后得到的仍然是一个1×64的矩阵,则这个矩阵 就是计算所得的解空间,包括了全部的64个F的值。再查找令F=1的值,这个位置所对应 的 的取值就是问题的解 通过观察,可以进一步发现算法的基础矩阵构成是有规律的,利用这些规律可以方便地 生成他们,其归纳构造特点如 (1)矩阵X规模相等,若变量个数为n,则规模为2(即12"); (2)矩阵X由周期性的0-1子串构成,其中0-1子串的形式是01(=2-,=0,1…) (3)矩阵X中0-1子串出现的周期为2,即2个01子串构成1×2的矩阵X;。 2.2.SAT问题求解实例一 上面的6变量SAT问题实例 )∧( )∧( 求解步骤: (1)用 MATLAB编程语言构造6个基础矩阵(为方便调用,集合在一个6×64的短 阵中) (2)将F的算式依据子句的顺序输入进行逻辑运算,求出问题的解空间 (3)找到鮮空門中F=1的元索位置编号,利用数制转换输岀1~。的值,即该SAT 山国武技文在线 http://wwwpaper.edu.cn 问题的解。将~6的枚举(00001看作6位二进制数的话,转换为十进制数是 0到31,而解空间矩阵元素位置编号是从1到32,与枚举区间一一对应,因此可以用转换 网数 ”来输出结果。 在用分」算法进行求解时,其实质是逐步输入子句条件进行一步步筛选,直至得到最终 的解。每个了句的逻辑运算结果与前步筛选结果的逻辑运算为¨次筛选,最后得到的解(即 F=1)是经过m次媂选得出的(本例中的m=7)。每次筛选的过程图解如下,图示的横坐标 上整数1到64代表解空间的64个可能解,纵坐标的0和1为每个可能解在筛选过稈中逻辑 运算后的F取值 T 0246810121416182022242628303234363840424446485052545658606264 图1筛选前的解的分布 山国科技论文在线 http://wwwpapercdu.cn TTTTTT °0246810121416182022242628303234363840424446485052545658606264 图2第一步输入A(ⅴ2y33)篼选后的解分布 1 0246810121416182022242628303234363840424446485052545658606264 图3第二步输入A(23√。)筛选后的解分布 山国武技论文在线 http://www.paper.edu.cn 2 1@9○ ①①○①O①①G④①①①①①①O①①O①①① 02468101214161820222426283032343638404244464850525456586)6264 图4第三步输入A(ⅴ3;√筛选后的解分布 1= 0246810121416182022242628303234363840424446485052545658606264 图5第四步输入(236)筛选后的解分布 6 山国利技论文在线 http://www.paper.edu.cn 2 10o 0 Qoo Q oo poop o0o 4 Opoooc 4o oppoopoo oo 02468101214161820222426283032343638404244464850525456586)6264 图6第五步输入∧(1ˇ2y45)筛选后的解分布 1 0246810121416182022242628303234363840424446485052545658606264 图7第六步输入^(4s。)筛选后的解分布 7 山国利技论文在线 http://www.paperedu.cn 2 ①④①○ DO OC 02468101214161820222426283032343638404244464850525456586)264 图8第七步输入~(1y26)筛选后得到最终的解空间 通过转换函数得到最后的结果: 2.3.SAT问题求解实例二 个20变量的SAT问题 3 )入(sV ∧ y5)∧ s)∧( )入( 5V17y7)∧(6√1pV13)(V9y5)A(121V14) ( s)∧ 8 中国阚技论又线 http://www.paper.edu.cn 求解步骤 (1)用 MATLAB编程语言构造20个基础矩阵 (2)将F的算式依据子句的顺序输入进行逻辑运算,求出问题的解空间; (3)找到解空间中F-1的元素位置编号,利用转换函数输出120的值。 下图是用直方图示的24步对可能解进行筛选的过程,x轴为步骤编号,y轴为筛选后 可能解的个数,最后一步筛选之后是最终解的个数(本例为1个): 筛选过程 10457初始规模 10 91704 18 14390和 14117 21370 10 E1口 计算步骤 图920变量SAT问题的筛选过程 该SAT问题最终的解只有一个:1000011011100111000 2.4.实验结果分析 通过实验过程及结果可以看出,对于变量个数为n,子句个数为m的kSAT问题,利用分 子算法的思想把矩阵作为计算单位,求出F的一共需要约(k-1)×m×(m-1)次逻辑运算, 因此,时间复杂度为O(m2),只与子句的个数相关,属于多项式级计算,而用传统的枚举 法逐个验证的算法时间复杂度为O(m*2)属于指数级运算。也就是说,通过引进空间并 行性的能有效降低时间复杂度。同时,不像DP过程算法、局部搜索算法等不能保证找出 仝部解的方法,我们的算法实验不仅得出SAT问题的最优解,还计算出了所有的解空间。既 继承了生物分子计算的优点,乂保证了结果的精确性. 山国科技论文在线 http://www.paper.edu.cn 结论 本文利用分子计算理论的基本思想,设计了可用于求解可满足性(SAT)问题的分子算 法模型。通过在 MATLAB环境下的模拟仿真,理论上达到了“以空间换时间”的并行效果, 同吋还继承了生物分了计算规模大,并行度高,能得到全部解空间的优点,验证了该方法的 合理性和可操作性。除了求解SAT问题之外,该算法还可以用于求解如0-1规划,背包问 题等其他NP问题,甚至是连续函数的极值问题。 因为算法是在现有的电子计算机环境下进行仿真实现的,并没有实现真正意义上的并行 体系结构,同时算法思想还需要进一步改进和扩大应用范围,以期为电子计算机上实现真正 的空间并行性创造理论支持。相信随着硬件设计技术的不断进步,具备分子计算优点的并行 电子计算机模型会最终实现 参考文献 [1] Adleman L. Molecular computation of solution to combinatorial problems[J]. Science, 1994, 66(11):1021-1024 [2 Richard J Lipton. DNA Solution of hard computationalproblems [. Science, 1995, 268(4): 542-545 [3] Ouyang Qi. DNA solution of the maximal clique problem[J]. Science, 1997, 278(17): 446-449 [4] Sakamoto. Molecular computation by DNA hairpin formation [J]. Science, 2000. 288(5): 1223-1226 5 Cukras R Chess games: a model for RNA based computation [J]. Biosystems, 1999, 52: 35-45 16 Davis m, Putnam II. A computing prodedure for quantitication theory[]. ACM, 1960,7: 201-215 [7 Braich R S. Chelyapov N, Johnson C, et al. Solution of a 20-variable 3-SAt problem on a DNA computer[UJ] Science,2002,296:499-502 [8]刘文斌,王淑栋,许进.可满足性(SAT)问题的几种DNA计算模型[小型微型计算机系统.2004, 25(7) [9]殷志祥,张凤月,许进.0-1规划问题的DNA计算[J.电子与信息学报,2003,25(1)

...展开详情
所需积分/C币:8 上传时间:2019-08-16 资源大小:1.22MB
举报 举报 收藏 收藏
分享 分享
论文研究-分子计算算法求解SAT问题的仿真实验 .pdf

分子计算算法求解SAT问题的仿真实验,陈程,余文,分子计算作为一种新型的计算方式,凭借其高度的并行性和巨大的信息存储能力为NP完全问题的解决提供了全新的方法。但与电子计算机�

立即下载
论文研究-主动式毫米波实时成像技术 .pdf

主动式毫米波实时成像技术,陈国平,曹清亮,近年来,恐怖分子活动频繁,人们越来越重视公共场所的安全检查。传统的安检手段已不能适应时代的需求,一种安全有效的毫米波安检��

立即下载
论文研究-Numerical Investigation on the Relationship between the Atomic Weigh and the Interface Thermal Conductivity of Aluminum/Cooper Composite Interface in Nanoscale Situation.pdf

微纳尺度下Al/Cu复合界面热导率和原子量之间关系的数值研究,葛道晗,,本文基于非平衡分子动力学法系统研究了Al/Cu界面的界面热导率,并考虑了原子迁移及不同温度下原子重力的影响。研究发现材料的界面�

立即下载
论文研究-对DHA分子光开关及其衍生物合成的研究 .pdf

对DHA分子光开关及其衍生物合成的研究,邱烨,诸葛倩,本文对DHA光开关分子的合成及其衍生物进行了研究:对传统的合成方法进行了验证及改进,合成了骨架分子2-(4-碘苯基)-8aH-薁-1,1-二��

立即下载
论文研究-基于主成分分析的荧光分子断层成像 .pdf

基于主成分分析的荧光分子断层成像,张旭,侯榆青,随着全角度非接触式成像系统的开发与应用,较大规模的多投影荧光数据能够降低荧光分子断层成像(FMT)重建问题病态性,提高重建图像�

立即下载
论文研究-基于perl语言的高分子材料玻璃化转变温度的预测方法研究 .pdf

基于perl语言的高分子材料玻璃化转变温度的预测方法研究,杨海霞,杨潞霞,为了方便快捷地使用Materials Studio分子模拟软件预测出高分子材料的玻璃化转变温度(Tg),本文在使用Materials Studio软件时引入Perl语言,�

立即下载
论文研究-Atomistic Simulation on Ion Implantation and Annealing.pdf

离子注入和退火的原子模型模拟,于民,黄如,本文开发了一个可靠高效的分子动力学低能离子注入模拟软件。软件应用了最新的物理模型和一些高效的算法。B,P,As注入的模拟结果��

立即下载
论文研究-基于源路径隔离引擎的跨域溯源扩展 .pdf

基于源路径隔离引擎的跨域溯源扩展,刘善阳,双锴,互联网于1969年产生于美军的阿帕网,在其开放性和便捷性得到迅速发展的同时,也吸引着不法分子的眼球,各种各样的网络攻击层出不��

立即下载
论文研究-Seesaw based Molecule Adders with Debugging Method$^dagger$.pdf

基于seesaw门的分子加法器电路及其调试方法,刘向荣,索娟,近年来的研究发现生物分子在构造计算模型方面有着的较大的潜力。但是由于需要考虑多种复杂而又不确定的因素(分子浓度,反应温度,�

立即下载
论文研究-MBE生长InGaAs/GaAs(001)多层矩阵式量子点 .pdf

MBE生长InGaAs/GaAs(001)多层矩阵式量子点,周清,刘珂,用分子束外延(MBE)设备以Stranski?Krastanov (S-K) 生长模式,通过间歇式源中断方式外延生长了多个周期垂直堆垛的InGaAs量子点,首次获得��

立即下载
论文研究-基于最小汉明距离译码的原核生物DNA表达效率分析 .pdf

基于最小汉明距离译码的原核生物DNA表达效率分析,初春,冯文江,基于通信系统结构,将分子生物的信息传递过程用通信模型描述,采用最小汉明距离译码的算法,分析核糖体16S rRNA的突变对原核生物DNA�

立即下载
论文研究-SiO2/Si衬底上制备增强型ZnO薄膜晶体管 .pdf

SiO2/Si衬底上制备增强型ZnO薄膜晶体管,张景文,侯洵,在NH3和O2的混合气氛下,采用激光分子束外延法(L-MBE)在SiO2/p-Si衬底上制备氮掺杂ZnO薄膜, XRD分析表明ZnO薄膜掺入微量的氮后仍有很高�

立即下载
钯催化的3,3'-螺-2-吲哚酮的合成研究

钯催化的3,3'-螺-2-吲哚酮的合成研究,胡佳,项斌,本文以Pd(OAc)2为催化剂,三叔丁基膦为配体,以NaOt-Bu为碱,通过2-吲哚酮的分子内芳基化反应,以93%的收率合成得到3,3'-螺碳环-2-吲哚酮�

立即下载
蚕丝在组织工程中的应用研究

蚕丝在组织工程中的应用研究,戴小珍,曹香朝,组织工程的核心是建立由细胞和生物材料构成的三维空间复合体, 材料在组织工程中起关键作用。蚕丝作为天然高分子材料,具备优良的�

立即下载
放射性肺纤维化小鼠肺组织蛋白质组学筛选与分析

放射性肺纤维化小鼠肺组织蛋白质组学筛选与分析,原茜,徐英,目的:为研究放射性肺纤维化发生进展过程中涉及的相关蛋白分子及信号通路。方法:(1)C57BL/6N小鼠精准定位右肺照射30Gy,建立放射�

立即下载
Ti-HMS-1分子筛的制备及其催化性能研究

Ti-HMS-1分子筛的制备及其催化性能研究,梁鹏,郑少辉,采用TS-1前驱体作为硅源和钛源,以十二胺为结构导向剂,在室温条件下合成了含微孔结构单元的纯介孔分子筛Ti-HMS-1。采用XRD、TEM、FT-IR�

立即下载
碱处理TS-1分子筛及其环己酮氨肟化反应性能研究

碱处理TS-1分子筛及其环己酮氨肟化反应性能研究,曹鹏,张军亮,本文采用TPAOH、氨水对晶粒尺寸为1μm、200nm、300nm的TS-1分子筛进行水热改性处理,考察了改性前后催化剂的环己酮氨肟化反应活性稳定性�

立即下载
可溶性PD-1分子在抗肿瘤免疫中的研究进展

可溶性PD-1分子在抗肿瘤免疫中的研究进展,陆臻桢,赵兴红,肿瘤免疫逃逸发生发展中,程序性死亡蛋白-1(Programmed Death-1, PD-1)是介导特异性T细胞抑制作用的主要负性协同刺激信号分子。近年来大量�

立即下载