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

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

无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法

在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,WangFeng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。

0-1背包问题的非线性降维近似算法

求解0-1背包问题的精确算法不能在较短时间内求解大规模0-1背包问题,使其实用性受到限制.针对该问题,给出求解0-1背包问题的非线性降维算法,并进行了数值实验,验证了算法的有效性.该算法属于近似算法,相对其他一些近似算法,计算结果更为精确.

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

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

一类分式规划问题的ε-近似算法

本文针对一类复杂的分式规划问题,提出一种全局最优ε-近似解算法,并从理论上证明该算法的收敛性和计算复杂性,数值结果表明本文算法有效可行.

混合图上最小-最大圈覆盖问题的近似算法

考虑一个混合图上的最小-最大圈覆盖问题。给定一个正整数k和一个混合加权图G=(V,E,A),这里V表示顶点集,E表示边集,A表示弧集。E中的每条边和A中的每条弧关联一个权重。问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧。目标是极小化最大环游的权重。该问题是运筹学和计算机科学中一个重要的组合优化问题,它和它的变形在诸如快递配送、垃圾收集、积雪清扫等相关行业具有广泛应用。针对该问题,通过结合二分搜索和环游撕裂的技巧,首次给出了一个近似比为37/5的近似算法。

{1,2}-赋权图最小最大2-路径覆盖问题的近似算法

给定边权重为1或2的完全图,研究如何用2条顶点不相交的路径覆盖图中所有顶点,为了达到最大路径权重尽可能小的目标,在{1,2}-赋权图上旅行售货商问题的已有算法的基础上,设计了该问题的近似算法,并证明了算法的近似比不超过11/7。

钢-混凝土组合梁挠度的近似算法分析

介绍钢-混凝土组合梁挠度的几种近似算法,通过与试验结果进行对比,分析组合梁挠度与抗剪连接程度的相互关系,总结各算法的适用范围及精确程度,方便工程设计人员根据需要使用。

最小—最大圈划分的近似算法

给出了求解最小-最大圈划分问题的一种新的近似算法,该算法的近似比为3.5p-2,时间复杂性为O(n4).

基于实测数据的路段可靠性近似算法研究

利用北京市快速路与主干路的流量与车速实测数据,分析交通流量的变化规律,拟合流量-速度关系;分别采用车速和流量计算可靠度与饱和度,得到欠饱和与超饱和状态下可靠度与饱和度之间的一一对应关系,从而建立可靠度与饱和度之间的关系模型;最后利用实测数据对该模型进行了验证,结果表明快速路最大误差为0.088 5,主干路最大误差为0.092 3.

难解问题的固定参数近似算法研究进展

固定参数近似算法采用参数计算方法寻求问题的近似解,是实际中处理难解问题的一种新的有效手段。根据难解问题的参数计算复杂性类别,综述了固定参数可解问题、参数计算复杂性未定问题和W[t]-难问题(t≥1)固定参数近似算法近年来的研究进展。对于上述每一类问题,分别归纳了当前的主要研究结果,分析了其中的主要算法设计技术并探讨了有待研究的相关问题。

混合变分不等式解的分裂惯性近似算法

在无限维Hilbert空间中研究了一类混合变分不等式,借助于极大单调算子的ε-扩大提出了分裂惯性近似算法,并讨论了该算法的弱收敛性,该结论进一步弱化了这类混合变分不等式解集所需满足的条件.

限定顶点个数为p的最大割问题的一种近似算法

给出了求解限定顶点个数为p的最大割问题的一种近似算法,讨论了它的性能保证,利用Pipage技术,为最大割问题设计出了0.5-近似算法.

0-1背包问题算法分析与研究

0/1背包问题是计算机算法中一个经典问题。提出背包问题在现实生活中具有广泛的应用,从理论入手,给出背包问题的数学描述,并对0-1背包问题的四种经典算法:分支界限法、动态规划法、近似算法、遗传算法的算法思想进行详细描述,并对四种算法在实现的时间,空间和准确性等性能方面进行分析和对比,总结四种方法实现的优缺点,并得出结论:在不同的约束条件下,四种算法各有优劣,但遗传算法应该是未来发展的方向。

近似2-连通k-支配容错虚拟主干网

由于无线网络存在节点失效、链路断裂等特性,虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。

计算树的[1,2]-数的算法研究

图G的一个点集S是[1,2]-集,若每个不在S中的点至少与S中的1个点相邻且至多与S中的2个点相邻.一个图的所有[1,2]-集中元素个数最小的集合,其元素个数称为图的[1,2]-数.针对树的[1,2]-数的计算问题进行研究.首先,根据[1,2]-数的定义给出了一个0-1规划模型,求解这个0-1规划可以得到图的[1,2]-数的精确值.然后,基于贪婪策略将树进行星分解,给出计算[1,2]-数的两个近似算法.最后,分析了两个近似算法的计算复杂度和性能.

应用邓肯-张非线性模型近似计算路基沉降

提出了应用邓肯－张非线性模型对路基沉降量进行估算的近似算法。通过与规范算 法和实测沉降的对比分析，证明该算法是可靠的，可用于软土路基设计与施工控制。

带惩罚μ-相似Bregman散度k-均值问题的初始化算法

k-均值问题是聚类中的经典问题,亦是NP-难问题。如果允许数据点不聚类,而是支付惩罚费用,则引出带惩罚的k-均值问题。本文将带惩罚的k-均值问题从欧氏距离推广到更一般的μ-相似Bregman散度,研究了带惩罚μ-相似Bregman散度k-均值问题的初始化算法。本文给出的初始化算法,近似比与μ和数据点惩罚最大值与最小值的比例r相关。

控制集与部分控制集问题的原始-对偶算法

图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为Δ+1的近似算法(Δ为图中顶点最大度)。

基于改进SAX算法与贝叶斯超参数优化的配电网负荷-馈线智能匹配方法

新型电力系统下配电网运行方式调整愈来愈频繁,配电网负荷-馈线匹配面临采样数据高维异构且价值密度低、现有匹配算法对负荷物理特征依赖度高、参数设置灵活性弱等难点,为此提出一种基于改进SAX(符号聚合近似)算法与贝叶斯超参数优化的配电网负荷-馈线智能匹配方法。首先,建立面向离散符号化时间数据序列的数据价值提升模型,将高维异构的数据近似表示为低维统一的符号,修正和填充异常数据、空白数据。其次,构建改进CNN-LSTM(卷积神经网络-长短期记忆)混合神经网络,对负荷数据进行所属馈线匹配分类训练,利用多头注意力机制深入挖掘负荷数据的潜在数学关系,降低对负荷物理特征的依赖度。然后,引入贝叶斯超参数优化算法对神经网络训练参数进行逐次更新,提高馈线拓扑变化时神经网络模型的灵活性与适应性。最后,对某地区100条馈线进行负荷匹配实验验证,结果证明所提方法较传统方法具有更高的匹配精度。