立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一 .对于给定的问题和分枝策略 ,算法的运行时间取决于实现算法的数据结构 .该文讨论了立体堆及其上的插入、删除算法 ;通过将分枝界限算法的运作过程与排序过程建立对应关系 ,给出了一般分枝界限算法的复杂度下界Ω ( m+hlogh) ,其中 m为评估的结点数 ,h为扩展的结点数 ;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构 ;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法 ;

收缩背包问题的并行分枝界限算法

收缩背包问题 (collapsing knapsack problem,CKP)是 0 - 1背包问题的变体 ,其中背包的容量为所装物品数量的非增函数 ,针对并行计算的需要 ,在对 CKP问题分解的基础上 ,给出了求解每个子问题的分枝界限算法 ;提出了基于 MIMD- DM的收缩背包问题的并行分枝界限算法 ;并在曙光 10 0 0上设计和实现了该算法 ,以消息传递方式来解决子算法最优解的播送问题 ,同时给出了子问题的求解顺序 。

几乎最快与渐近最优的并行分枝界限算法(英文)

分枝界限算法是求解组合优化问题的技术之一 ,它被广泛地应用在埃运筹学与组合数学中 .对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω ( m / p +hlogp ) ,其中 p为可用处理器数 ,h为扩展的结点数 ,m为状态空间中的活结点数 .通过将共享存器设计成 p个立体堆 ,提出了 PRA M- EREW上一个新的一般并行分枝界限算法 ,理论上证明了对于 h<p2 p ,该算法为最快且渐近最优的并行分枝界限算法 .最后对 0 -

一种混合分枝界限算法及其性能分析

分枝界限算法是组合搜索中的常用方法之一 .本文提出了一种基于全局最优者优先 (GBF)与局部最优者优先 (LBF)的混合 .这一混合算法保持了GBF扩展结点数少的优点 ,并有效地降低了GBF算法的空间开销 ,改善了LBF策略特别是深度优先搜索的盲目性 .还提出了一种称作串队列的数据结构 ,不同于常用的堆结构 ,它既能快速地实施选择规则 ,又能方便地实现淘汰规则 .最后在PRAM CREW模型上对混合算法给出了并行化 .

一类有效的一般并行分枝界限算法

本文针对使用 p个处理器选出 p个子问题进行并行扩展的一类并行分枝界限算法 ,提出了一个称作双层立体堆的数据结构 ,给出了 PRAM- CREW模型上的并行分枝界限算法 .假定在状态空间树上扩展一个结点最多生成 r个子结点 ,本文提出的并行算法最多使用 r个处理器 ,其运行时间为 O((r/ logr) hlogh+ rh) .对于 logh <r <h,在系数因子 logh/ logr的范围内 ,以及对于 logh>r,在系数因子 r/ logr的范围内 ,本文提出的并行算法为运行速度最快的算法 ,其中 h为算法找到第一个最优解时所需的迭代次数 .

优先队列与并行分枝界限算法

讨论了分枝界限算法中使用的优先队列结构．针对分枝界限算法的选择规则和淘汰规则，提出了立体堆，双层立体堆，串队列三种新的结构；给出了各结构上相应的基本算法及复杂度分析．在此基础上给出了一类ＰＲＡＭＣＲＥＷ 模型上基于双层立体堆的并行分枝界限算法，其运行时间为Ｏ（（ｒ／ｌｏｇｒ） ｈｌｏｇｈ ＋ ｒｈ） ，其中ｒ 为可用处理器数，ｈ 为找到最优解时的迭代次数．

分枝界限法在压裂作业中的应用

压裂作业的组织者在组织区块压裂作业时必须根据压裂任务的变化,充分利用压裂设备,采用集中压裂形式,统筹安排每一区块的压裂井次,缩短施工周期,降低人力、物力的消耗,减少作业队伍的搬迁,从而保证及时、优质地完成压裂生产任务。为此,我们运用分枝界限法,以计算机为辅助手段,编制压裂作业的最优计划模型,对合理组织压裂作业生产进行了探索。

随时间变化的海洋平台结构系统可靠性分析

海洋平台在服役期间由于受到各种损伤，其系统可靠性将随时间而变化。本文分析了几种典型损伤——疲劳损伤、腐蚀损伤对海洋平台结构系统可靠性的影响，在考虑其对结构构件强度和承受载荷的影响情况下分析随时间而变化的海洋平台结构的系统可靠性。首先得到考虑时间因素的结构构件的强度和载荷函数，采用分枝界限法寻找结构的主要失效路径，最后以Ｄｉｔｌｅｖｓｅｎ界限法求取结构的系统失效概率。算例说明，在考虑时间因素的条件下，结构的系统可靠性将会迅速下降。按以上思路编制了空间刚架在构件强度随时间变化条件下的通用可靠性分析程序，算例表明程序是合理有效的。

TSP问题及几种常见算法的比较研究

TSP问题是一个经典的NP完全问题,它在众多领域中都有着广泛而有价值的实际应用,所以一直有众多的学者对其进行研究。从介绍TSP问题入手,从动态规划法、分枝界限法、遗传算法、蚁群算法等四种常见算法开始,在概述了各种算法的基本原理、程序设计的基本步骤的基础上,对各种算法的优缺点、时间复杂度、适用范围等几个方面进行了分析和比较。