期刊文献+
共找到16篇文章
< 1 >
每页显示 20 50 100
一种O(2.983^n)时间复杂度的最优联盟结构生成算法 被引量:10
1
作者 刘惊雷 张伟 +1 位作者 童向荣 张振荣 《软件学报》 EI CSCD 北大核心 2011年第5期938-950,共13页
首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低... 首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS(effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS算法时间复杂度的下界是O(2.818n),用时间序列分析方法求出了EOCS算法的上界是O(2.983n).最后,将EOCS算法与其他算法作了对比,指出无论联盟值满足何种概率分布,EOCS算法都能在O(2.983n)时间内找出最优联盟结构.Rothkopf提出的DP(dynamic programming)算法和Rahwan提出的IDP(improved dynamic programming)算法能够在O(3n)时间内求出最优联盟结构.所作的EOCS算法设计、正确性证明、时间复杂度的上下界分析都是对Rothkopf及Rahwan等人相关工作的改进和提高. 展开更多
关键词 最优联盟结构 有效二部分解 克林闭包 时间复杂度的上下界 积分极限定理 时间序列分析
下载PDF
一种根据决策树结合信息论的经典算法复杂度可能下界分析 被引量:3
2
作者 周毅敏 李光耀 《计算机科学》 CSCD 北大核心 2013年第11A期238-241,共4页
计算机算法是电子计算机诞生时同时出现的产物。有时甚至认为算法比现代计算机出现得更早。为解决具体问题,出现了各种各样的算法。算法的时间复杂度是算法实现中最关心的问题之一。然而,面对一个问题,是否存在一个算法复杂度不可逾越... 计算机算法是电子计算机诞生时同时出现的产物。有时甚至认为算法比现代计算机出现得更早。为解决具体问题,出现了各种各样的算法。算法的时间复杂度是算法实现中最关心的问题之一。然而,面对一个问题,是否存在一个算法复杂度不可逾越的界限以及如何确定这个界限却不常作为一个值得研究的问题受到重视。针对这个问题,提出了一个基于决策树和信息论的分析方法来对一些经典算法建模并分析这些算法的时间复杂度可能达到的下界是什么,以及如何计算这个下界等。所提计算方法是真实可行的,对列出的一些经典算法是有效的,并能够应用到其它一些文中未列出的算法中。 展开更多
关键词 算法 时间复杂度 决策树 信息论 下界
下载PDF
CP-nets学习的复杂度 被引量:3
3
作者 刘惊雷 廖士中 《计算机科学》 CSCD 北大核心 2018年第6期211-215,共5页
CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CPnets表示的偏好公式之间的联系,将... CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CPnets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。 展开更多
关键词 二值条件偏好网 推理与学习 命题公式的可满足性 有界树宽的CP-nets 复杂度的上下界
下载PDF
时滞反应扩散方程有界解周期解的存在唯一性 被引量:3
4
作者 王长有 胡晓红 《重庆邮电学院学报(自然科学版)》 2005年第5期644-646,共3页
利用上、下解方法及相应的单调迭代方法研究了一类反应项非单调的时滞反应扩散方程,构造了非单调反应项的上、下控制函数,并证明了所构造的函数满足L ipsch itz条件及单调性,克服了反应项非单调无法利用单调迭代方法的局限性。为讨论反... 利用上、下解方法及相应的单调迭代方法研究了一类反应项非单调的时滞反应扩散方程,构造了非单调反应项的上、下控制函数,并证明了所构造的函数满足L ipsch itz条件及单调性,克服了反应项非单调无法利用单调迭代方法的局限性。为讨论反应项非单调的微分方程提供了一种有效方法,并获得了此方程解的有界性及周期解存在唯一性的充分条件,推广了已有的一些结果。 展开更多
关键词 时滞 有界解 周期解 上下解 反应扩散方程
下载PDF
一种简单多边形凸包的新线性算法 被引量:10
5
作者 刘润涛 《工程图学学报》 CSCD 2002年第2期120-126,共7页
给出了一个计算简单多边形凸包的新算法。其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度。该算法具有线性时间复杂度和空间复杂度。同时,具体量化了该算法的复杂度,给出了该... 给出了一个计算简单多边形凸包的新算法。其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度。该算法具有线性时间复杂度和空间复杂度。同时,具体量化了该算法的复杂度,给出了该算法的时间复杂度和空间复杂度的确定的上界,即,时间复杂度为不超过4(n-4)次乘法、6(n-4)次减法和17n-12次比较运算,空间复杂度为不超过2n个存储单元(n是该简单多边形顶点的个数)。 展开更多
关键词 线性算法 简单多边形 凸包 计算几何 时间复杂度 空间复杂度
下载PDF
股票价格模型中三个指标的概率计算 被引量:3
6
作者 张丕一 《青岛理工大学学报》 CAS 2006年第5期119-123,共5页
在假定股票价格变动服从几何布朗运动的模型下,利用微分方程初值问题与随机过程的联系,将要计算的概率问题转化为微分方程问题.在已知现在的股票价格情况下,通过求解微分方程,计算了股票价格到达给定的上、下限的概率和平均到达的时间.... 在假定股票价格变动服从几何布朗运动的模型下,利用微分方程初值问题与随机过程的联系,将要计算的概率问题转化为微分方程问题.在已知现在的股票价格情况下,通过求解微分方程,计算了股票价格到达给定的上、下限的概率和平均到达的时间.此外,给出了一个有具体数据的例子,说明了上述结果可以直接应用到实际股票投资决策之中. 展开更多
关键词 几何布朗运动 上、下限 数学期望 随机微分方程 停时
下载PDF
华罗庚不等式的上界与下界的研究 被引量:1
7
作者 杨忠鹏 《厦门大学学报(自然科学版)》 CAS CSCD 北大核心 2007年第3期297-301,共5页
在多复变分析的研究中,华罗庚发现并证明了行列式不等式det(I-AAH)det(I-BBH)≤|det(I-ABH)|2,其中n×n复矩阵A,B满足I-AAH,I-BBH都是Hermitian正定矩阵.本文从一个矩阵恒等式的应用出发,给出了较为精细的华罗庚不等式的新的上界和... 在多复变分析的研究中,华罗庚发现并证明了行列式不等式det(I-AAH)det(I-BBH)≤|det(I-ABH)|2,其中n×n复矩阵A,B满足I-AAH,I-BBH都是Hermitian正定矩阵.本文从一个矩阵恒等式的应用出发,给出了较为精细的华罗庚不等式的新的上界和下界:det(I-AAH)det(I-BBH)+|det(A-B)|2+(2n-2)|det(A-B)|[det(I-AAH)det(I-BBH)]21≤|det(I-ABH)|2≤det(I+AAH)det(I+BBH)+(22n-1-2n+1+1)|det(A+B)|2-(2n-2)|det(A+B)[(22(n-1)-2n)|det(A+B)|2+det(I+AAH)det(I+BBH)]21. 展开更多
关键词 矩阵恒等式 Hermitian正定矩阵 行列式不等式 上界 下界
下载PDF
基于分支回溯的NAE-3SAT问题求解算法
8
作者 谷文祥 傅琳璐 +1 位作者 周俊萍 姜蕴晖 《智能系统学报》 北大核心 2012年第6期506-511,共6页
NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效... NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目. 展开更多
关键词 NAESAT NAE-3SAT 时间复杂性 NAE-3SAT问题上界 变量数目 分支回溯
下载PDF
一类修正Navier-Stokes方程解衰减速率的上下界估计
9
作者 吴珞 《上海第二工业大学学报》 2010年第3期173-177,共5页
Navier-Stokes方程描述了具有小速度梯度的不可压缩粘性流体运动规律,在流体动力学研究中有着重要的应用。1966年,Ladyzhenskaya O.A.放弃了速度梯度很小的限制,提出了几种描述不可压缩粘性流体运动规律的修正Navier-Stokes方程。为估... Navier-Stokes方程描述了具有小速度梯度的不可压缩粘性流体运动规律,在流体动力学研究中有着重要的应用。1966年,Ladyzhenskaya O.A.放弃了速度梯度很小的限制,提出了几种描述不可压缩粘性流体运动规律的修正Navier-Stokes方程。为估计整个三维空间上一类修正Navier-Stokes方程解衰减速率的上下界,使用改进的Fourier分解方法得到当初值u0∈Lp(1≤p<2)时,解的L2模衰减速率上界为(t+1)-3/2(1/p-1/2);对某些初值u0∈Lp(1≤p<97)时,解的L2模衰减速率下界为34(t+1)-3/4。 展开更多
关键词 修正Navier-Stokes 大时间行为 衰减率 上界 下界
下载PDF
具有Markov链利率的风险模型的破产研究 被引量:4
10
作者 孙华斌 孙勇 《科学技术与工程》 2010年第24期5976-5980,共5页
在随机利率服从Markov链下,建立起带随机利率的离散风险过程模型。重点探讨了破产前后盈余的情况。分别给出了破产前一刻盈余和破产赤字的分布的积分表达式。由此推导得出最终破产概率的积分表达式。最后讨论了在利率为非负情况下破产... 在随机利率服从Markov链下,建立起带随机利率的离散风险过程模型。重点探讨了破产前后盈余的情况。分别给出了破产前一刻盈余和破产赤字的分布的积分表达式。由此推导得出最终破产概率的积分表达式。最后讨论了在利率为非负情况下破产概率的一个上界,改进已往的结论,并且对利率为0≥Ii>-1情况下给出了最终破产概率的下界。 展开更多
关键词 离散时间风险模型 MARKOV链 破产概率 鞅方法 上下界
下载PDF
利用时滞分割的方法研究系统的稳定性 被引量:1
11
作者 谢涛 钟守铭 《西南民族大学学报(自然科学版)》 CAS 2015年第4期485-488,共4页
研究了带有时变时滞的神经网络系统,通过构造新的Lyapunov-Krasovslii泛函,利用时滞的分割方法,倒凸不等式,Schur定理和添加自由权矩阵等方法,依据Lyapunov稳定理论,用线性矩阵不等式的形式,建立了系统的平衡点是渐近稳定的新标准,最后... 研究了带有时变时滞的神经网络系统,通过构造新的Lyapunov-Krasovslii泛函,利用时滞的分割方法,倒凸不等式,Schur定理和添加自由权矩阵等方法,依据Lyapunov稳定理论,用线性矩阵不等式的形式,建立了系统的平衡点是渐近稳定的新标准,最后通过实验证明了新标准可以更好的降低了已有结果的保守性. 展开更多
关键词 时滞 神经网络系统 Lyapunov-Krasovslii泛函 倒凸不等式
下载PDF
基于自行车共享系统静态再平衡问题的分支定界算法 被引量:2
12
作者 王天宇 韩印 夏晓梅 《物流科技》 2018年第11期73-77,共5页
自行车共享系统是一种交通系统,允许用户在分散在城市各处的众多自动租车点之一租用一辆自行车,使用它们进行短途旅行,并在任何站点返回。良好的服务质量是建立在再平衡操作基础上完成的,具体形式表现在将自行车从一些车站移走,并将它... 自行车共享系统是一种交通系统,允许用户在分散在城市各处的众多自动租车点之一租用一辆自行车,使用它们进行短途旅行,并在任何站点返回。良好的服务质量是建立在再平衡操作基础上完成的,具体形式表现在将自行车从一些车站移走,并将它们转移到其他车站。为了提高服务质量,研究了静态情况下的再平衡车辆路径问题,即车辆在各车站之间进行往返,以将其返回到所期望的站点,而且每一个站只能访问一次。这个问题类似于有额外限制出行的推销员的问题。其目的是找到一种最优的车辆调度方法,使车站在不平衡状态下的总等待时间最小化。首先建立相关模型,提出使用下界和上界。这些边界用于分支定界算法进行计算,得出最优解。为了验证方法可行性,对大量实例进行了计算实验,得到的结果表明了该方法的有效性。 展开更多
关键词 自行车共享系统 车辆调度 等待时间 下界和上界 分支定界算法
下载PDF
一类带有变指数非局部项的反应扩散方程解的爆破行为 被引量:1
13
作者 田娅 秦瑶 向晶 《应用数学和力学》 CSCD 北大核心 2022年第10期1177-1184,共8页
该文考虑了一类带有变指数非局部项的反应扩散方程的爆破问题.首先,由不动点原理,证明了问题解的局部存在性和唯一性.其次,利用上下解方法,给出在齐次Dirichlet边界条件下,问题的解在有限时间发生爆破的充分条件,即变指数大于零且初始... 该文考虑了一类带有变指数非局部项的反应扩散方程的爆破问题.首先,由不动点原理,证明了问题解的局部存在性和唯一性.其次,利用上下解方法,给出在齐次Dirichlet边界条件下,问题的解在有限时间发生爆破的充分条件,即变指数大于零且初始值足够大,并对爆破时间的上下界进行了估计. 展开更多
关键词 非局部项 变指数 有限时间爆破 爆破时间上下界
下载PDF
面向时间依赖路网的空间索引方法 被引量:1
14
作者 李佳佳 臧寅旭 +2 位作者 刘向宇 夏秀峰 朱睿 《计算机工程》 CAS CSCD 北大核心 2019年第5期127-134,共8页
在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与... 在兴趣点(POI)呈稀疏分布时,现有时间依赖路网中的k近邻查询方法效率较低,且无法高效支持多类型的POI查询。为此,建立基于POI分布的空间索引结构TDG。根据路径权值上、下界对预计算路径进行剪枝优化,在此基础上,提出一种索引更新策略与基于TDG的k近邻查询算法。实验结果表明,与启发式查询算法相比,该算法的扩展节点数量平均减少87.5%,查询响应时间平均缩短33%~66%。 展开更多
关键词 时间依赖路网 多类型POI 网格划分 上、下界剪枝 K近邻查询
下载PDF
非局部边界条件下的反应扩散方程的爆破解
15
作者 岳丽霞 《兰州文理学院学报(自然科学版)》 2021年第5期1-6,共6页
研究Neumann非局部边界条件下具有梯度反应项的反应扩散方程的爆破解,利用构造适当的辅助函数和微分不等式技巧相结合的方法,证明了解的存在性,并得到了解发生爆破的条件以及爆破时间的上下界.
关键词 反应扩散方程 非局部边界条件 爆破时间的上下界
下载PDF
Alleviating limit cycling in training GANs with an optimization technique 被引量:1
16
作者 Keke Li Liping Tang Xinmin Yang 《Science China Mathematics》 SCIE CSCD 2024年第6期1287-1316,共30页
In this paper,we undertake further investigation to alleviate the issue of limit cycling behavior in training generative adversarial networks(GANs)through the proposed predictive centripetal acceleration algorithm(PCA... In this paper,we undertake further investigation to alleviate the issue of limit cycling behavior in training generative adversarial networks(GANs)through the proposed predictive centripetal acceleration algorithm(PCAA).Specifically,we first derive the upper and lower complexity bounds of PCAA for a general bilinear game,with the last-iterate convergence rate notably improving upon previous results.Then,we combine PCAA with the adaptive moment estimation algorithm(Adam)to propose PCAA-Adam,for practical training of GANs to enhance their generalization capability.Finally,we validate the effectiveness of the proposed algorithm through experiments conducted on bilinear games,multivariate Gaussian distributions,and the CelebA dataset,respectively. 展开更多
关键词 GANs general bilinear game predictive centripetal acceleration algorithm lower and upper complexity bounds PCAA-Adam
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部