二级垃圾回收中转设施选址问题的降阶回溯算法

随着我国城市化进程的加快和经济的高速发展,城市中因生产生活所产生的垃圾废料量日益增加,如何有效地建立回收中转设施是当前社会需要解决的问题。对二级垃圾回收设施选址问题进行研究,其实质为组合优化中的NP-hard问题。首先根据实际情况对二级垃圾回收中转设施选址问题进行数学建模,研究该问题的数学性质并给予证明,利用这些性质减小问题规模,降低求解难度;然后设计符合该问题的分配子算法、上下界子算法,基于以上算法提出一种可以在减小问题规模的同时得到精确解的降阶回溯算法;最后通过分析和模拟若干个示例进一步阐述该算法的原理及执行过程,结果表明该算法能通过减小问题规模,降低问题求解的难度。

奖励-收集Steiner树问题的精确算法

奖励-收集Steiner树问题是图的Steiner最小树问题的衍生,同时也是组合优化中的NP-hard问题。首先,提出该问题的数学性质并给出证明,利用数学性质能降低该问题的规模;其次,基于该问题的数学性质设计出上下界子算法、降阶子算法和回溯子算法,通过上下界子算法和降阶子算法可以降低该问题解空间的规模,从而缩短回溯子算法的搜索时间,进而降低求解该问题最优解的时间;最后,应用案例分析、算例分析以及算法分析与对比表明,所设计的算法不仅可以求出该问题的最优解,而且比没有考虑该问题数学性质的一般回溯算法的时间复杂度更低。

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

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

考虑容量和成本的最大最小分散度选址问题的降阶回溯算法

最大最小分散度问题可简单描述为:在给定的集合中选择包含固定元素个数的子集,使得该子集中的元素在给定距离度量下的最小距离最大;该问题在生产生活中有广泛的应用.近些年来,该问题的一种考虑容量下限和成本上限的变体开始引起学者们的关注,并已被证明为NP-Complete问题.基于考虑容量和成本的最大最小分散度选址问题进行研究,首先提出该问题的数学性质并证明,利用这些性质可以减小问题规模或缩减搜索空间,以加快问题的求解速度,然后设计了上下界子算法及降阶子算法;基于这些子算法提出一种可大幅缩减搜索空间并能得到最优解的降阶回溯算法.通过分析和求解一个示例来阐述该算法的原理和执行过程,并通过随机算例测试、算法对比分析和案例分析进一步验证了该算法的可行性和有效性.结果表明该算法可有效通过大幅缩减搜索空间加快问题的求解速度.

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

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

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

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

疫情期间生活物资集散点选址问题的降阶回溯算法

疫情爆发后,封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一,该问题可抽象为疫情期间生活物资集散点选址问题,其实质为组合优化中的NP-hard问题。基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究,首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出分配子算法、上下界子算法以及降阶子算法;基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程,结果表明该算法能通过减小问题规模来降低问题求解的难度。

TST问题的降阶回溯算法

考虑Terminal Steiner Tree(TST)问题中特殊结点及其关联边之间的关系、结点之间的权值比较、可行解的连通性等几个方面,提出该问题的相关数学性质,判断问题中结点与边是否一定在或一定不在最优解中;利用上下界子算法对降阶回溯算法的解空间进行剪枝,加快了算法求解问题的速率,最后通过算法复杂度分析证明算法的有效性。

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

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

竞争决策算法原理及其应用

全面阐述竞争决策算法的基本概念、原理、算法流程、特点,给出了常用的竞争力函数、决策函数、初始状态、资源交换规则,并以示例来说明该算法的原理、特点及应用.研究内容进一步完善了竞争决策算法的基本理论,在应用方面则降低了算法应用的难度.

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.

多目标旅行商问题竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来到达优化目的的新型寻优算法。给出了用竞争决策算法求解多目标旅行商问题的算法,经过大量数据测试和验证,获得了较好的结果。

竞争决策算法及其在车辆路径问题中的应用

在分析自然界各种竞争机制和人类社会决策原理的基础上,利用竞争造就优化和决策左右结果的特性,提出了一种能广泛应用于组合优化难题的新型算法———竞争决策算法(CDA),并给出了CDA的通用模型.车辆路径问题(VRP)是一个著名的NP难题,也是物流领域内一个重要的调度问题,利用CDA的通用模型设计了一个针对VRP的快速求解算法,并用该算法求解了VRP标准测试库中的实例,经过大量数据测试和验证,获得了令人满意的效果,其中部分问题的解优于目前公布的最好解.

城市物流配送中的三维装箱算法

针对城市物流多种类物品三维装箱问题,设计了一种新的求解算法。该算法把三维空间分割成小长方体方格并用相应的数据结构来表示。它能处理多种类物品混装的情况,允许一个货物在6个方向上旋转,该算法与车辆路径算法结合就易于得到一个完整的城市智能物流配送算法。

0/1背包问题竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来到达优化目的的新型寻优算法。在考虑0/1背包问题特点的基础上给出了用竞争决策算法求解0/1背包问题的算法,经过大量数据测试和验证,获得了较好的结果。

大规模旅行商问题的竞争决策算法

针对旅行商问题,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想,能求解大规模和超大规模TSP问题的快速求解方法,经过大量数据测试和验证,获得了较好的结果。

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试和验证,并与其它算法的结果进行了比较,得到了较好的结果.

最小比率旅行商(MRTSP)问题竞争决策算法

针对最小比率旅行商问题,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想、能求对称型最小比率旅行商问题的快速求解方法,经过数据测试和验证,获得了较好的结果。

基于快速下界估算的瓶颈旅行商问题竞争决策算法

利用数学推导和证明得出了一个瓶颈旅行商问题下界快速估算法,在此基础上利用竞争决策算法(新型优化思想)的通用模型,给出了一种瓶颈旅行商问题的竞争决策算法,经过大量数据测试和验证,并将求解结果与下界相比较,部分结果与下界相同.

最大团问题降阶算法

最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.