首页 | 本学科首页   官方微博 | 高级检索  
检索     
共有20条相似文献,以下是第1-20项 搜索用时 171 毫秒

1.  一种基于分治的三维匹配问题DNA计算算法  
   周旭  李肯立  乐光学  杨志邦《电子学报》,2010年第38卷第8期
    本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间,提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略,提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从O(2n)减少至O(2n/2)≈O(1.414n),同时生物操作数由O(n2)减少至O(15n+30q),测试试管数由所需的O(n)减少至O(1),最大链长由O(15n+45q)减少至O(15n/2+45q).因此,本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(267≈1022)提高到134(67×2=134).同时,与传统的穷举搜索算法相比,该算法具有高效的空间利用率及容错技术的优点.    

2.  RP(k)网络上Hypercube通信模式的波长指派算法  被引次数:12
   刘方爱  刘志勇  乔香珍《软件学报》,2003年第14卷第3期
   波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2n个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.    

3.  模糊聚类计算的最佳算法  被引次数:14
   马军  邵陆《软件学报》,2001年第12卷第4期
   给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n2).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n3logn)计算时间相比,新算法至少降低了O(n    

4.  无向图的边极大匹配并行算法及其应用*  
       岩间一雄  顾谦平《软件学报》,1999年第10卷第1期
   在EREW PRAM(exclusive-read and exclusive-write parallel random access machine)并行计算模型上,对范围很广的一类无向图的边极大匹配问题,给出时间复杂性为O(logn),使用O((n+m)/logn)处理器的最佳、高速并行算法.    

5.  背包问题的最优并行算法  被引次数:12
   李庆华  李肯立  蒋盛益  张薇《软件学报》,2003年第14卷第5期
   利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-ε个并行处理机单元,0≤ε≤1,O(2n/2)个存储单元,在O(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.    

6.  一类实际网络中的最小截算法  被引次数:9
   张宪超  万颖瑜  陈国良《软件学报》,2003年第14卷第5期
   讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n2logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.    

7.  Multi-log2N交换网络的性能分析模型及控制算法  
   刘晓锋  赵有健  吴亚娟《软件学报》,2013年第24卷第3期
   高速多平面交换网络解决了其内部冲突问题,但需要相应的路由控制算法的辅助,否则,内部冲突不能彻底解决.这是因为包在输入级路由平面的选择不够恰当,容易导致路由冲突的产生.因此,根据冲突链路集的思想,给出一种Multi-log2N交换网络的控制算法.该算法控制分组在路由平面间的选择,不仅能够适用于RNB和SNB,还能实现单播和多播的控制,保障Multi-log2N完全实现无阻塞.另一方面,Multi-log2N消除了内部的链路冲突,提高了交换速率,但对其交换性能缺乏系统的理论分析.给出一种基于嵌入式马尔可夫链的分析模型,对Multi-log2N网络中队列的使用及分组在队列中的平均等待时间、平均队长等相关性能指标进行了系统的分析,为基于Multi-log2N的光交换节点的设计提供了良好的理论依据.    

8.  盾构隧道施工期间土体沉降计算分析  
   刘 阳  任 青  喻孟初  颜 超  马荣全《水资源与水工程学报》,2017年第28卷第1期
   对重塑饱和砾质黏土进行室内动三轴试验。综合考虑土体固结围压、循环荷载幅值、加载频率3种因素共同作用下的循环累积塑性变形模型和循环累积孔压模型;基于试验结果讨论了应变沉降指数b值与孔压沉降系数Nβ值随着循环次数的变化规律。试验结果表明:前10000次循环b值与Nβ值的变化较大,且在前1000次变化最为显著;随着循环次数增加,b值呈现出递减的规律,而Nβ与之相反;十万级循环次数下b值与Nβ值逐渐趋于稳定。对某隧道区间进行施工沉降计算发现与实测沉降范围吻合较好;建议施工期间的土体沉降预测根据循环加载的次数来确定b值与Nβ值,预测隧道的长期沉降时取稳定后的b值与Nβ值计算。研究成果为预测隧道施工期间土体沉降提供了具有价值的参考。    

9.  半动态矩形交查询算法  
   高静波  李新友  唐泽圣  周晓辉《软件学报》,1997年第8卷第8期
   本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法,它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O(logMk′),更新时间复杂度是O(logMlogn),空间复杂度是OnlogM/).二维查询算法的查询时间复杂度是O(log2Mk),更新时间复杂度是O(log2Mlogn),空间复杂度是Onlog2M).本文分别实现了这两个算法,通过对它们的性能进行比较,发现一维查询算法是一种高效、实用的算法.    

10.  人工渠道糙率系数影响因素的试验研究  
   拜亚茹  赵锦程  邱秀云  赵 涛《水资源与水工程学报》,2014年第25卷第4期
   通过物理模型试验资料分析,探讨了矩形渠道的糙率与渠道水深、弗汝德数的变化规律。分析得出:当底坡不变时,随着弗汝德数Fr的增大,糙率n值逐渐减小。在缓流渠道中,渠道糙率n随弗汝德数Fr变化的速率很快;在急流渠道中,渠道糙率n值随弗汝德数Fr的速率较慢。糙率系数n随水深h的变化关系与流态有关。缓流中,随着水深h的增大,糙率n值减小;急流中,当弗汝德数1<Fr<1.51时,糙率n值先是随着水深h的增大而减小,达到某一值后再随水深h的增大而增大;当弗汝德数Fr>1.51时,糙率系数n随水深h的增大而增大。    

11.  背包类问题的并行O(25n/6)时间-空间-处理机折衷  
   李肯立  赵欢  李仁发  李庆华《软件学报》,2007年第18卷第6期
   将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.    

12.  PRAM和LARPBS模型上有向序列翻转距离并行算法  
   沈一飞  陈国良  张强锋《软件学报》,2007年第18卷第11期
   分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn).    

13.  矩阵条件数及高斯算法平滑分析的进一步研究  被引次数:1
   杨智应  朱洪  宋建涛《软件学报》,2004年第15卷第5期
   算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ2≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og2(n)+3log2(1/σ)+log2log2n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og2n+3log2(1/σ)+4√2+log2n+log2(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n2)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og2n+3log2(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.    

14.  RNA二级结构预测中动态规划的优化和有效并行  被引次数:6
   谭光明  冯圣中  孙凝晖《软件学报》,2006年第17卷第7期
   基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n4)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n2×k2)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n3)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.    

15.  用擂台赛法则构造多目标Pareto最优解集的方法  被引次数:14
   郑金华  蒋浩  邝达  史忠植《软件学报》,2007年第18卷第6期
   针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0m/N<1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN2)和O(Nlog(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.    

16.  一种基于拓扑势的网络社区发现方法  被引次数:12
   淦文燕  赫南  李德毅  王建民《软件学报》,2009年第20卷第8期
   从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n3/γ)~O(n2),n为网络节点数,m为边数,2<γ<3为一个常数.    

17.  基于改进PSO-BP神经网络的冰蓄冷空调冷负荷动态预测模型  
   杨熊  于军琪  郭晨露  华宇剑  赵安军《重庆建筑大学学报》,2019年第41卷第1期
   当前多数冰蓄冷空调冷负荷动态预测方法中,由于模型输入变量与输出结果相关性差、信息冗余度高等原因,导致多数预测模型在预测精度和收敛速度方面都未达到理想的预测效果,因此,提出一种改进的PSO-BP神经网络算法预测大型公共建筑的冷负荷。对于输入变量与输出结果采用灰色关联度分析,消除样本输入变量对数的耦合性,确定影响冰蓄冷空调系统冷负荷的关键性因素,将其作为输入变量,预测冰蓄冷空调系统动态冷负荷。结果表明:T时刻室外空气温度、T-1 h时刻室外空气温度、T时刻室外空气湿度、T时刻太阳辐射强度、T-1 h时刻太阳辐射强度、T-1 h时刻空调冷负荷是影响T时刻冰蓄冷空调系统冷负荷的关键因素,并以此作为预测模型的输入变量。相对于传统PSO-BP神经网络全输入变量预测算法,该模型预测结果精确度更高、收敛速度更快。    

18.  基于改进PSO-BP神经网络的冰蓄冷空调冷负荷动态预测模型  
   杨熊  于军琪  郭晨露  华宇剑  赵安军《土木建筑与环境工程》,2019年第41卷第1期
   当前多数冰蓄冷空调冷负荷动态预测方法中,由于模型输入变量与输出结果相关性差、信息冗余度高等原因,导致多数预测模型在预测精度和收敛速度方面都未达到理想的预测效果,因此,提出一种改进的PSO-BP神经网络算法预测大型公共建筑的冷负荷。对于输入变量与输出结果采用灰色关联度分析,消除样本输入变量对数的耦合性,确定影响冰蓄冷空调系统冷负荷的关键性因素,将其作为输入变量,预测冰蓄冷空调系统动态冷负荷。结果表明:T时刻室外空气温度、T-1 h时刻室外空气温度、T时刻室外空气湿度、T时刻太阳辐射强度、T-1 h时刻太阳辐射强度、T-1 h时刻空调冷负荷是影响T时刻冰蓄冷空调系统冷负荷的关键因素,并以此作为预测模型的输入变量。相对于传统PSO-BP神经网络全输入变量预测算法,该模型预测结果精确度更高、收敛速度更快。    

19.  有中断时间代价的一致并行机抢先调度问题  被引次数:1
   孙广中  陈国良  许胤龙  顾钧《软件学报》,2002年第13卷第8期
   提出了一种具有中断时间代价的抢先调度问题(P|ptmn(δ)|Cmax):在抢先调度中,一个任务发生一次中断,其总的执行时间会增加一个δ.该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.证明了这是一个NP-hard问题,给出了一个时间复杂度为O(nlogn+m)的脱线近似算法LPT-Wrap,其近似比小于等于1.40825,并分析了P|ptmn(δ)|Cmax的在线特性,给出一个线性时间复杂度的在线近似算法,其竞争比为2.    

20.  确定任意多边形凸凹顶点的算法  被引次数:21
   周培德《软件学报》,1995年第6卷第5期
   本文提出一种确定任意多边形凸凹顶点的算法.该算法的时间复杂性为O(n2logn)次乘法和O(n2)次比较.    

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

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