Lower Bounds and a Nearly Fastest General Parallel Branch-and-Bound Algorithm

In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.

构造最小生成树的量子算法

图的最小生成树问题是网络优化中的一类基本问题。目前构造最小生成树的算法都是基于传统计算机的算法如Prim算法和Kruskal算法。该文提出了一个用于构造图的最小生成树的量子算法,它结合量子搜索的方法和经典Kruskal算法的思想,对于n个节点m条边的图,依次搜索出n-1条边使它们构成一棵最小生成树。这一算法的时间复杂性为O(nm√)。与经典Kruskal算法相比,在同等条件下,该文的算法有较快的加速。

考虑运营费用和线性化树形改编策略的货物列车开行方案研究

国外货物列车开行方案的制定通常以车流和车列的综合费用最小为目标,而我国大多以车流的集结和改编车小时消耗最小为目标,很少考虑每个车列的运营费用,造成理论开行费用偏小,其方案未必最优.此外,我国现有开行方案模型将车流树形改编策略递归表示,不利于对不可行流的处理.鉴于此,本文对现有模型进行改造,在总目标中增加车列运营费用;在约束中引入新的决策变量,实现线性化的车流树形改编策略.设计并行禁忌搜索算法实现对模型的求解.结果表明,单位列车运营费用中的固定费用对开行方案有着重要的影响,其费用越高,总开行列数越少,列车平均运距越长,但总改编车流量增加;线性化的改编策略直观展现车流的改编路径,便于对不可行流的运输方案进行调整.

知识库更新的研究

<正>一、研究现状 在知识库管理中,当人们获取了新的领域知识时,就需对原有知识库进行更新.对知识库的更新,从理论上讲,主要有以下三种基本操作~[4]

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。

光滑粒子流体动力学的一种并行数值计算方案

在三维超高速碰撞数值计算方面,针对三维光滑粒子动力学(SPH)方法计算量大和耗时长的缺点,文章提出了一种简单直接、易于编程实现的SPH并行计算方案,并简述了该方案的基本思想、任务划分、变量存储、信息传递以及主要计算步骤。最后利用自编并行程序计算了两个超高速碰撞实例,结果表明:针对几百万个粒子,在运算速度为每秒5万亿次的"银河"计算机上申请23个核并行计算,每步约需要8 s,加速比约为10,并行效率约为50%,计算时间显著减少。

一种基于规则分解映射的防火墙规则匹配算法

并行树搜索(PTS)算法是报文分类领域中较为优秀的算法之一,但它需要构建大量的external nodes,且只支持以前缀形式表示的规则,因此其匹配效率及适用范围都受到了很大的影响。针对这一问题,提出一种基于规则分解映射的规则匹配算法RMBRDM。RMBRDM算法首先按照启发式方法选取标准维;然后根据规则分解映射和标准维对相关规则进行分解;最后建立一棵二叉决策树。理论分析和仿真实验均表明,RMBRDM算法不仅支持以范围形式表示的规则,且时空性能优于PTS算法。

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

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

并行计算在机动飞行轨迹生成中的应用

针对现有通用机动轨迹需要较长的预规划时间,无法在机载计算平台实时解算的问题,提出一种利用并行计算的方式对通用机动框架进行加速的方法。对现有的MCTS算法叶子节点并行、根节点并行和树并行方式进行分析,结合叶子节点并行和根节点并行方式各自的优点,对每棵搜索树采用叶子节点并行方法,分别利用Pthread和CUDA对并行通用机动框架进行加速,并以筋斗机动为例对加速效果进行测试。实验结果表明:并行通用机动框架不仅性能优于串行框架,而且可大幅缩短机动解算时间。