基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

带次模惩罚的部分命中集问题的近似算法

研究了带次模惩罚的部分命中集问题.给定一个超图H=(V,E),一个定义在V上的费用函数,一个定义在2~E上的次模惩罚函数,和一个非负整数k.问题的目标是找一个顶点子集S?V,使得S至少覆盖k条超边,且S的总费用加上未被S覆盖的超边集的惩罚费用之和最小.设计了一个基于原始-对偶的两阶段组合算法来解决该问题.当次模惩罚函数是正规化的且非减时,得到算法的近似因子为l+1,其中l是超边所含的顶点数的最大值.

基于近似算法的分布参数对机电系统动态响应的频时域研究

文章针对具有机械部分分布参数的机电系统进行了频时域实验研究。文章强调了考虑参数分布的重要性,并分析了影响其分布特性的重要元素。在验证阶段开发了实验装置,并采用StrimServer和CANMonitor程序用于数据采集和分析;同时开发了控制系统,描述了最简单校正装置的创建过程,突出了用于开发控制程序的编程环境,并提供了一组编程控制器的程序。在频域实验中,在模拟机电系统行为的条件下,展示了合成控制系统的有效性。通过与理论计算的比较发现,其与实际值最大相对误差不超过10%,证实了理论计算的可靠性。在时域分析中,通过CANMonitor程序绘制电流图,发现在共振频率下电流幅值增加到1.83倍,这与在谐振频率处应有的情况相符。期望本文能对理解和设计具有分布参数的机电系统带来启发。

优先级k-中心问题的FPT近似算法

优先级k-中心问题是聚类领域中1个经典的NP-难问题。给定度量空间中的1个集合X和参数k∈N+,其中,集合X中每个点v都被赋予1个优先级参数r(v)∈R+,求解1个大小为k的子集S■X,考虑集合X中任意数据点到集合S的距离与r(v)之间比值,找到最大比值,目标是最小化该比值。对于优先级k-中心问题,目前最好的结近似算法是多项式时间内的2-近似算法,该问题不存在1个(2-ε)-近似算法,(其中,ε为用于控制算法近似比的参数)。本文研究优先级k-中心问题的固定参数可解(fixed-parameter tractability,FPT)时间内的近似算法。基于k-中心问题的贪心策略,提出新的中心点选取方法。研究结果表明:该方法通过贪心策略选取一定规模的候选中心点集,利用加倍度量维度的性质去限制该集合的大小,实现了FPT时间内的(1+ε)-近似算法,降低了目前该问题的近似比。

平方度量的设施租赁问题的近似算法

作为设施租赁问题的推广,首次提出平方度量的设施租赁问题,平方度量侧重于突出距离对连接费用的影响,具有广泛的实际应用背景。在平方度量的设施租赁问题中,每个时间段都有顾客到达,每个到达的顾客都需要被连接到某个其到达时正在租赁的设施上。租赁设施产生租赁费用,连接顾客到设施产生连接费用,连接费用是顾客与设施之间距离的平方,通常假设距离是度量的。目标是租赁一些设施,连接每个顾客,使得租赁费用与连接费用之和最小。基于原始对偶技巧,给出平方度量的设施租赁问题的9-近似算法。

南京大学计算机科学与技术系教授栗师 为近似算法突破贡献技术模型

凭借非凡的计算速度和准确度,计算机大大拓展了人类的思考能力。凭借强大的计算能力,人类已经可以在一定程度上破译生命的密码,也可以破译思想的基因。那么,计算机是如何做到这些的呢?要准确地回答这个问题离不开以南京大学计算机科学与技术系教授、博士生导师栗师为代表的理论计算机科学领域算法设计专家给出的答案。

适合复杂网络分析的最短路径近似算法

基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性.

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广 ,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景 .提出了求解有色装箱问题的 KC- A算法 ,它首先对输入物品进行分类预处理 ,然后在同一类内部使用经典装箱问题的近似策略 A;给出了 K C- A算法最坏情况渐近性能比的下界 ;分析了当选用的算法 A是著名装箱算法 N F,FF,BF,WF时 K C- A算法的最坏情况渐近性能比和平均性能比 ;给出了实验结果 ,并指出 K C-

求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.

求解项目调度中资源水平问题的近似算法

针对 RL P与 RCPSP的相似之处和自身特点 ,以求解 RCPSP的遗传算法为基础 ,设计了一种求解 RL P的基于分支定界策略的近似算法 .搜索树的每一节点对应一个 RCPSP,通过求解各节点 RCPSP来求得 RL P的最优调度计划 .算法从具有基本资源需求水平的根节点开始 ,采用宽度优先顺序逐渐提高各种资源的可用量 ,既有利于资源的均衡利用 ,又可以通过定界策略有效地控制搜索树的节点数量 .结合实例问题说明了基于分支定界策略的近似算法的求解过程 .最后通过实例问题对该算法与遗传算法进行求解效果和时间效率的对比 。

GPU上两阶段负载调度问题的建模与近似算法

随着硬件功能的不断丰富和软件开发环境的逐渐成熟,GPU(graphics processing unit)越来越多地被应用到通用计算领域,并对诸多计算系统(尤其是嵌入式系统)性能的显著提升起到了至关重要的作用.在基于GPU的计算系统中,大规模并行负载同时进行数据传输和加载的情况时常发生,数据传输延时在系统性能全局最优化中变得不容忽视.综合考虑负载的传输时间和执行时间,以总负载makespan最小化作为系统性能的全局优化目标,研究了GPU上负载"传输-执行"联合调度问题.首先,将负载的时间信息和并行任务数与矩形域的二维空间联系起来,建立了负载的2D双层矩形域模型;然后,将GPU上负载调度问题归结为一类Strip-Packing问题;最后,基于贪婪策略给出了近似度为3的多项式时间近似算法,算法复杂度为O(nlogn).该近似算法的核心是对数据传输阶段进行负载排序调度.这从理论层面上证明了GPU系统采取"传输-执行"两阶段调度的有效性,即,在数据传输阶段采取负载排序调度,在负载执行阶段采取先来先服务(first-come-first-serve,简称FCFS)调度,能够使GPU性能达到全局最优或近似最优.

城门洞形断面隧洞正常水深的近似算法

城门洞形断面隧洞是输水工程中较常采用的一种形式,但其正常水深方程是超越方程,数学上无解析解。目前采用的图解、试算等方法存在着计算过程繁琐且计算精度差的缺陷。应用拟合法提出了近似计算公式,其形式简捷、结论准确。在工程常用范围内(0<h/r≤1.8)最大误差<0.2%。

一种不确定数据集上频繁模式挖掘的近似算法

为提高不确定数据集上频繁模式挖掘的效率,针对已有算法在判断是否需要为头表中的某项创建子头表时的计算量比较大的问题,给出一个近似挖掘策略AAT-Mine,以损失小部分频繁项集为代价,提高整个算法的挖掘效率。采用三个不同的典型数据集进行了算法的测试,分别与目前最好的算法和典型算法进行性能对比。实验结果验证了近似算法AAT-Mine的时空效率都得到了提高。

矩形件排样优化的一种近似算法

根据矩形件排样的实际下料工艺要求 ,以板材的长或宽对待排矩形件的长或宽求余数 ,根据余数结果提出了一种矩形件排样的近似优化算法。

求解单位等边三角形Packing问题的近似算法

多边形Packing问题不仅具有重要的理论意义 ,而且也有广阔的应用前景 .由于该问题具有NP难度 ,且具有连续的性质 ,一般要事先对多边形的放置方位进行限制 ,例如不允许多边形旋转 ,然后再进行优化求得近似解 .该文采用一种新的思路对多边形Packing问题的一个特例———单位等边三角形Packing问题进行了研究 ,提出了零自由度动作和零自由度放置策略的概念 ,并设计了一个近似求解算法———最小损伤法 .复杂性分析和计算结果表明该算法是高效的 .以此为基础 ,可能为多边形Packing问题找到类似的求解算法 .

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现(在第一阶段不知道).两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合(称为场景).并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务.给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小.根据问题的特定结构,给出了原始-对偶(组合)3-近似算法.

城市环境车联网中基于近似算法的RSU部署方案

为了使用尽可能少的RSU实现对目标区域的有效覆盖,设计c街道模型,将对区域的覆盖转化为对区域内街道的覆盖,然后,在该模型下提出基于贪心策略的多项式(GBP,greedy-based polynomial)时间近似算法,得到RSU的部署方案以解决覆盖问题。针对城市中一些地形复杂的区域,设计Cue模型(complex urban environment model),将目标区域划分为子区域,然后提出基于shifting策略的多项式时间近似算法,并对算法的近似比率和时间复杂度进行了理论分析与证明。仿真结果表明,算法GBP能够有效地解决城市环境车联网中的区域覆盖问题。

1|B,r_j∈{0,r}|ΣC_j问题的复杂性及近似算法

讨论了分批排序中工件有两个到达时间 ,以工件完工时间总和为目标函数的批处理问题 ,证明了其NP_完备性 ,并以Brucker等[1] 给出的动态规划算法为基础 ,给出了一性能指标为

大型相关失效工程网络系统可靠度的近似算法

为避开失效模式(或系统可靠路径)的NP难题(non-polynomialincreasehardproblem),提出递推分解算法,降低大型工程网络系统可靠度分析中的计算复杂性,同时,将改进的多维正态变量积分公式,引入递推分解算法之中,计算多失效模式(或系统可靠路径)的联合概率,并最终计算工程网络系统的失效概率和可靠度,对于特别复杂的工程网络系统,采用上下界的方法,给出具有很高精度的可靠度近似值。实例分析表明,本文提出的方法,具有较高的精度和计算效率。

记数集团抽样检查接收概率的近似算法及其应用

本文给出记数集团抽样检查接收概率的近似公式及算法,并且通过与传统近似算法的比较和计算机模拟抽样检查验证,讨论了该方法的准确性和实用性,结果表明：本文提出的接收概率算法明显优于传统算法,可用于计数型集团检查抽样方案设计而不必考虑一个集团中有2个或更多不合格品混入的问题．该算法已应用于家蚕微粒子病母蛾集团检查2次和多次抽样方案的设计．