期刊文献+
共找到36篇文章
< 1 2 >
每页显示 20 50 100
有向网络中最大容量支撑树形图扩容问题
1
作者 杨子兰 朱娟萍 杨宇 《运筹学学报(中英文)》 CSCD 北大核心 2024年第2期151-158,共8页
针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树... 针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA),采用权重差最小换弧方法设计时间复杂度为O(mn)的多项式时间算法。 展开更多
关键词 最大容量树形图 扩容 NP-困难 启发式算法 多项式时间算法
下载PDF
基于Petri网局部性的极大冲突集枚举算法 被引量:3
2
作者 潘理 郑红 +1 位作者 刘显明 杨勃 《电子学报》 EI CAS CSCD 北大核心 2016年第8期1858-1863,共6页
冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP(Non-deterministic Polynomial)完全的.提出极大冲突集动... 冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP(Non-deterministic Polynomial)完全的.提出极大冲突集动态枚举算法,该算法基于当前标识的所有极大冲突集,利用Petri网实施局部性,仅计算下一标识中受局部性影响的极大冲突集,从而避免重新枚举所有极大冲突集.该算法时间复杂度为O(m2n),m是当前标识的极大冲突集数目,n是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至O(n2).极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考. 展开更多
关键词 PETRI网 冲突集问题 NP(non-deterministic polynomial)完全性 极大冲突集枚举算法
下载PDF
原油采购-远洋运输方案模糊聚类图优化法 被引量:6
3
作者 肖文涛 徐宁 +3 位作者 刘志玲 周晓玲 王震 李启 《中国石油大学学报(自然科学版)》 EI CAS CSCD 北大核心 2017年第3期176-182,共7页
总结中国原油采购-远洋运输业务流程,分析原油采购-远洋运输方案优化问题的特殊属性。原油采购-远洋运输方案优化是包含多种高维度变量的动态-模糊组合优化的大规模NP(non-deterministic polynomial)难问题,需要多个区域业务人员根据市... 总结中国原油采购-远洋运输业务流程,分析原油采购-远洋运输方案优化问题的特殊属性。原油采购-远洋运输方案优化是包含多种高维度变量的动态-模糊组合优化的大规模NP(non-deterministic polynomial)难问题,需要多个区域业务人员根据市场和需求的动态变化协作完成,超出现有方法的解决范畴。提出模糊聚类图优化法,通过实时挖掘和利用启发性优化信息以及全局视野拼接由启发式算法所搜索到的局部静态优化方案,实现大规模原油采购-远洋运输方案的全局优化。应用结果表明,模糊聚类图优化法弥补了传统建模求解的方法的不足,充分结合了人的灵活决策优势与计算机暴力计算特点,可辅助业务人员适应原油采购-远洋运输方案优化的动态-模糊特性,通过合理调整运输任务(即调整优化模型的目标函数和限制条件)实现原油采购-远洋运输方案优化,具有较强的决策支持作用。 展开更多
关键词 原油远洋运输优化 NP难问题 差分进化算法 聚类图解法
下载PDF
Hamming距离下的最短路逆问题 被引量:2
4
作者 张斌武 王勤 《河海大学学报(自然科学版)》 CAS CSCD 北大核心 2008年第4期571-574,共4页
针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.
关键词 HAMMING距离 最短路 NP困难 多项式归约 3-SAT问题
下载PDF
受光阑限制厄米-双曲正弦-高斯光束的解析传输公式 被引量:1
5
作者 邓素辉 陶向阳 +2 位作者 刘明萍 吴峰星 葛卫国 《南昌大学学报(理科版)》 CAS 北大核心 2006年第2期183-186,共4页
从Collins公式出发,使用厄米多项式展开的方法,对厄米-双曲正弦-高斯光束(HShG)光束通过有硬边光阑限制的近轴ABCD光学系统的传输进行了研究,将其在输出面上的场分布表示成为不完全伽马函数的形式,得出解析表达式。并讨论了该光束的传... 从Collins公式出发,使用厄米多项式展开的方法,对厄米-双曲正弦-高斯光束(HShG)光束通过有硬边光阑限制的近轴ABCD光学系统的传输进行了研究,将其在输出面上的场分布表示成为不完全伽马函数的形式,得出解析表达式。并讨论了该光束的传输特性和该方法的优越性。 展开更多
关键词 厄米-双曲正弦-高斯光束 硬边光阑 厄米多项式 不完全伽马函数
下载PDF
现代物流技术中装卸工问题的拟多项式时间可解情况 被引量:10
6
作者 唐国春 《运筹与管理》 CSCD 2005年第4期15-18,共4页
装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展,促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题,本文... 装卸工问题是从现代物流技术中提出的一个实际问题,这个问题的雏形早在上个世纪60年代中国科学院数学研究所就提出和研究过。现代物流业的迅速发展,促成和推动装卸工问题的提出和研究。装卸工问题是一个新的NP困难的组合优化问题,本文研究限制情形下的装卸工问题,并证明是拟多项式时间可解的。 展开更多
关键词 运筹学 装卸工问题 NP困难 拟多项式时间可解 限制情况
下载PDF
移动通信系统中的最优功率控制算法 被引量:1
7
作者 尚松蒲 胡晓东 李旭 《应用数学》 CSCD 北大核心 2006年第1期134-138,共5页
本文研究了移动通信系统中的功率最优控制问题.我们首先将这一个工程问题转化为最大可满足线性不等式组问题的一个特殊情形,然后通过对这个组合优化问题的最优解的性质研究,给出了求解该问题的多项式时间算法.
关键词 功率控制 多项式时间算法 NP-难解问题
下载PDF
无容量限制的批处理机时间表问题 被引量:1
8
作者 刘朝晖 俞文■ 《华东理工大学学报(自然科学版)》 CAS CSCD 北大核心 2001年第4期431-433,共3页
研究无容量限制的批处理机时间表问题 ,在工件有到达时间和工期约束下 ,证明了当工件的到达时间和工期 ,或到达时间和加工时间一致单调时 ,该问题是多项式时间可解的 ;当加工时间和工期一致单调时 ,该问题是
关键词 排序 批处理机 多项式时间算法 NP困难性 到达时间 工期 加工时间 时间表问题
下载PDF
成组加工的单机延误工件个数问题 被引量:1
9
作者 刘朝晖 俞文 《华东理工大学学报(自然科学版)》 CAS CSCD 北大核心 1998年第2期235-242,共8页
证明了成组加工的单机延误工件个数问题是强NP困难的,即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期,又有相同加工时间的进一步... 证明了成组加工的单机延误工件个数问题是强NP困难的,即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期,又有相同加工时间的进一步限制情形,由于输入规模的减少,证明了其是普通意义下NP困难的。 展开更多
关键词 单机时间表 成组技术 延误工件个数 NP困难性
下载PDF
求解Hamming距离下单位型单发点树型网络最短路改进问题的算法 被引量:1
10
作者 张斌武 王勤 《河海大学常州分校学报》 2007年第4期1-4,共4页
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络... 给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法. 展开更多
关键词 HAMMING距离 最短路改进问题 NP-困难 多项式时间算法
下载PDF
基于递推分解的Torus网络可靠性研究
11
作者 黄亿海 王高才 《计算机工程与设计》 CSCD 北大核心 2009年第14期3278-3280,3309,共4页
为解决大规模Torus网络可靠度计算中遇到的NP难问题,引入递推分解和组合模型的思想对Torus网络的可靠性进行分析研究。递推分解的算法降低了计算网络可靠度的复杂性,组合模型的方法则降低了网络的结构复杂度。对于大规模的Torus网络,通... 为解决大规模Torus网络可靠度计算中遇到的NP难问题,引入递推分解和组合模型的思想对Torus网络的可靠性进行分析研究。递推分解的算法降低了计算网络可靠度的复杂性,组合模型的方法则降低了网络的结构复杂度。对于大规模的Torus网络,通过采用可靠度上下界逐步逼近的方法,可以得到较高精度的可靠度近似值。实验结果表明,在结点失效概率均小于0.10%时,对多达上千个结点的Torus网络仍超过90%的可靠度,而且提出的方法也适合其它并行体系结构网络的可靠度计算。 展开更多
关键词 TORUS网络 NP难问题 可靠度 递推分解算法 组合模型
下载PDF
两台机器流水作业中带成组加工的最大迟后问题 被引量:2
12
作者 陈跃 孙世杰 +1 位作者 宋政芳 何龙敏 《应用科学学报》 CAS CSCD 2004年第2期247-251,共5页
考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为Lmax.文中指出该问题为NP-hard后给出了其多项式可解的特例并构造了相应的动态规划算法.
关键词 排序 批处理机 最大迟后 强NP-hard 多项式可解 流水作业 成组加工
下载PDF
有不同中断时间代价的一致并行抢先调度问题 被引量:2
13
作者 周华奇 鲁鸣鸣 朱洪 《计算机研究与发展》 EI CSCD 北大核心 2005年第3期507-513,共7页
提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法,其近... 提出了具有不同中断时间代价的抢先调度问题(P|ptmn(δi)|Cmax).该问题在工程任务分配、分布式计算和网络通信等实际问题中有着广泛的应用背景.首先证明了这个问题是一个NP难优化问题.并给出了一个时间复杂度为O(nlogn)的近似算法,其近似度为5/3.算法的特点是结合中断时间δi来应用LPT思想,而不只是把它应用到任务i的执行时间pi上,从而避免了LPT算法在最坏情形下的近似度差的问题.在算法的关键部分,运用了均分的技巧来提高任务执行的并行性,进一步提高了近似度. 展开更多
关键词 调度问题 组合优化 NP NP完全 多项式时间归约 NP难
下载PDF
工件加工可拒绝的无界批量分批排序问题的几点探讨(英文) 被引量:1
14
作者 张咸昭 蔡增霞 任剑锋 《运筹学学报》 CSCD 2009年第3期23-30,共8页
本文对两个加工可拒绝的无界批量分批排序问题1|B≥n,rej|∑w_jT_j+TP和1|B≥n,rej|∑w_jU_j+TP进行了研究,对这两个问题分别给出了伪多项式时间算法和(FPTAS)近似算法.目前为止它们都是比较好的精确算法和近似算法.
关键词 运筹学 可拒绝 NP-困难 伪多项式时间 FPTAS
下载PDF
供应链管理中的一类分批调度问题 被引量:1
15
作者 朱洪利 王迅娣 张玉忠 《曲阜师范大学学报(自然科学版)》 CAS 2010年第4期41-44,共4页
研究了一类集成配送和加工的供应链调度问题.在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加工;在加工阶段,工件在批处理机上成批加工,批加工费用固定.目标函数是极小化最大完工时间和总加工费用之和.证明了该问题是NP... 研究了一类集成配送和加工的供应链调度问题.在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加工;在加工阶段,工件在批处理机上成批加工,批加工费用固定.目标函数是极小化最大完工时间和总加工费用之和.证明了该问题是NP-难的,并对该问题的一类特殊情形给出了多项式时间算法. 展开更多
关键词 分批排序 供应链调度 复杂性 NP-hard 多项式时间算法
下载PDF
求解NP难度问题的几种有效的快速算法
16
作者 杨帆 《黄山学院学报》 2006年第3期87-88,共2页
提出三种有效的快速算法——局部搜索、多空间搜索和全局搜索来解决NP难度问题。
关键词 组合优化 最优解 NP难度(NPH) 局部搜索 多空间搜索 全局搜索
下载PDF
多约束QoS路由算法综述 被引量:1
17
作者 李敏 陆芸婷 《深圳信息职业技术学院学报》 2008年第2期71-76,共6页
保证服务质量的QoS路由(Quality of Service Routing)是网络中解决QoS问题的一项关键技术。QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用。度量参数选择问题、寻路问题和路由信息不... 保证服务质量的QoS路由(Quality of Service Routing)是网络中解决QoS问题的一项关键技术。QoS路由的主要目标是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用。度量参数选择问题、寻路问题和路由信息不准确问题是QoS路由中的几个主要研究内容。多约束QoS路由算法通常是NPC问题,本文先对QoS路由中的问题进行分类,再对当前研究的一些多约束QoS路由算法进行了归纳与分析。这些算法对于在Internet中实现QoS有着重要的指导意义。 展开更多
关键词 服务质量路由(QoSR) 多约束路由 NP(non-deterministic polynomial)完全问题 多约束路由算法
下载PDF
Application of polynomial chaos on numerical simulation of stochastic cavity flow 被引量:9
18
作者 WANG XiaoDong1,2 & KANG Shun1 1 Key Laboratory of Condition Monitoring and Control for Power Plant Equipment, Ministry of Education, School of Energy Power and Mechanical Engineering, North China Electric Power University, Beijing 102206, China 2 Department of Mechanical Engineering, Vrije Universiteit Brussel, Brussels 1050, Belgium 《Science China(Technological Sciences)》 SCIE EI CAS 2010年第10期2853-2861,共9页
In present paper,the mathematic background of intrusive polynomial chaos (IPC) method and coupling process with one dimension Euler equation were introduced. The IPC method was implemented for the 2D compressible stoc... In present paper,the mathematic background of intrusive polynomial chaos (IPC) method and coupling process with one dimension Euler equation were introduced. The IPC method was implemented for the 2D compressible stochastic Navier-Stokes equations to simulate the non-deterministic behavior of a lid driven cavity flow under the influence of uncertainties. The driven velocity and fluid viscosity were supposed respectively to be the uncertain variable which has Gaussian probability distribution. Based on the validation with benchmark results,discussions were mainly focused on the statistic properties of velocity distribution. The results indicated the effect of IPC method on the simulation of propagation of uncertainty in the flow field. For the simulated results of 2D cavity flow,influence of the driven velocity uncertainty is larger than that of viscosity. 展开更多
关键词 non-deterministic polynomial CHAOS NUMERICAL simulation LID driven CAVITY flow
原文传递
西非—中国航线原油远洋运输方案优化 被引量:3
19
作者 周晓玲 王震 +1 位作者 肖文涛 许国栋 《上海海事大学学报》 北大核心 2017年第1期31-36,51,共7页
为满足西非—中国航线的原油远洋运输方案的时效性要求,以油船运费、滞期费和靠港费之和最低为目标函数,以供需平衡、港口水深和装卸时间为约束条件,求解一个包含船型组合、装/卸港航线组合、油种替换、批次拆分等多决策变量的大规模NP(... 为满足西非—中国航线的原油远洋运输方案的时效性要求,以油船运费、滞期费和靠港费之和最低为目标函数,以供需平衡、港口水深和装卸时间为约束条件,求解一个包含船型组合、装/卸港航线组合、油种替换、批次拆分等多决策变量的大规模NP(Non-deterministic Polynomial)难问题.采用差分进化算法进行求解.为提高求解速度,采用双染色体编码、基因组压缩编码、船型与拼装变量隐式联锁、配送油种比对解码等方法,进行供需平衡约束,降低问题规模,并缩减问题的"劣质解空间",提高差分进化算法的搜索时效.利用提出的算法对中国石化某月度西非—中国航线实际原油远洋运输方案进行优化,得到优化方案平均用时约5 min,可节约运费50余万美元. 展开更多
关键词 原油远洋运输 NP难问题 差分进化算法 数据降维
下载PDF
带测度函数的连通支配集问题
20
作者 马俊 朱洪 《计算机科学》 CSCD 北大核心 2006年第1期220-222,共3页
连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的 NP 完全性,并给出多项式时间的近似算法... 连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题(CDS(F)),使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的 NP 完全性,并给出多项式时间的近似算法,它的近似度为 Ln△+3(△为图中顶点的最大度数)。 展开更多
关键词 支配集问题 组合优化 NP NP完全 多项式时间归约 NP难 测度函数 支配集 连通 NP完全性 多项式时间
下载PDF
上一页 1 2 下一页 到第
使用帮助 返回顶部