期刊文献+
共找到12篇文章
< 1 >
每页显示 20 50 100
一种资源共享系统的模型和近似性能分析 被引量:21
1
作者 林闯 《计算机学报》 EI CSCD 北大核心 1997年第10期865-871,共7页
本文提出一种随机Petri网(SPN)的资源共享系统的模型,并给出了模型分解和子模型选代近似求解的两种方法:标识概率交换和平均标志个数交换.例子显示了这两种方法的有效性和相对误差.本文还证明了上述两种方法在固定点迭代... 本文提出一种随机Petri网(SPN)的资源共享系统的模型,并给出了模型分解和子模型选代近似求解的两种方法:标识概率交换和平均标志个数交换.例子显示了这两种方法的有效性和相对误差.本文还证明了上述两种方法在固定点迭代求解中,固定点解的存在.本文的复杂模型近似性能求解方法可以应用到很多复杂系统的性能分析中. 展开更多
关键词 资源共享系统 近似性能分析 PETRI网
下载PDF
(μ+λ)EA算法关于最多叶子生成树问题的近似性能
2
作者 夏小云 郭肇禄 +1 位作者 杨书新 王吉源 《江西理工大学学报》 CAS 2016年第3期91-95,共5页
为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的(μ+λ)演化算法((μ+λ)EA)在NP难的最多叶子生成树问题(MLST)上的近似性能,证明了对于最多叶子生成树问题,(μ+λ)EA算法从任意初始解出发,能够分别在... 为了更好地理解演化算法的运行机制及其在求解NP难问题上的性能,研究了基于种群的(μ+λ)演化算法((μ+λ)EA)在NP难的最多叶子生成树问题(MLST)上的近似性能,证明了对于最多叶子生成树问题,(μ+λ)EA算法从任意初始解出发,能够分别在期望多项式时间O((μ/λ)nm^2+μmlogn+n)和O((μ/λ)nm^4+μmlogn+n)内获得5和3近似比.并证明了如果选取λ>2μ,基于种群的(μ+λ)EA算法要优于基于单个个体的(1+1)EA算法. 展开更多
关键词 演化算法 最多叶子生成树问题 近似性能 运行时间分析
下载PDF
合取范式3可满足问题的局部搜索近似算法 被引量:1
3
作者 朱大铭 马绍汉 张平平 《计算机学报》 EI CSCD 北大核心 2010年第7期1127-1139,共13页
合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法... 合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sat问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+1),k4.设计解答Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+1+k(k-1)/(n-k)),k4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性. 展开更多
关键词 算法 复杂性 近似性能 可满足性 局部搜索
下载PDF
最大不全k满足问题的局部搜索近似算法
4
作者 咸爱勇 朱大铭 《计算机学报》 EI CSCD 北大核心 2015年第8期1561-1573,共13页
合取范式可满足与最大可满足问题是理论计算机科学的核心问题.最大不全满足问题是最大可满足问题的一般化.限制每个子句均含有k(≥2)个字母的最大不全满足问题又称为最大不全k满足问题.最大不全满足问题的算法进展,以解答该类问题的半... 合取范式可满足与最大可满足问题是理论计算机科学的核心问题.最大不全满足问题是最大可满足问题的一般化.限制每个子句均含有k(≥2)个字母的最大不全满足问题又称为最大不全k满足问题.最大不全满足问题的算法进展,以解答该类问题的半定规划松弛法最具代表性.关于最大不全2满足、3满足和4满足问题,目前性能最好的近似算法分别由Goemans与Williamson、Zwick、Karloff与Zwick给出,近似性能比分别为1.139(1/0.878)、1.10047(1/0.9087)和8/7.当k≥5时,最大不全k满足问题的近似算法则未曾见到.文中给出了一个解答最大不全k满足问题的局部搜索算法,近似性能比可达到2k-1/(2k-1-1),k≥2;进一步将该方法推广到解答由不少于k个字母的子句构成的最大不全k满足问题,近似性能比亦可达到2k-1/(2k-1-1).利用解答最大不全k满足问题的近似算法,给出了解答最大k可满足问题的新近似算法,近似性能比可达到2k/(2k-1).文中最后证明了若P≠NP,则k≥4的最大不全k满足问题不能近似到小于2k-1/(2k-1-1),从而说明文中解答最大不全k满足问题的算法近似性能比是最优的. 展开更多
关键词 局部搜索 算法 近似性能 合取范式 可满足性
下载PDF
蚁群优化算法的理论研究进展 被引量:35
5
作者 夏小云 周育人 《智能系统学报》 CSCD 北大核心 2016年第1期27-36,共10页
蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展,分析了其理论研究的对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。... 蚁群优化算法的理论研究有助于更好地理解算法的原理以及指导算法应用。回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展,分析了其理论研究的对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。从蚁群算法理论分析方法和研究问题类型2个方面对蚁群算法的理论研究进行综述。介绍了适应值划分、漂移分析等最基本的数学分析工具,对时间复杂性及近似性能等重要问题进行了探讨。总结比较了蚁群算法求解各类问题的性能,指出这些研究能够更加深入了解蚁群算法的运行机制。最后,探讨了目前蚁群算法理论研究中亟待解决的问题,指出引入新的分析工具以及研究更为复杂的算法模型等是值得进一步研究的方向和内容。 展开更多
关键词 蚁群优化算法 理论研究 组合优化 收敛性 时间复杂度 近似性能
下载PDF
k-median问题反向贪心随机算法 被引量:2
6
作者 王守强 《计算机科学》 CSCD 北大核心 2012年第7期232-236,共5页
k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([k... k-median问题的近似算法研究一直是计算机科学工作者关注的焦点。基于均衡限制条件,利用反向贪心策略,给出求解该问题的随机近似算法。证明该算法以较大的概率满足其近似性能比的期望值为(3+O(ln(ln(k)/α))。该算法的时间复杂度为O([kαln(k)]2(n+m)),其中n和m分别代表设施集合以及客户点集的大小。最后,通过计算机实验验证了k-median问题的反向贪心算法的实际计算效果。 展开更多
关键词 k-median 随机算法 反向贪心 近似性能
下载PDF
求解旅行商问题的嵌入遗传算子启发式算法
7
作者 陈继业 谢文平 +1 位作者 成礼智 张君 《计算机工程与应用》 CSCD 北大核心 2006年第18期43-46,共4页
算法复杂性理论中的NP完全问题是悬解的著名难题之一。旅行商问题作为经典的组合优化问题,实际中的应用非常广泛,但它却是一个NP完全问题。历年来,对它的一项主要研究工作,就是寻找一种既有高质量的解,又能快速收敛的近似算法。围绕这... 算法复杂性理论中的NP完全问题是悬解的著名难题之一。旅行商问题作为经典的组合优化问题,实际中的应用非常广泛,但它却是一个NP完全问题。历年来,对它的一项主要研究工作,就是寻找一种既有高质量的解,又能快速收敛的近似算法。围绕这项研究,本文的主要创新是:首先,设计了求解该问题的一种嵌入遗传算子的启发式算法,它在本质上是经典插入算法的改良,但同时渗透了遗传算法思想;其次,对于这种近似算法,文章阐明算法具有多项式时间界O(n3),并且给出了评价其性能的不超过2的界估计及其严格的理论证明,因而它的算法理论基础是坚实的;最后,通过两个典型的算例计算结果的对比分析表明:该近似算法较之几种常用的启发式算法,其解的质量更高,又由于插入算法的程序设计方便快捷,因而它对于实际问题的计算需求无疑是极有意义的。 展开更多
关键词 旅行商问题 环游 插入算法 遗传算子 近似算法性能
下载PDF
网络丢包环境中基于新息驱动的远程状态估计传输策略设计 被引量:1
8
作者 陆赛杰 李云骥 彭力 《传感技术学报》 CAS CSCD 北大核心 2018年第5期759-765,共7页
由于传感器节点本身携带的能量以及传输距离有限,导致其在无线传感网的应用受到了一定的限制。从降低传感器的电池功耗、延长传输距离这两点出发,针对远程状态观测设计了一种一类基于新息驱动的数据传输策略。利用增加中继节点的方法延... 由于传感器节点本身携带的能量以及传输距离有限,导致其在无线传感网的应用受到了一定的限制。从降低传感器的电池功耗、延长传输距离这两点出发,针对远程状态观测设计了一种一类基于新息驱动的数据传输策略。利用增加中继节点的方法延长了数据传输的距离,并通过该传输策略控制各节点发送数据的时间,降低整个网络的平均能耗,延长数据传输的距离。此传输策略通过推导一类近似二次性能指标的上界求解以使远程估计精度和节点的电池能耗获得最优的平衡。此外,利用该传输策略能很好地解决无线网络中发生数据丢包、数据无法传输的情况。最后,通过观测一组锂电池放电过程的实验对所提出的策略进行验证,结果表明,该策略能够很好地平衡节点的电池能耗与远程估计的性能。 展开更多
关键词 无线传感网络 数据传输策略 近似二次性能指标 状态估计
下载PDF
A Note on the Controllability of Distribution Parameter Control System 被引量:1
9
作者 石金娥 张志平 《Chinese Quarterly Journal of Mathematics》 CSCD 北大核心 2005年第4期435-437,共3页
This paper gives the relation between the precise controllabilities of two distrib-ution parameter systems.
关键词 controllability of distribution parameter system GENERATOR SEMIGROUP Yosidaapproximation
下载PDF
A nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix
10
作者 李文法 Wang Gongming +1 位作者 Ma Nan Liu Hongzhe 《High Technology Letters》 EI CAS 2016年第3期241-247,共7页
Problems existin similarity measurement and index tree construction which affect the performance of nearest neighbor search of high-dimensional data. The equidistance problem is solved using NPsim function to calculat... Problems existin similarity measurement and index tree construction which affect the performance of nearest neighbor search of high-dimensional data. The equidistance problem is solved using NPsim function to calculate similarity. And a sequential NPsim matrix is built to improve indexing performance. To sum up the above innovations,a nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix is proposed in comparison with the nearest neighbor search algorithms based on KD-tree or SR-tree on Munsell spectral data set. Experimental results show that the proposed algorithm similarity is better than that of other algorithms and searching speed is more than thousands times of others. In addition,the slow construction speed of sequential NPsim matrix can be increased by using parallel computing. 展开更多
关键词 nearest neighbor search high-dimensional data SIMILARITY indexing tree NPsim KD-TREE SR-tree Munsell
下载PDF
First-principles calculations of optical properties of Mg_2Pb 被引量:3
11
作者 DUAN YongHua SUN Yong 《Science China(Physics,Mechanics & Astronomy)》 SCIE EI CAS 2014年第2期233-238,共6页
Based on the density functional theory (DFT), the electronic structures and optical properties of Mg2Pb are calculated by using the local density approximation (LDA) and plane wave pseudo-potential method. The cal... Based on the density functional theory (DFT), the electronic structures and optical properties of Mg2Pb are calculated by using the local density approximation (LDA) and plane wave pseudo-potential method. The calculation results show that the indirect band gap width of Mg2Pb is 0.02796 eV. The optical properties of MgzPb have isotropic characteristics, the static dielectric function of Mg2Pb is ε1(0) = 10.33 and the refractive index is n0 = 3.5075. The maximum absorption coefficient is 4.8060×10^5 cm-1. The absorption in the photon energy range of 25-40 eV approaches to zero, shows the optical colorless and transparent behaviors. 展开更多
关键词 FIRST-PRINCIPLES Mg2Pb electronic structure optical properties
原文传递
Supersymmetry and SWKB Approach to Dirac Equation with Hyperbolic Scarf Potential
12
作者 N.Akbarzadeh A.Chenaghlou 《Communications in Theoretical Physics》 SCIE CAS CSCD 2016年第7期49-52,共4页
By using the supersymmetric quantum mechanics and shape invariance concept, we study the Dirac equation with the hyperbolic Scarf potential and the exact energy spectrum is obtained. Also, we calculate the bound state... By using the supersymmetric quantum mechanics and shape invariance concept, we study the Dirac equation with the hyperbolic Scarf potential and the exact energy spectrum is obtained. Also, we calculate the bound state energy eigenvalues by using the supersymmetric WKB approximation approach so that we get the same results. 展开更多
关键词 Dirac equation supersymmetric quantum mechanics supersymmetric WKB hyperbolic Scarf potential
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部