最小费用充电站选址问题的分支定界算法 被引量：7

1

作者 孙智勇 宁爱兵 +2 位作者 傅汤毅 尹思淼 张惠珍 《计算机应用研究》 CSCD 北大核心 2022年第1期80-83,共4页

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规... 电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。 展开更多

关键词 充电站选址 精确算法 上界算法 下界算法 分支定界算法

下载PDF 职称材料

基于Map/Reduce的时间序列相似性搜索算法 被引量：4

2

作者 王会青 孙宏伟 张建辉 《山东大学学报（工学版）》 CAS 北大核心 2016年第1期15-21,共7页

将并行计算的策略引入到时间序列处理中,提出基于Map/Reduce的时间序列相似性搜索算法,充分利用云计算可进行大规模计算和数据处理的特点,有效降低了时间序列相似性搜索中运算量,简化了计算过程。该算法在心电图数据集上进行相似性搜索... 将并行计算的策略引入到时间序列处理中,提出基于Map/Reduce的时间序列相似性搜索算法,充分利用云计算可进行大规模计算和数据处理的特点,有效降低了时间序列相似性搜索中运算量,简化了计算过程。该算法在心电图数据集上进行相似性搜索,分别进行PAA下界过滤和DTW距离的计算,验证运算时间和并行加速比随节点变化的情况,与传统的单机运算相比,有效地提高了时间序列挖掘效率。 展开更多

关键词 并行计算 时间序列挖掘 相似性搜索 动态时间弯曲距离 下界算法

原文传递

充电站选址问题的降阶回溯算法 被引量：2

3

作者 孙智勇 宁爱兵 +2 位作者 傅汤毅 夏萌萌 张惠珍 《系统科学与数学》 CSCD 北大核心 2020年第7期1133-1145,共13页

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-难问题.文章首先研究了该问题良好的数学性质并给予相应的证明,其中包括可以批量确定某些设施一定开设或一定不开设的性质,利用这些性质降低问题的规模,从而... 电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-难问题.文章首先研究了该问题良好的数学性质并给予相应的证明,其中包括可以批量确定某些设施一定开设或一定不开设的性质,利用这些性质降低问题的规模,从而降低问题的求解难度;然后设计了上界子算法,下界子算法,分配子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解一个示例来进一步阐述文章算法的原理和执行过程,结果表明所提出的算法能够有效地降低时间复杂度. 展开更多

关键词 充电站选址 精确算法 上界算法 下界算法 回溯算法

原文传递

最大覆盖选址问题的一种降阶回溯算法 被引量：2

4

作者 彭大江 宁爱兵 +1 位作者 尚春剑 张惠珍 《系统管理学报》 CSSCI CSCD 北大核心 2020年第2期346-353,共8页

最大覆盖选址问题在实际生活中有广泛的应用,是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法,然后研究数学性质,其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后,利用上下界子算法和这些数学性质设计出一... 最大覆盖选址问题在实际生活中有广泛的应用,是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法,然后研究数学性质,其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后,利用上下界子算法和这些数学性质设计出一种可以快速减小问题规模且能求出最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程。 展开更多

关键词 最大覆盖选址问题 精确算法 上界算法 下界算法

下载PDF 职称材料

锥上的线性规划的基线算法 被引量：2

5

作者 方秋莲 胡朝明 阮国桢 《长沙铁道学院学报》 CSCD 北大核心 2002年第3期74-78,共5页

针对锥上的线性规划问题的求解 ,在基线算法理论的基础上 ,提出并讨论了基线算法的一种具体的实现算法———保界算法 ,并证明了它的可行性和收敛性 .

关键词 线性规划 基线算法 锥 保界算法 可行性 收敛性

下载PDF 职称材料

灾后应急配送中心选址问题的降阶回溯算法

6

作者 胡开元 宁爱兵 +2 位作者 尹远翔 陈至伟 张惠珍 《物流科技》 2024年第16期1-5,共5页

近年来自然灾害频发,提高灾后应急物资的配送效率一直以来都是性命攸关的大事,因此文章基于灾后应急配送中心选址问题的精确算法进行研究。首先,建立该问题的数学模型并对该问题中的数学性质进行研究和证明;其次,在这些数学性质的基础上... 近年来自然灾害频发,提高灾后应急物资的配送效率一直以来都是性命攸关的大事,因此文章基于灾后应急配送中心选址问题的精确算法进行研究。首先,建立该问题的数学模型并对该问题中的数学性质进行研究和证明;其次,在这些数学性质的基础上,设计上下界子算法和降阶子算法,这些子算法能够有效减少解空间,提高算法的效率,使该算法能够更有效地处理规模更大的问题;再次,提出降阶回溯子算法,通过剪枝和局部降阶进一步缩小问题的搜索规模,并能得到最优解;最后,通过分析和解决一个案例来更清楚地说明算法的原理和操作步骤。 展开更多

关键词 应急配送中心选址问题 上下界算法 降阶回溯算法

下载PDF 职称材料

最小支配阈值集问题的降阶回溯算法

7

作者 储旭 宁爱兵 +2 位作者 胡开元 代苏玉 张惠珍 《计算机工程与科学》 CSCD 北大核心 2024年第5期897-906,共10页

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小... 图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。 展开更多

关键词 最小支配阈值集问题 数学性质 上下界算法 降阶回溯算法

下载PDF 职称材料

有约束竞争选址问题的降阶回溯算法 被引量：1

8

作者 傅汤毅 宁爱兵 +2 位作者 孙智勇 林道晗 张惠珍 《计算机应用研究》 CSCD 北大核心 2021年第12期3678-3682,共5页

有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢。针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并... 有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢。针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶,达到了缩减问题搜索解空间的目的,降阶的过程中既有单个的降阶,也有成批的降阶;然后在前面的基础上设计了一个回溯子算法来求解问题的最优解;最后通过两个示例分析更清楚地阐述该算法的原理,结果证明该算法可以较快求得最优解。 展开更多

关键词 竞争选址 上下界算法 降阶算法 回溯算法

下载PDF 职称材料

瓶颈TSP下界快速算法

9

作者 宁爱兵 马良 王周缅 《科学技术与工程》 2006年第9期1260-1263,共4页

瓶颈TSP是网络设计和优化中的一个NP难题,在数学推导和证明的基础上,给出了一个求解对称型瓶颈TSP问题下界的快速算法,利用该算法求解了TSP问题标准库中部分对称型问题,给出了计算结果并与标准问题库中已知的最好解进行了比较。

关键词 瓶颈TSP 下界 算法 逼近程度

下载PDF 职称材料

最小连通顶点覆盖问题的降阶回溯算法

10

作者 曾宾 宁爱兵 +2 位作者 付振星 李之桥 张惠珍 《运筹与管理》 CSCD 北大核心 2024年第3期28-34,共7页

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问... 本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。 展开更多

关键词 最小连通顶点覆盖 上界子算法 下界子算法 回溯子算法

下载PDF 职称材料

Logistic回归模型中参数极大似然估计的二次下界算法及其应用 被引量：3

11

作者 王佳 丁洁丽 《数学杂志》 CSCD 北大核心 2015年第6期1521-1532,共12页

本文研究了Newton-Raphson等算法无法进行时探寻更加稳定的数值解法的问题.利用B¨ohning&Linday(1988)提出的二次下界算法(Quadratic lower-bound),文中在Logistic回归模型下构造了极大似然函数的代理函数并进行数值模拟,获得... 本文研究了Newton-Raphson等算法无法进行时探寻更加稳定的数值解法的问题.利用B¨ohning&Linday(1988)提出的二次下界算法(Quadratic lower-bound),文中在Logistic回归模型下构造了极大似然函数的代理函数并进行数值模拟,获得了二次下界算法是Newton-Raphson算法的合理替代的结果,推广了数值方法在Logistic回归模型中的应用. 展开更多

关键词 minorization-maximization算法 LOGISTIC回归模型 QUADRATIC lower-bound算法 极大似然估计 Newton-Raphson算法

下载PDF 职称材料

调整时间与顺序相关的等同并行机调度 被引量：10

12

作者 胡大勇 姚振强 《机械工程学报》 EI CAS CSCD 北大核心 2011年第16期160-165,共6页

调整时间与顺序相关的等同并行机调度在生产服务业与制造业中有着十分广泛的应用背景,具有计算复杂性的主要特点。调整时间与顺序相关的等同并行机调度是将被加工工件集的各工件分配给等同并行机资源,并安排工件的加工次序。它是决策的... 调整时间与顺序相关的等同并行机调度在生产服务业与制造业中有着十分广泛的应用背景,具有计算复杂性的主要特点。调整时间与顺序相关的等同并行机调度是将被加工工件集的各工件分配给等同并行机资源,并安排工件的加工次序。它是决策的一种形式,其目的是优化一个或多个目标。研究以最小化被加工工件最大完工时间为目标的调整时间与顺序相关的等同并行机调度,建立该问题的数学规划模型,根据问题的结构特点开发基于两段式染色体表达的遗传算法以获得该问题的近似最优解;在所建立数学规划模型的基础上,引入所求解问题的下界对近似最优解的质量进行评价。对具有不同规模的问题实例进行计算试验,计算结果表明所设计的遗传算法能够在可接受的计算时间内获得合理的解。 展开更多

关键词 等同并行机调度 调整时间与顺序相关 数学规划模型 下界 遗传算法

下载PDF 职称材料

奖励-收集顶点覆盖问题的精确算法

13

作者 曾宾 宁爱兵 +2 位作者 付振星 徐江盼 张惠珍 《计算机时代》 2023年第5期51-56,共6页

奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数... 奖励-收集顶点覆盖问题是顶点覆盖问题的衍生问题,同时也是组合优化NP-hard问题。本文提出该问题的数学性质并给出证明,利用数学性质能够确定某些顶点一定在或一定不在最优奖励-收集顶点覆盖集中,从而降低该问题的规模;基于该问题的数学性质设计出上下界子算法、降阶子算法、回溯子算法,通过降阶子算法可以降低该问题的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间。通过应用和算法对比表明,所设计的算法比没有考虑该问题数学性质的一般精确算法的时间复杂度更低。 展开更多

关键词 奖励-收集顶点覆盖 上下界子算法 降阶子算法 回溯子算法

下载PDF 职称材料