检索结果-南通市图书馆

湖北民族学院学报（自然科学版） 2000年第4期18卷 64-62页

作者：时凌陶勇湖北民族学院计算机与数学系湖北恩施445000 利川市民族中等职业技术学校湖北利川445700

讨论两台机器上的有序流水作业时间表问题 ,证明两台机器上的有序流水作业时间表问题是np -困难的 .

关键词：奇偶划分有序工件 np-困难有序流水作业时间表

在线全文

学校读者我要写书评

暂无评论

有向网络中最大容量支撑树形图扩容问题

运筹学学报（中英文） 2024年第2期28卷 151-158页

作者：杨子兰朱娟萍杨宇丽江文化旅游学院信息学院云南丽江674199 云南大学数学与统计学院云南昆明650091

针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是np-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树... 详细信息

针对有向网络中最大容量支撑树形图扩容问题(EMCSA),由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是np-困难的,并且给出解决EMCSA问题的一个启发式算法。最后,考虑EMCSA问题的一种特殊情况:有向网络中最大容量支撑树形图的最少弧扩容问题(NEMCSA),采用权重差最小换弧方法设计时间复杂度为O(mn)的多项式时间算法。

关键词：最大容量树形图扩容 np-困难启发式算法多项式时间算法

在线全文

学校读者我要写书评

暂无评论

图均匀分割算法研究

图均匀分割算法研究

作者：陆逸豪华东师范大学

学位级别：硕士

图均匀分割问题旨在将图G的顶点集合V分割为大小相近的多个部分V,...,V,满足max|V|≤(1+?)[n/p],?∈R,使得分割后横跨各部分间的割边权和尽可能小.图均匀分割问题是图论的重要问题,在很多工业领域有重要应用.Metis软件是目前使用最为广... 详细信息

图均匀分割问题旨在将图G的顶点集合V分割为大小相近的多个部分V,...,V,满足max|V|≤(1+?)[n/p],?∈R,使得分割后横跨各部分间的割边权和尽可能小.图均匀分割问题是图论的重要问题,在很多工业领域有重要应用.Metis软件是目前使用最为广泛的图分割求解工具,由Karypis实验室开发,对C++和Fortran都有完善的api支持.越来越多的机构希望自主开发图均匀分割求解软件,使得其能够结合自身需求,灵活地在求解结果的好坏与求解速度间进行取舍.本文旨在为自主定制化开发类似Metis软件的图均匀分割求解软件进行算法研究,希望能够在花费时间较Metis软件少的情况下,获得效果相近的分割结果.本文针对小规模图(点数为100-200)和大规模图(点数为10000-20000)进行算法方向的探索.在小规模图上提出了邻域搜索算法,针对边数较多的情况加入了随机抽样.实验中邻域搜索算法在稀疏图上相比Metis软件运行时间平均减少了94.8%,割边权和与Metis软件结果相比平均增大了3.8%.邻域搜索算法在密集图上相比Metis软件运行时间平均减少了61.4%,割边权和与Metis软件结果相比平均减少了0.6%.加入随机抽样的邻域搜索算法在稀疏图上相比Metis软件运行时间平均减少了90.4%,割边权和与Metis软件结果相比平均增大了4.1%.加入随机抽样的邻域搜索算法在密集图上相比Metis软件运行时间平均减少了81.6%,割边权和与Metis软件结果相比平均减少了0.2%.在大规模图上,提出了基于S3收缩的多级分割算法和动态顺序的流式算法.在实验中多级分割算法相比Metis软件运行时间平均分别减少了14.3%,割边权和与Metis软件结果相比平均增加了3.3%.动态顺序的流式算法相比Metis软件运行时间平均减少了68.2%,割边权和与Metis软件结果相比平均增加了5.6%.

关键词：图均匀分割启发式算法 np-困难 Metis软件

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

平面RNA二级结构预测的复杂性与算法

平面RNA二级结构预测的复杂性与算法

作者：刘洁山东大学

学位级别：硕士

RNA序列发生弯曲时,不相邻的碱基之间可产生氢键,这些氢键构成RNA的二级结构。RNA二级结构对于其功能有重要的影响,因此RNA二级结构预测问题是计算生物学领域的热点之一,其目的在于根据生物界的规则和原理使用合适的算法计算RNA链最可... 详细信息

RNA序列发生弯曲时,不相邻的碱基之间可产生氢键,这些氢键构成RNA的二级结构。RNA二级结构对于其功能有重要的影响,因此RNA二级结构预测问题是计算生物学领域的热点之一,其目的在于根据生物界的规则和原理使用合适的算法计算RNA链最可能产生的二级结构。目前采用最多的是最低能量规则,即能量越低RNA结构越稳定。RNA序列中不相邻的碱基可根据规则形成基对,研究发现,当两条基对平行且相邻时,它们会构成堆叠,此时其能量最低。由此,分子生物学家们提出了以堆叠数量为优化目标的最大堆叠问题（maximum stacking base pairs,MSBP）。假结是指两组碱基堆叠发生交叉的现象。最简单的RNA二级结构中不存在假结,此时最优的RNA二级结构是多项式时间可计算的,但是假结存在于绝大多数的真实RNA二级结构中。平面RNA二级结构是指当将二级结构的所有碱基对嵌入到平面时,其堆叠之间不交叉。此时的RNA二级结构中存在假结,但不存在三组堆叠相互交叉的现象。本文研究了平面输入的MSBP问题,即输入的氢键（用弧表示）互不相交、与碱基形成的点组成的图为平面图,将3-正则平面无桥连通图的最大独立集问题归约到平面输入的MSBP,从而证明该问题是np-困难的,并给出了该问题的一个时间复杂度与空间复杂度均为O（1.755n）的精确算法。另外,设计了一种基于动态规划的时间复杂度与空间复杂度均为O（n·16s）的启发式算法2s-DP,使用的参数s为序列中跨度最长的弧的长度。最后,我们在计算机上模拟了该启发式算法在随机生成的RNA序列输入上的表现,其在长度n与弧最大跨度s差距越大时,计算的速度越快。此毕业设计能够对RNA二级结构预测问题的子问题研究进行补充,同时为平面RNA二级结构预测问题的算法设计提供了新思路。

关键词：计算生物学 RNA二级结构预测 np-困难启发式算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

单机上工件可拒绝的ND双代理排序问题

单机上工件可拒绝的ND双代理排序问题

作者：葛晴郑州大学

学位级别：硕士

工件可拒绝排序以及双代理排序是应用背景很强的两个现代排序模型,近二十年来得到人们的广泛关注与研究.然而,只有少量文献研究这两个模型的组合问题,即工件可拒绝的双代理排序问题.在工件可拒绝排序中,每个工件或者被接收并安排在机器... 详细信息

工件可拒绝排序以及双代理排序是应用背景很强的两个现代排序模型,近二十年来得到人们的广泛关注与研究.然而,只有少量文献研究这两个模型的组合问题,即工件可拒绝的双代理排序问题.在工件可拒绝排序中,每个工件或者被接收并安排在机器上进行加工,或者被拒绝并支付相应的拒绝费用.在经典的竞争双代理(CO双代理)排序中,两个代理的工件集合是完全不交的.而在非不交双代理(ND双代理)排序中,我们允许两个代理有共同的工件.因此,ND双代理排序是CO双代理排序的推广.本学位论文研究了一些单机上工件可拒绝的ND双代理排序问题.按照排序问题的三参数表示法,这些问题可统一表示为1|ND,rej,fB+∑JB∈RB ejB≤Q｜fA+∑JjA∈RAejA,它要求在B代理工件的排序费用与拒绝费用之和不超过阈值的前提下使得A代理工件的排序费用与拒绝费用之和达到最小.针对(fA,fB)的不同选取,我们研究了下述四个问题:本文的主要结果如下:(1)对问题(P1),我们说明了它的np-困难性,并给出了一个拟多项式时间算法以及一个全多项式时间近似方案.(2)对问题(P2),我们说明了它的np-困难性,并给出了一个拟多项式时间算法.(3)对问题(P3),我们说明了它的np-困难性,并给出了一个拟多项式时间算法以及一个全多项式时间近似方案.(4)对问题(P4),我们说明了它的np-困难性,并给出了一个拟多项式时间算法以及一个全多项式时间近似方案.

关键词：工件可拒绝排序 ND双代理排序 np-困难动态规划算法全多项式时间近似方案

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

动态网络最短路问题的复杂性与近似算法

计算机学报 2007年第4期30卷 608-614页

作者：林澜闫春钢蒋昌俊周向东同济大学电子与信息工程学院上海200092 复旦大学计算机与信息技术系上海200433

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时... 详细信息

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是np-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.

关键词：动态网络最短路算法 np-困难稳定性

带服务器的三台平行机排序问题的复杂性和近似算法

在线全文

学校读者我要写书评

暂无评论

应用数学学报 2003年第3期26卷 544-550页

作者：苏纯洁华东理工大学理学院上海200237

本文研究了带服务器的三台平行机排序问题的复杂性,并给出了一个最好的在线近似算法。

关键词：服务器平行机排序问题复杂性近似算法 np-困难三元划分问题

在线全文

学校读者我要写书评

暂无评论

最小化最大加权完工时间重新排序研究

系统科学与数学 2017年第11期37卷 2293-2300页

作者：臧西杰李士生王曦峰中原工学院理学院郑州450007

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个... 详细信息

重新排序模型可以描述如下:一组原始工件已经按照某个准则做好最优加工(排序)方案,但是还没有开始加工.此时,另一组新工件突然到达,需要与原始工件一起加工.生产部门需要调整已有的加工方案,使得在原始工件不打乱太多的情形下得到一个合理的排序.本文研究最大加权完工时间的重新排序问题,问题的目标是: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-困难

关于工期分配与加权误工数的双指标排序问题（英文）

在线全文

学校读者我要写书评

暂无评论

工程数学学报 2017年第1期34卷 73-86页

作者：林浩何程河南工业大学理学院郑州450001

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步... 详细信息

排序问题中工期分配的目的是处理分配费用与性能指标的利益平衡,由此提出工期分配的双目标排序问题.关于工期分配与加权误工数的单机双指标排序问题,文献中只研究了其线性组合形式.针对该问题,本文针对约束形式及Pareto优化形式进一步研究了更多的模型.主要结果包括np-困难性、多项式可解情形以及多项式时间近似方案等结果.通过这些结果,一个多目标优化问题的特征得以完整地刻画.

关键词：双指标排序工期分配加权误工数 np-困难多项式近似方案

在线全文

学校读者我要写书评

暂无评论

储存时间有上限的两阶段供应链排序问题

运筹学学报 2017年第2期21卷 126-134页

作者：张龙曲阜师范大学管理学院运筹学研究所山东日照276826

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费... 详细信息

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是np-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.

关键词：储存时间供应链排序 np-困难伪多项式时间算法