改善分支限界法求解旅行商问题效率的策略

叙述了NP完全问题的复杂性及分支限界法求解问题最优解的策略,分析了利用分支限界法求解旅行商问题过程中影响算法求解效率的主要原因。针对欧氏空间的旅行商问题求解,提出了通过化简初始边集的策略,改善算法的求解效率,通过实验说明了该策略的有效性。该策略可应用到求解旅行商问题的其他算法中。

基于分支限界法的火电机组负荷分配研究

针对大规模新能源并网调峰问题,提出不同调峰阶段火电机组负荷分配方法:分析火电机组调峰能力、调峰成本及二者之间的关系;以总煤耗成本、机组启停成本之和最小为目标,建立不同调峰阶段火电机组负荷分配优化模型;根据火电机组爬坡率、滑坡率,提出参与负荷分配机组的组合策略,并使用分支限界法对负荷分配优化模型求解。算例表明,随着火电机组调峰深度的增加,机组煤耗成本和启停成本减少,深度调峰运行下附加煤耗成本和机组损耗成本增加。

回溯法与分支限界法的用法取向探讨

回溯算法与分支限界算法是两种用法非常相似,甚至某些问题两种算法都可以求解,因此有些初学者不容易严格区分这两种算法,可能在这两种算法的用法取向上出现误区。本文对这两种算法做深入分析,详细说明这两种算法的用法取向。

优先队列式分支限界法和蚂蚁算法的比较

叙述了近几年出现于优化领域的一种新的搜索策略———蚂蚁算法和传统的优先队列式分支限界法的基本思想,并进行了分析和比较。

优先队列分支限界法解多货车多货箱装载问题

由于车辆配备有限而快件量爆炸增长,使得物流企业快件派送的服务质量和派送时效无法有效满足需求。为了解决该问题,提出一种基于优先队列分支限界思想的算法并应用于多货车多货箱装载问题的求解。该方法利用贪心策略,采用分阶段分支限界方法装载每辆货车。实例分析表明应用该算法可以获得多货车多货箱问题的可行方案。

旅行商问题分支限界法的一个注解

在旅行商问题传统的分支限界法基础上提出一个新的方法,最后用算例检验了该方法能有效地求得最优解.

分支限界法在电力物资配送调配中的应用

在当今的电力行业发展中,电力企业的规模在不断扩大,对物资配送的要求也越来越高。电力物资配送受诸多因素的影响,对配送效率与时间都有较高的要求。文章针对电力物资配送调配中的车辆装载问题进行了分析,提出应用分支限界算法的解决方法,并对该方法进行了说明和实验例证。通过例证可证实应用分支限界法能够实现电力物资车辆装载的最优方案,有效缓解电力物资配送调配在车辆装载方面依靠纯人工经验模式带来的问题,提高车辆装载率和车辆利用率,降低配送成本。

线性整数规划的分支限界解法及其MATLAB实现

讨论了计算机算法中分支限界法对于线性整数规划问题的解决思想,通过MATLAB中提供的优化函数,实现了快速解决线性整数规划的问题,同时改进了对于此类问题的计算量巨大和编制程序困难的问题,使用了堆栈而不是递归,节约了计算中的资源。编制的MATLAB线性整数规划的程序,可以编译成C/C++实现和COM组件。

分支限界装载问题的算法分析与设计

该文主要介绍用分支限界的方法解决装载问题。首先给出对装载问题的描述;接着着重优先队列式分支限界法的算法设计思想和算法分析展开谈论;最后给出实验,用分支限界法来解决装载问题,从而得到集装箱装载问题的装载方案或者不存在合理的装载方案。

石油传输网络最少增压器问题的回溯与分支限界解法

回溯法和分支限界法是用于解决诸多问题的重要而有效的方法。本文首先提出石油传输网络中的最少增压器问题,然后介绍了基于回溯法和分支限界法的两种有效算法,最后对这两种算法进行了比较和讨论。实验结果验证了算法的有效性。

基于分治法和分支限界法的大规模TSP算法

利用分治法能够处理大规模问题但精度较低,分支限界法能够得到精确解但时间复杂度很高的优点,设计一种有效的基于分治法和分支限界法的大规模TSP求解方法.该算法利用聚类和凸包技术将大规模问题逐层进行有效划分,直到适合分支限界法求解的最佳规模;然后用分支限界法求出每个子问题和每层子问题间的最优解,合并而得到整个问题的解.比较实验表明:该算法在求解质量、稳定性和时间效率上有明显优势.

带有度约束的最小耗费生成树的分支限界算法

最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。

基于分支限界算法的横折臂混凝土布料机构避障布料分析

通过对横折臂混凝土布料机构、建筑结构布料区域、障碍区域的合理简化,在平面坐标系下建立了横折臂混凝土布料机构避障布料的数学模型,推导出横折臂布料机构考虑关节转角的状态函数。通过对横折臂布料机构状态函数和障碍区域边界函数的位置关系分析,在线段定义域重合的判别条件的基础上,推导了横折臂混凝土布料机构避开障碍区域的充要条件。结合模型的约束条件,基于分支限界算法,进行了横折臂布料机构避障布料问题的求解算法设计,并通过工程算例验证了算法的高效可行。

对分枝限界法的一种改进

分枝限界法是寻找结构主要失效模式的一种常用方法，但由于涉及到联合概率的计算而使过程繁琐。本文针对这一缺陷，将PNET法的思想引入到分枝限界法中，取消了限界操作，大大简化了计算过程。算例表明，经过改进的分枝限界法所得结果是可靠的。

软件定义数据中心网络基于分支界限法的多路径路由算法

数据中心网络中大、小数据流分布不均、传输性能要求各异,已有算法往往片面强调大、小流各自性能要求,而忽视全网性能优化.为此,综合考虑数据流的特点以及链路时延和剩余带宽两种因素的影响,提出一种基于分支界限法的多路径路由算法.该算法首先利用分支限界法获取链路剩余带宽尽可能大、链路时延尽可能小的网络子集;随后,提出最小网络连通子集、瓶颈时延、瓶颈带宽等概念,给出软件定义数据中心网络连通条件,在此基础上,依据大、小流各自性能要求在网络子集中利用不同策略为它们选择合适路径;最后,通过Mininet和Floodlight进行仿真测试.仿真结果表明:与文献中已有算法相比,所提算法具有更低的分组端到端时延、更高的网络吞吐量和平均链路利用率.

求解0-1背包问题的多种算法策略的分析

0-1背包问题是一个经典的组合优化问题,常常被应用于资源分配、物流管理等领域,并且在计算机科学和数学中具有重要的理论价值。解决0-1背包问题有多种策略,常见的策略为动态规划法、回溯法和分支限界法,为了确定对该问题求解的最有效方法,研究三种算法求解的性能表现是十分必要的。通过探讨求解0-1背包问题的三种不同算法,并给出该问题的动态规划法、回溯法和分支限界法的求解思路和算法设计,然后通过实验对比和分析三者的运行时间效率。实验表明,三种算法各具优缺点,要根据问题特点和需求来灵活选择算法。

高效识别桁架结构主要失效模式的一种新方法

在对现有两大类主要失效模式识别方法进行深入分析基础上,针对保留的候选失效元并非都是组成失效模式必备单元的问题展开研究.利用结构力学基本理论,分析了单元失效对残余结构内力影响规律,并推导了其关系式;通过该关系式,证明了具有相同基本失效单元的失效模式间线性相关;结合概率论相关理论,得出主要失效模式一定只包含基本失效单元的结论,由此证实了组成主要失效模式的必备单元就是基本单元;基于结构几何构造分析理论,分析了结构体系的失效形式,讨论了形成结构体系失效的基本单元范围;进而采用对结构进行逐步搭建的思想,建立了基本单元最小存在范围的划分方法;与分支限界法结合提出一种新的桁架结构主要失效模式识别方法;通过算例分析,证实该方法合理有效,且具有较高识别效率,同时能保证不遗漏主要失效模式.

基于0-1背包问题的两种算法

0-1背包问题是组合优化领域里的一个典型问题,是属于易于描述却难于解决的NP难题,有效解决0-1背包问题具有重要意义。首先给出了0-1背包问题的描述,然后详细介绍了回溯法和分支限界法的算法思想和搜索策略,并对两种算法进行了比较和分析。

海洋平台水下结构累积损伤失效路径的动态搜寻方法

介绍了海洋平台水下结构累积损伤失效路径的动态搜寻方法,重点阐述了增量载荷法,分支限界法和β-解链法,及对方法的某些合理改进,最后指出了各种方法的优缺点,并提出了目前解决失效路径动态搜寻所存在的一些关键问题。

多核系统的多应用任务映射方法研究

在多核处理器系统中,多个计算任务映射到多核处理器内核的方式对于系统吞吐率至关重要。针对此问题提出一种新的多应用任务到多核的映射算法,该算法在应用到来之前预测应用的相关性能,并采用分支限界法提前为未来应用预留合适的内核几何位置。当应用真正到来时,根据预留的区域完成映射。实验结果表明,该算法相比其他传统算法,在多任务通信量的减少和多核系统的吞吐率等方面都收到了良好效果。