期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到110篇文章
< 1 2 … 6 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
用启发式贪心法求解旅行商问题 被引量：19
1
作者 潘立登 黄晓峰 《北京化工大学学报（自然科学版）》 CAS CSCD 1998年第2期46-51,共6页
旅行商问题是ＮＰ完全的组合优化问题。分析了邻域启发式算法的基本操作，提出一种简单的启发式贪心法，仅利用城市间的距离信息求解旅行商问题。理论分析与实验结果表明该方法是确定性的多项式时间算法。对５个不同规模的典型的旅行商... 旅行商问题是ＮＰ完全的组合优化问题。分析了邻域启发式算法的基本操作，提出一种简单的启发式贪心法，仅利用城市间的距离信息求解旅行商问题。理论分析与实验结果表明该方法是确定性的多项式时间算法。对５个不同规模的典型的旅行商问题进行优化，均达到或优于文献中的结果。 展开更多
关键词 旅行商问题 启发式算法 贪心法 TSP 求解
下载PDF
寻求中国货郎担问题最短回路的多项式时间算法 被引量：9
2
作者 周培德 周忠平 张欢 《北京理工大学学报》 EI CAS CSCD 2000年第2期201-204,共4页
研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货... 研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货郎担问题存在多项式时间算法求得最短回路．所设计的算法的时间复杂性为O（n2lbn），将它用于中国货郎担问题，得到一条长度为15404km的最短回路．与陈沐天等人采用几何分块方法所得的最短回路相一致． 展开更多
关键词 中国货郎担问题 最短回路 多项式时间算法
下载PDF
旅行商问题基于参考点的相邻插入法及其改进 被引量：7
3
作者 童行行 王凌 何京芮 《计算机工程与应用》 CSCD 北大核心 2002年第20期63-65,共3页
旅行商问题(Traveling Salesman Prblem,TSP)是典型的 NP-hard 问题。通过对已有以最近插入法为代表的构造性算法的分析,提出了一种具有多项式时间性能的基于参考点的相邻插入法及其改进策略,其时间复杂度分别为O(n2)和O(n3),同时基于... 旅行商问题(Traveling Salesman Prblem,TSP)是典型的 NP-hard 问题。通过对已有以最近插入法为代表的构造性算法的分析,提出了一种具有多项式时间性能的基于参考点的相邻插入法及其改进策略,其时间复杂度分别为O(n2)和O(n3),同时基于典型算例的仿真研究验证所提出算法的有效性和高效性。 展开更多
关键词 旅行商问题 参考点 相邻插入法 构造性算法 多项式时间算法
下载PDF
判定有限域上不可约多项式及本原多项式的一种高效算法 被引量：5
4
作者 王鑫 王新梅 韦宝典 《中山大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第1期6-9,共4页
提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效的确定性算法。分析了多项式次数与其不可约因式之间的内在联系,给出了有限域上任意n次多项式是否为不可约多项式、本原多项式的一个充要条件。通过利用欧几里得... 提出了一个判定有限域上任一多项式是否为不可约多项式、本原多项式的高效的确定性算法。分析了多项式次数与其不可约因式之间的内在联系,给出了有限域上任意n次多项式是否为不可约多项式、本原多项式的一个充要条件。通过利用欧几里得算法,该判定仅需做O((log2n)n3)次域上乘法,属于多项式时间,易于硬件实现。为扩频通信与序列密码寻找和利用不可约多项式构造线性反馈移位寄存器提供了一种有效算法。 展开更多
关键词 有限域 不可约 本原 多项式时间算法 扩频通信 序列密码
下载PDF
有向网络中最大容量支撑树形图扩容问题
5
作者 杨子兰 朱娟萍 杨宇 《运筹学学报（中英文）》 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
多共同工期分配调度问题算法研究
6
作者 包晗 吕丹阳 王吉波 《重庆师范大学学报（自然科学版）》 CAS 北大核心 2024年第1期8-13,共6页
为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该... 为确定所有工件的多个共同工期以及工件的最优调度序列,最小化提前惩罚、延误惩罚和公共工期分配的加权和,利用位置权重与处理时间的匹配过程来获得最优解。对此问题给出了最优解满足的性质,当分配给共同工期的工件个数为给定常数时该问题可解。该问题是多项式可解的,并给出了具体求解算法。 展开更多
关键词 调度 提前/延误惩罚 多项式时间算法 单机 多共同工期
原文传递
求解线性规划的几种方法 被引量：5
7
作者 雍龙泉 《江西科学》 2007年第2期202-205,212,共5页
线性规划是运筹学中应用最广泛的一个分支,详细地分析了线性规划的非多项式算法和多项式算法;给出了求解线性规划问题常用的数学软件,并对这些软件做了介绍。最后给出了线性规划问题的原-对偶内点算法,数值实验表明该算法具有很好的收... 线性规划是运筹学中应用最广泛的一个分支,详细地分析了线性规划的非多项式算法和多项式算法;给出了求解线性规划问题常用的数学软件,并对这些软件做了介绍。最后给出了线性规划问题的原-对偶内点算法,数值实验表明该算法具有很好的收敛性与稳定性。 展开更多
关键词 线性规划 多项式算法 数学软件 原一对偶内点算法
下载PDF
OEM业务的Stackelberg博弈策略与算法 被引量：4
8
作者 宿洁 《计算机工程与应用》 CSCD 北大核心 2008年第21期227-230,共4页
随着经济全球化的发展和经济的区域化分工,OEM合作已成为一种重要的企业间生产方式。通过分析OEM业务中委托方和被委托方的决策行为及双方关系,建立OEM业务的Stackelberg博弈策略模型,并研究求解算法。首先,分析OEM业务中的委托方和被... 随着经济全球化的发展和经济的区域化分工,OEM合作已成为一种重要的企业间生产方式。通过分析OEM业务中委托方和被委托方的决策行为及双方关系,建立OEM业务的Stackelberg博弈策略模型,并研究求解算法。首先,分析OEM业务中的委托方和被委托方各自的决策行为;进而以此为基础,建立OEM业务的Stackelberg博弈策略模型。最后,利用双层规划的对偶理论,给出求解OEM业务最优策略的一种多项式时间算法。 展开更多
关键词 OEM业务 STACKELBERG博弈 双层规划 多项式时间算法
下载PDF
一类框式凸规划的原始 -对偶内点算法 被引量：4
9
作者 王浚岭 张明望 《应用数学》 CSCD 2000年第1期89-93,共5页
本文为框式约束的一类凸规划提出了一个新的内点算法 ,原始 -对偶路径跟踪法 。
关键词 凸规划 框式约束 内点算法 多项式算法
下载PDF
三台带两个服务等级的平行机排序问题算法研究
10
作者 吴兆蕊 陈智斌 王扬 《陕西理工大学学报（自然科学版）》 2023年第1期67-72,共6页
研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设... 研究了带两个服务等级的平行机排序问题,其中等级为1的机器有2台,等级为2的机器只有1台。每个工件和每台机器等级均为1或2,只有当工件等级不低于机器等级时,才能将工件安排到机器上加工,目标为极小化最大完工时间。针对该NP-难问题,设计了一个近似比严格小于3/2的新算法,改进了已知结果。同时,在加工时间满足2的幂次方条件下,设计了一个新算法,并证明了该算法总能得到一个最优分配。 展开更多
关键词 排序问题 服务等级 多项式时间算法 近似算法
下载PDF
AKS算法及关于它的一种改进算法的实现分析 被引量：3
11
作者 朱文余 《四川大学学报（自然科学版）》 CAS CSCD 北大核心 2005年第3期459-466,共8页
2002年,Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题.他们给出了一个算法(简称AKS算法),该算法对输入整数是素数还是合数进行判断,它是一个确定的多项式时间算法.后来许多科学家对该算法进行了改进,其中... 2002年,Agrawal、Kayal和Saxena成功地解决了多项式时间判别素数这一著名的世界难题.他们给出了一个算法(简称AKS算法),该算法对输入整数是素数还是合数进行判断,它是一个确定的多项式时间算法.后来许多科学家对该算法进行了改进,其中一个比较好的改进是由Bernstein给出的(简称Bernstein算法).作者详细分析了这两种算法,利用C语言实现了这两种算法,并进行了比较,找出了真正需要用到AKS算法和Bernstein算法来判断其为素数和合数的最小数,并估计出所需要的运行时间. 展开更多
关键词 素数 合数 素数判定 多项式时间算法
下载PDF
具有最大作业延迟的生产调度优化算法及仿真 被引量：4
12
作者 王秀利 吴惕华 刘磊 《计算机仿真》 CSCD 2003年第6期40-42,共3页
成组作业优化调度问题中的作业根据其加工特点要求可分成若干作业类。同一类的作业连续加工 ,其后的作业不需要机器设置花费 ,而不同类的作业连续加工 ,其后的作业需要机器设置花费。当优化目标是最大作业延迟时 ,单机成组作业优化调度... 成组作业优化调度问题中的作业根据其加工特点要求可分成若干作业类。同一类的作业连续加工 ,其后的作业不需要机器设置花费 ,而不同类的作业连续加工 ,其后的作业需要机器设置花费。当优化目标是最大作业延迟时 ,单机成组作业优化调度是HP -hard。本文在利用优化性质的基础上 ,提出了一种适于大规模优化调度问题的多项式时间算法。仿真实验表明该算法具有良好的性能。 展开更多
关键词 生产调度优化算法 最大作业延迟 NP问题 仿真 多项式时间算法
下载PDF
基于多个供应商和多个零售商组成的经济批量问题研究 被引量：3
13
作者 徐健腾 张庆普 《运筹与管理》 CSCD 北大核心 2009年第2期136-142,共7页
本文考虑了由两个供应商和两个零售商组成的经济批量问题,当在每个供应商处的进货费用函数为数量折扣费用函数时,我们分析了该问题最优解的性质,并设计了一个计算复杂性为的动态规划算法,进而说明该问题是多项式可解的。
关键词 运筹学 库存管理 多项式时间算法 动态规划 经济批量
下载PDF
单机分批加工最大迟后问题的一个多项式时间算法 被引量：2
14
作者 孙世杰 AndrewsBoadi 刘朝晖 《应用科学学报》 CAS CSCD 1998年第1期18-23,共6页
文中考虑下述单机分批问题：对时刻零同时到达的ｎ个工件需分成若干批在同台机器上加工，同批工件加工时相邻，任一工件的完工时间为所在批中全部工件完工时的时间，机器每加工一批工件需一相同的调整时间．文中以工件的最大迟后为目标... 文中考虑下述单机分批问题：对时刻零同时到达的ｎ个工件需分成若干批在同台机器上加工，同批工件加工时相邻，任一工件的完工时间为所在批中全部工件完工时的时间，机器每加工一批工件需一相同的调整时间．文中以工件的最大迟后为目标函数，对工件加工顺序预先给定和可任意时的最优分批分别给出了多项式时间算法． 展开更多
关键词 排序 分批 多项式时间算法 柔性制造系统
下载PDF
二次锥规划的不可行内点算法 被引量：2
15
作者 迟晓妮 刘三阳 李炳杰 《兰州大学学报（自然科学版）》 CAS CSCD 北大核心 2007年第4期136-139,共4页
给出二次锥规划的一种不可行内点算法并证明该算法是多项式时间算法.利用本算法需O(n^(1/2)lnε^(-1))次迭代就可找到问题的ε-近似解,其迭代复杂性界与现有的二次锥规划可行内点算法的复杂性界相同.
关键词 二次锥规划 不可行内点算法 多项式时间算法
下载PDF
瓶颈指派问题的一种多项式时间算法 被引量：2
16
作者 晓斌 张干宗 《国防科技大学学报》 EI CAS CSCD 1997年第1期94-98,共5页
本文对瓶颈指派问题给出了一种新的算法，该算法不需要利用最大流算法，而类似于解经典指派问题的匈牙利算法。该算法是一个多项式时间算法，其复杂性为Ｏ（ｎ３）
关键词 瓶颈指派问题 多项式时间算法 阀门算法
下载PDF
基于一般时间相关和位置相关的单机排序问题研究 被引量：3
17
作者 王申重 《重庆师范大学学报（自然科学版）》 CAS CSCD 北大核心 2017年第2期6-10,共5页
【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,... 【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。 展开更多
关键词 排序 时间相关排序 位置相关排序 多项式时间算法
原文传递
单架飞机受干扰后飞机路径恢复多项式算法研究 被引量：3
18
作者 胡玉真 宋艳 许保光 《运筹与管理》 CSSCI CSCD 北大核心 2017年第8期11-18,共8页
飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NPhard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调... 飞机路径恢复是航班调整中保证航班能够运行的必要条件之一,而传统目标下的飞机路径优化问题是NPhard的。本文针对单架飞机受到干扰后,基于最小最大目标的同机型飞机路径最优化问题,给出了一个新的多项式时间算法。首先基于航空公司调整航班的常用原则,提出把最大航班延误时间最小化作为问题的目标。然后根据问题的一些特点和目标形式,设计出解构造算法,得到飞机路径恢复问题的最优解,并分析出算法的复杂度为O(n^2)。相对于一般的最小最大二分图匹配算法(复杂度为O(n^3log(n))),该算法具有较小的时间复杂度。最后用实例验证了解构造算法的有效性。该研究结果将为航空公司减少航班延误提供理论和方法支持。 展开更多
关键词 飞机路径恢复 二分图 最小最大匹配问题 多项式时间算法
下载PDF
一个具有两类工件的多目标排序的多项式时间算法 被引量：3
19
作者 冯琪 原晋江 《运筹与管理》 CSCD 2007年第3期52-55,共4页
本文考虑具有两个工件集的单机排序问题。第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数。问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小。本文证明该问题可在O(n1n2(n1+n2))时间内... 本文考虑具有两个工件集的单机排序问题。第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数。问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小。本文证明该问题可在O(n1n2(n1+n2))时间内求解。 展开更多
关键词 运筹学 排序 多目标 多项式时间算法
下载PDF
哈密顿图判定问题的多项式时间算法 被引量：3
20
作者 姜新文 《计算机科学》 CSCD 北大核心 2020年第7期8-20,共13页
NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的... NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。 展开更多
关键词 MSP问题 HC问题 NP完全问题 多项式时间算法
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 2 … 6 下一页 到第 页
使用帮助 返回顶部