期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到68篇文章
< 1 2 … 4 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
动态网络最短路问题的复杂性与近似算法 被引量：17
1
作者 林澜 闫春钢 +1 位作者 蒋昌俊 周向东 《计算机学报》 EI CSCD 北大核心 2007年第4期608-614,共7页
有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时... 有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性. 展开更多
关键词 动态网络 最短路 算法 np-困难 稳定性
下载PDF
并行分批排序问题综述 被引量：13
2
作者 张玉忠 曹志刚 《数学进展》 CSCD 北大核心 2008年第4期392-408,共17页
并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序... 并行分批排序是兴起于上世纪末的一类新型排序问题,它最初来源于半导体生产中的芯片测试过程,有重要的应用价值,在理论上也有重要的意义.因此,并行分批排序问题近年来受到了越来越广泛的关注,新的研究成果不断涌现.本文就并行分批排序问题的最新进展作了全面的介绍,指出了许多尚未解决的问题和许多新的研究方向,给出了丰富的参考文献,旨在把感兴趣的读者迅速带到此研究领域的前沿. 展开更多
关键词 并行分批排序 np-困难 近似算法
下载PDF
顶点覆盖问题的贪心算法的设计与分析 被引量：9
3
作者 姚朝灼 《福州大学学报（自然科学版）》 CAS CSCD 2001年第1期8-11,共4页
设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .
关键词 顶点覆盖 贪心算法 np-困难 相对比率 顶点度数 无向图 时间分析 误差分析 数据结构
原文传递
有向网络中最大容量支撑树形图扩容问题
4
作者 杨子兰 朱娟萍 杨宇 《运筹学学报（中英文）》 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
带到达时间分批排序问题的数学模型 被引量：3
5
作者 姜冠成 《苏州大学学报（自然科学版）》 CAS 2005年第2期22-27,共6页
建立数学规划模型来研究排序问题是一件有意义的工作.本文对单机分批带到达时间的最大完工时间排序问题1|B,rj|Cmax(属NP-困难,LIU Z H等)建立了它的0-1整数规划模型;利用统计软件SAS中的LP过程编程对此模型进行了数值求解实验,得到了... 建立数学规划模型来研究排序问题是一件有意义的工作.本文对单机分批带到达时间的最大完工时间排序问题1|B,rj|Cmax(属NP-困难,LIU Z H等)建立了它的0-1整数规划模型;利用统计软件SAS中的LP过程编程对此模型进行了数值求解实验,得到了按此数学模型计算机能求得最优解的该问题的规模. 展开更多
关键词 排序问题 到达时间 数学模型 最大完工时间 数学规划模型 整数规划模型 np-困难 数值求解 LP过程 统计软件 模型计算 SAS 最优解
下载PDF
Hamming距离下树型网络的最短路改进问题 被引量：3
6
作者 张斌武 王勤 《兰州理工大学学报》 CAS 北大核心 2008年第2期84-86,共3页
研究Hamming距离下树型网络的最短路改进问题,通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题并求解.该研究方法在一定程度上推广了已有的结果.该问题的研究有助于设计求解一般的Hamming距离下的最... 研究Hamming距离下树型网络的最短路改进问题,通过把该问题转化为0-1整数线性规划问题并通过求解有限个小规模0-1整数线性规划问题并求解.该研究方法在一定程度上推广了已有的结果.该问题的研究有助于设计求解一般的Hamming距离下的最短路改进问题的有效近似算法. 展开更多
关键词 HAMMING距离 最短路 np-困难 0-1整数规划
下载PDF
含装卸工调配的物流车辆配送路径问题的研究 被引量：2
7
作者 刘诚 陈治亚 《铁道科学与工程学报》 CAS CSCD 北大核心 2006年第4期79-83,共5页
考虑到物流配送车辆路径问题中要涉及货物的装卸作业,将装卸工调配问题和车辆路径问题相结合提出了含装卸工调配的物流车辆配送路径问题,给出了以总运输费用最小、总装卸工人数最少为目标函数的双目标0-1混合整数规划问题的数学模型.按... 考虑到物流配送车辆路径问题中要涉及货物的装卸作业,将装卸工调配问题和车辆路径问题相结合提出了含装卸工调配的物流车辆配送路径问题,给出了以总运输费用最小、总装卸工人数最少为目标函数的双目标0-1混合整数规划问题的数学模型.按目标函数的主次分2个阶段对该问题进行求解;最后,将装卸工人数最少转化为装卸费用最小将该模型进行了推广。 展开更多
关键词 装卸工调配 车辆路径 混合整数规划 np-困难
下载PDF
求解Hamming距离下的最短路改进问题的一个近似算法 被引量：2
8
作者 张斌武 王勤 余维燕 《兰州理工大学学报》 CAS 北大核心 2008年第4期98-100,共3页
研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近... 研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法. 展开更多
关键词 HAMMING距离 最短路改进问题 np-困难 近似算法
下载PDF
关于工期分配与加权误工数的双指标排序问题（英文） 被引量：2
9
作者 林浩 何程 《工程数学学报》 CSCD 北大核心 2017年第1期73-86,共14页
排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步... 排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型.主要结果包括NP-困难性、多项式可解情形以及多项式时间近似方案等结果.通过这些结果,一个多目标优化问题的特征得以完整地刻画. 展开更多
关键词 双指标排序 工期分配 加权误工数 np-困难 多项式近似方案
下载PDF
带服务器的三台平行机排序问题的复杂性和近似算法 被引量：1
10
作者 苏纯洁 《应用数学学报》 CSCD 北大核心 2003年第3期544-550,共7页
本文研究了带服务器的三台平行机排序问题的复杂性,并给出了一个最好的在线近似算法。
关键词 服务器 平行机 排序问题 复杂性 近似算法 np-困难 三元划分问题
原文传递
弦图上团划分数问题的复杂性 被引量：1
11
作者 马绍汉 吴举林 《山东大学学报（自然科学版）》 CSCD 1989年第2期14-19,共6页
本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。
关键词 弦图 图覆盖数 团划分数 np-困难
原文传递
有区间约束单机延误排序问题 被引量：1
12
作者 周贤伟 杜文 周双贵 《运筹与管理》 CSCD 1998年第2期13-19,共7页
研究一类推广的从准备时间ｒｉ到交工期ｄｉ的多重ｒ／ｄ区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是ＮＰ—困难的，对问题的特殊情形证明了它是多项式时间可解的。
关键词 单机排序 区间约束 延误问题 np-困难
下载PDF
工件加工可拒绝的无界批量分批排序问题的几点探讨(英文) 被引量：1
13
作者 张咸昭 蔡增霞 任剑锋 《运筹学学报》 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
求解Hamming距离下单位型单发点树型网络最短路改进问题的算法 被引量：1
14
作者 张斌武 王勤 《河海大学常州分校学报》 2007年第4期1-4,共4页
给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络... 给出了求解两类特殊的Hamming距离下单位型单发点树型网络最短路改进问题的多项式时间算法,并研究了一般树型网络下该问题的性质.解决了Hamming距离下逆问题(改进问题)中的部分问题,有助于设计出更多的求解Hamming距离下单位型树型网络最短路改进问题的算法. 展开更多
关键词 HAMMING距离 最短路改进问题 np-困难 多项式时间算法
下载PDF
环上的最大流通量问题 被引量：1
15
作者 陈智斌 李建平 《云南大学学报（自然科学版）》 CAS CSCD 2004年第4期288-291,共4页
研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,…,n-1},每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对{si,ti}(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点... 研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集{0,1,2,…,n-1},每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对{si,ti}(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点对中的某些点对(也许是所有的),此时每个点对就由一条道路相连,在通过环上每条边的总条数不超过其边整数容量限制的条件下,最大化所用到的道路条数.通过引入单方向概念并应用LP-rounding技巧,证明了环上的单方向最大流通量问题属于P类,即可有多项式时间算法求解,并因此获得了环上最大流通量问题的一个2-近似多项式算法. 展开更多
关键词 环 最大流通量 LP-rounding技巧 近似算法 np-困难
原文传递
最小化最大加权完工时间重新排序研究 被引量：1
16
作者 臧西杰 李士生 王曦峰 《系统科学与数学》 CSCD 北大核心 2017年第11期2293-2300,共8页
重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个... 重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是:1)在原始排序错位限制的条件下最小化最大加权完工时间;2)最小化最大加权完工时间与原始排序的错位的加权和.在本文研究中我们假设所有工件在0时刻到达.文章的主要结果:对于Γ∈{D_(max)(π~*),△_(max)(π~*)},给出了问题1|Γ≤k|max w_jC_j和问题1‖maxw_jC_j+μΓ多项式时间的求解算法;证明了问题1|∑△_j(π~*)≤k|max w_jC_j和问题1‖max w_jC_j+μ∑△_j(π~*)是强NP-困难的. 展开更多
关键词 重新排序 错位 最大加权完工时间 np-困难
原文传递
图的部分控制集问题的修正Greedy算法 被引量：1
17
作者 丁玲玲 方奇志 《运筹与管理》 CSCD 2007年第5期83-86,共4页
部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H... 部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。 展开更多
关键词 运筹学 图的控制集 近似算法 np-困难
下载PDF
m台机器上流水作业时间表问题的复杂性及一种新的启发式算法(英)
18
作者 时凌 《西南民族大学学报（自然科学版）》 CAS 2003年第3期258-263,共6页
研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的。给出一种新的启发式算法,并证明该算法的最坏性能比是(m+1)/2,且上界是紧的。
关键词 流水作业时间表 复杂性 延迟时间 准备时间 3-划分 np-困难 算法
下载PDF
单机交错排序问题的复杂性证明
19
作者 于彬 王广彬 +1 位作者 赵立宽 孙亮 《高师理科学刊》 2007年第4期4-7,共4页
关于共同宽容交货的单机排序问题,对于宽容区间大小给定,位置不固定的情况,给出了5条性质,证明该问题是NP-困难的.
关键词 宽容区间 超前迟后 np-困难
下载PDF
带有固定工件的一个单机排序问题
20
作者 石磊 金世国 《安阳师范学院学报》 2008年第5期21-23,共3页
本文考虑带有固定工件的一个单机排序问题,证明了该问题是NP-困难的并给出了它的一个动态规划算法,证明该问题是拟多项式时间可解的。
关键词 固定工件 np-困难 动态规划算法
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 2 … 4 下一页 到第 页
使用帮助 返回顶部