检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

k-中位问题的近似算法

中国科学:数学 2025年第2期55卷 551-566页

作者：吴晨晨杜东雷苗润杰徐大川天津理工大学理学院运筹学与系统工程研究所天津300384 Faculty of Management University of New BrunswickFredericton E3B 5A3Canada 郑州大学数学与统计学院郑州450001 北京工业大学数学统计学与力学学院北京100124

k-中位问题是理论计算机科学和组合优化领域中的经典问题之一,其应用场景遍及图像处理、模式识别、供应链管理和数据挖掘等前沿领域.如今,随着大数据和机器学习的发展,k-中位问题的实际应用愈发复杂多样,这也产生了诸多亟待解决的研究课... 详细信息

k-中位问题是理论计算机科学和组合优化领域中的经典问题之一,其应用场景遍及图像处理、模式识别、供应链管理和数据挖掘等前沿领域.如今,随着大数据和机器学习的发展,k-中位问题的实际应用愈发复杂多样,这也产生了诸多亟待解决的研究课题.为使相关研究人员快速了解k-中位问题,本文综述经典k-中位问题及其变型问题的基于线性规划舍入、原始-对偶、对偶拟合、局部搜索和Lagrange松弛等技巧设计的有效算法.首先介绍经典k-中位问题与无容量设施选址问题之间的密切联系;然后介绍k-中位问题的若干重要变形,包括k-中心问题、k-设施选址问题、背包中位问题、容错k-中位问题、带容量的k-中位问题、带下界的k-中位问题、带惩罚的k-中位问题、带异常值的k-中位问题和在线中位问题等问题;最后介绍k-中位问题的近似算法研究成果,并列出该领域中的若干公开问题.

关键词： k-中位问题近似算法线性规划局部搜索

同方期刊数据库

在线全文

学校读者我要写书评

暂无评论

最小化开放式变尺寸装箱问题的近似算法

运筹学学报(中英文) 2025年

作者：郭梦瑶帅天平北京邮电大学理学院数学与信息网络教育部重点实验室(北京邮电大学)

本文研究最小化开放式变尺寸装箱问题,它是将最小化的开放式装箱问题和变尺寸装箱问题相结合得到的装箱问题的变体。我们将经典的装箱算法应用到该问题上,根据箱子的选择策略给出了四种在线装箱算法NFL,FFL,FFS和HA,并证明其渐近竞争比... 详细信息

本文研究最小化开放式变尺寸装箱问题,它是将最小化的开放式装箱问题和变尺寸装箱问题相结合得到的装箱问题的变体。我们将经典的装箱算法应用到该问题上,根据箱子的选择策略给出了四种在线装箱算法NFL,FFL,FFS和HA,并证明其渐近竞争比分别为4,2,2和71/60。

关键词：装箱问题变尺寸装箱开放式装箱近似算法

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

近似算法在并行计算中的应用

高技术通讯 2004年第5期14卷 1-4页

作者：芦东昕吴磊陈鹏深圳中兴通讯公司成都研究所，成都610041 电子科技大学应用数学学院，成都610054 北京大学计算机科学技术学院北京，100871

在发现关联规则的并行算法中，候选项目集在各个处理器节点之间如何划分，以使各个节点负载平衡，是一个非常关键的问题。本文通过引入近似算法，简单而有效解决了上述问题。最后，对引入近似算法后的算法复杂度给出了较为详细的分析。

关键词：近似算法并行计算关联规则负载平衡数据挖掘事务数据库

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

采用邻域近似算法估计环境参数不确定性

声学学报 2008年第1期33卷 41-50页

作者：杨坤德马远良西北工业大学西安710072

根据贝叶斯理论,逆问题的解可以用后验概率密度来表征,它包含了模型参数先验知识和观测数据信息,反映了反演参数的不确定性。一种快速吉布斯采样算法已经被用于后验概率密度的多维积分运算,但其需要调用大量的声场前向模型,在多个频率... 详细信息

根据贝叶斯理论,逆问题的解可以用后验概率密度来表征,它包含了模型参数先验知识和观测数据信息,反映了反演参数的不确定性。一种快速吉布斯采样算法已经被用于后验概率密度的多维积分运算,但其需要调用大量的声场前向模型,在多个频率或水平变化的匹配场参数反演中,计算量仍然很大。基于邻域近似算法,提出一种比快速吉布斯采样算法更快的参数不确定性估计方法。对低维参数反演问题,邻域算法可以很好地逼近真实的后验概率密度;而对高维问题及其敏感参数,在模型参数样本量有限的条件下,邻域算法很难精确地估计后验概率密度。为了克服以上缺点,并完整地得到反演参数的不确定性信息,设计了一种多步估计方案。数值仿真和实测数据分析表明,多步邻域算法采用较少的计算代价,可获得与快速吉布斯方法相似的估计精度。

关键词：参数不确定性近似算法估计方法邻域概率密度环境模型参数不确定性信息

在线全文

学校读者我要写书评

暂无评论

一般设施定位问题计算复杂度和近似算法研究

计算机研究与发展 2007年第5期44卷 790-797页

作者：潘锐朱大铭马绍汉山东大学计算机科学与技术学院济南250061

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该... 详细信息

设施定位问题即UFL问题是NP-hard的组合优化问题,是聚类问题领域的热点问题之一,在数据挖掘和分类识别方面有着重要应用.多年来其近似算法研究一直是计算机科学工作者关注的焦点,然而现有研究结果大多关于Metric空间,一般距离空间中该问题结果始终未见.针对最大连接费用至多是最小连接费用ω>1倍的一般距离空间中设施定位问题,简称一般设施定位问题,借助集合覆盖问题,利用问题归约方法证明其不存在近似性能比小于1.243+0.316ln(ω-1)的多项式时间近似算法,除非NPDTIME(nO(loglogn));设计了一般设施定位问题的局部搜索算法,证明算法近似性能比是(1+ω)/α,ω>1,1≤α≤2.仿真实验表明,一般设施定位问题局部搜索算法的求解质量极高;通过实验进一步研究了该算法并给出了改进方法.

关键词：设施定位计算复杂性集合覆盖近似算法局部搜索

改进的基于拓扑分析的Steiner树近似算法

在线全文

学校读者我要写书评

暂无评论

西安交通大学学报 2003年第10期37卷 1012-1015页

作者：高磊张德运王晓东安智平西安交通大学电子与信息工程学院西安710049 福州大学计算机科学与技术系福州350002

针对Berman近似算法k为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在... 详细信息

针对Berman近似算法k为3情况下的求解思想进行了改进.在使用Fibonacci堆求解出相应点对间最短距离的基础上,通过构建Voronoi域求出元组子树的耗费,并分析了Steiner树的网络拓扑结构以去除无用元组,从而简化拓扑,降低总体时间复杂度.在实验结果中,每个实例的过滤因子均大于0.9,有的甚至高达0.999,这表明大量无用的元组在进入评估阶段和构造阶段之前已被过滤掉,同时运行时间的减少也显示出改进算法在多播应用的路由寻径中更有效.

关键词：近似算法拓扑分析时间复杂度

在线全文

学校读者我要写书评

暂无评论

翻转距离星树问题的计算复杂度和近似算法

软件学报 2002年第6期13卷 1117-1122页

作者：朱大铭马绍汉雷鹏山东大学计算机科学技术学院山东济南250100

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.

关键词：翻转距离星树问题计算复杂度近似算法数据结构星型进化树

在线全文

学校读者我要写书评

暂无评论

无线传感器网络最小覆盖集的贪婪近似算法

软件学报 2010年第10期21卷 2656-2665页

作者：陆克中孙宏元深圳大学计算机与软件学院广东深圳518060 深圳大学国家高性能计算中心深圳分中心广东深圳518060 深圳大学ATR国防科技重点实验室广东深圳518060

网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一... 详细信息

网络生命期是限制无线传感器网络发展的一个瓶颈.在保证网络监控性能的前提下,仅调度部分节点工作而让其余节点处于低功耗的休眠状态,可以有效节省能耗,延长网络生命期.节点调度的目标是寻找一个能够覆盖监控区域的最小节点集合,这是一个NP难问题,目前,其近似算法的性能较低.提出了一种基于贪婪法的最小覆盖集近似算法,在构造覆盖集的过程中,优先选择扩展面积最大的有效节点加入覆盖集.理论分析表明,该算法能够构造出较好的覆盖集,时间复杂度为O(n),其中,n为初始节点总数.实验数据表明,该算法的性能要优于现有算法,得到的覆盖集的平均大小比现有算法减小了14.2%左右,且执行时间要短于现有算法.当初始节点分布较密时,该算法得到的平均覆盖度小于1.75,近似比小于1.45.

关键词：无线传感器网络网络生命期节点调度最小覆盖集贪婪算法近似算法

在线全文

学校读者我要写书评

暂无评论

数据流上的分位数近似算法研究

计算机研究与发展 2008年第2期45卷 287-292页

作者：杨蓓黄厚宽北京交通大学计算机与信息技术学院

数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精... 详细信息

数据流是一种新型数据模型,广泛应用于交通流量监控、通信管理、传感器网络、股票分析、Web点击流等众多领域.近年来越来越多的学者关注于数据流上的分位数计算研究.由于流数据的连续、无界、易失等特性,存储完整的流数据信息并得到精确的查询结果几乎是不可能的.在实施查询计算时追求内存用量与查询精度之间的最佳均衡.设计了规范数直方图的概要数据结构以存储流数据的摘要信息,并在此基础上提出了单遍扫描的、联机的分位数近似算法,其时间和空间复杂度均线性于概要结构中桶的个数,而与数据流的长度无关,因而具有很好的可规模性.该方法在均匀分布的数据上取得了优良性能.分析了算法精度与内存需求的关系.实验结果表明该算法具有较精确的查询结果,具备良好的实用性和有效性.

关键词：数据流概要数据结构直方图分位数近似算法