树型网格下独立任务的实用调度算法

讨论在节点计算能力和网络通信速度异构的树型网格下独立任务的调度问题。与最小化任务总执行时间不同（该问题被证明是NP难题[1]）,本文修正[2]中为树型网格平台任务调度问题建立的整数线性规划模型,针对多层树通过线性规划模型求解最优任务分配数的时间复杂性大（ ）的问题,引入推拉方法,将多层树线性规划求解归结为单层树求解,复杂性降低为 ,其中 ,m为树的层数, 为第j层中节点的数目最多的节点的子节点数。基于求出的近似最优任务分配数,提出一个静态分布式的启发式任务调度算法。分析和实验表明,在异构的树型网格下做大量的独立任务调度时,算法性能优于同类算法。 关键词: 任务调度; 网格计算; 线性规划; 最优任务分配; 分布式任务调度算法;     

基于二分图最优完备匹配的目标关联算法

针对群目标编队飞行过程中的关联问题,提出基于二分图最优完备匹配的目标关联算法.该算法利用网格邻聚构造了目标关联二分图,并给出了二分图中边的权值定义;以二分图最优完备匹配作为约束条件建立了关联模型,通过求解最优解实现了目标的正确关联.用蒙特卡罗仿真结果对所提算法在各种不同的系统偏差、目标飞行间距环境中的关联性进行了比较验证,结果表明:所提算法能够取得良好的关联效果,可以有效地抵抗传感器系统偏差的影响,同时也大大降低了密集群目标关联的不确定性,其计算复杂度能够满足实际应用需求,从而证明了该算法的有效性和鲁棒性.     

基于改进型FP-Tree的分布式关联分类算法

传统的信息挖掘技术已经无法满足大数据环境下日益复杂的应用需求,而分布式数据挖掘技术是解决这个难题的一种手段,因此提出了基于改进型频繁模式树（FP－Tree）的分布式关联分类算法。首先,在各局部节点优化FP－Tree。生成局部条件模式树（CFP－Tree）,再通过各节点间传送CFP－Tree构建全局CFP－Tree;其次,在挖掘全局CFP－Tree时通过计算显著度来获取初始的全局显著分类规则;最后,利用剪枝策略选取一个较小规则集来构造全局的关联分类器。实验结果表明该算法能够有效降低网络通信量,提高信息挖掘效率,同时保证剪枝的质量和规则的统计显著性,提高分类的精确性。     

基于遗忘系数的LDPC译码算法研究

长LDPC码的Tanner图中通常没有环路,此时LLR BP译码算法是性能最优的软判决译码算法.而短LDPC码的Tanner图中通常存在环路,因此变量节点之间的信息就不再相互独立,这时LLR BP译码算法的译码性能就会下降.针对短LDPC码的特点,提出一种改进型LLR BP译码算法,利用遗忘系数来计算该算法中的参数.仿真结果表明,与LLR BP译码算法、Normalized BP译码算法以及Offset BP译码算法相比,改进型LLR BP译码算法能够在降低算法复杂度的同时提高环路存在情况下的LDPC译码性能.     

高频地波雷达的阵列互耦校正

针对分布式高频地波雷达（HFSWR）的工程应用,研究了基于自适应混合算法（AHA）的阵列无源校正方法.该方法将阵列误差估计问题转化为多元参数的联合估计问题,利用改进的混合算法得到了该优化问题的最优解估计.利用海洋回波校正了分布式高频地波雷达阵列幅相误差之后,将该方法应用到雷达系统的阵列互耦误差校正.仿真和现场实验实测数据的分析表明,该方法对空间谱算法性能的改善十分明显,验证了其有效性.     

基于链路重要性的分布式网络可靠性评价方法

为了快速有效地评估分布式网络可靠性,针对目前最有效的HRFST算法在搜索最小文件生成树过程中存在的3个问题,提出了一种基于链路重要性的分布式网络可靠性评价方法.该算法以链路重要性为最小文件生成树的首要搜索依据,提高了干路被选中的概率.将改进的网络化简方法用于搜索的每一步,使图更为简化,并消除了对不含文件生成树的子图搜索.分析和实验结果表明,在得到正确可靠性结果的基础上,该算法减少了子图产生数量和分析可靠性的实际执行时间,性能优于其他算法.     

毛毛虫树三角和四边形变换下的割宽不变性

图的割宽问题在一般情形下,是NP难的,但对于树的情形有多项式算法.本文对于毛毛虫树给出了对其进行三角和四边形变换后,割宽保持不变的充分必要条件.     

非对称不确定性越库调度算法

在正态分布的模式下,对运输时间期望值进行修正,采用修正后的期望值计算确定性情形下的最优解以及不确定性情形下的现实解和最优解并分别加以比较,提出了期望值修正算法和基于修正期望值的启发式算法.采用最小化最大完工时间作为目标函数,研究了运输时间非对称不确定性条件下的直运物流调度问题.数值实验结果表明,因考虑了非对称性,所提出的修正策略的有效性和实用性较高.     

带有锥约束的全局最优化问题的修正拉格朗日方法

针对锥约束的非线性规划问题,给出了一个基于修正拉格朗日的全局优化算法,这类算法可广泛应用于工程设计和非线性系统分析等实际问题中.对于每一次迭代k,当εk→ε时,给出了与该锥约束修正拉格朗日方法相对应的εk—全局最优解,并证明了算法全局收敛到ε—全局最优解.     

最小最大路划分的一个启发式算法

首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.     

具有状态支付向量的有向图上的动态对策

通过在有向图的每个状态结点处引入状态支付向量,运用C．Berge关于图上对策中策略的概念,在有限图上研究动态对策。在非合作情形,证明了具有状态支付向量的有向图上对策的精练均衡的存在性定理。在合作情形,通过建立有向图上局与对策树上路径之间的对应关系,将有向图上的对策转化为对策树,并给出了特征函数的算法以及以Shapley向量作为合作解的计算示例。     

一种故障树模块的划分方法

故障树中模块的划分可以有效地降低故障树分析的计算代价 .基于在图中寻找强连接节点的算法 ,给出一种线性时间复杂度算法来检测故障树中的模块 .该算法通过对故障树进行两次深度优先最左遍历来实现 ,其复杂度与故障树中的节点数、边数之和呈线性关系     

基于面向对象软件的故障树技术研究

故障树模型是导致系统失效的基本事件之间逻辑关系的图形表示,应用于系统失效模型的定性和定量分析.面向对象软件可靠性分析过程包括面向对象软件故障树构造、故障树简化及量化、依据基本事件失效概率确定系统失效( 顶部事件)的概率等.继承性是面向对象软件的特性.文章提出了一个从类的继承关系图( 类层次图或类格)构造面向对象软件故障树的构造算法,并且提出了构造多层故障树的设想 .     

含奇异网络元件的全符号网络函数分析

本文研究含有nullor元件的一般线性时不变网络的全符号网络函数。定义了电压图、电流图及公共树后,不需电路变换,也不需构成信号流图,就可以用数码运算产生符号网络函数.     

一致性验证的结构化激励生成算法

为解决Cache一致性验证中传统随机激励方法的冗余覆盖及覆盖死角等问题,提出了一种高层次结构化激励生成算法和相应的高层次功能覆盖率模型.首先根据实际多核应用场景将冲突访存操作分类成基本同步和复杂同步,并进一步抽象成有向二分图模型,由此提出一种通用的层次化输入空间等价类划分算法和对应的高层次HSPC（Host Slave Pair Coverage）功能覆盖率模型,最后基于树的搜索提出了结构化激励生成算法.上述方案成功应用于IME-Diamond SoC的Cache一致性的功能验证中,实际结果表明,相比传统基于代码的覆盖率,高层次HSPC功能覆盖率模型的揭示功能Bug能力更强,而且相对于传统的随机生成,结构化的激励能够将覆盖率收敛所需的激励数减少96.3%.     

针对带约束匹配搜索的扩展Kuhn-Munkres算法

提出了扩展的Kuhn-Munkres算法,可解决带下界约束的局部匹配存在性问题,即在匹配全集的给定子集中,搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树,利用搜索优先级和剪枝,将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．      

连通图的基本割集多项式生成所有支撑树的一种证明

连通图必存在支撑树,且支撑树一般不唯一。如何得到连通图的所有支撑树,是图论中讨论的一个重要问题。利用基本割集对应的子图多项式生成所有支撑树是一个简单可行的方法[1],现有的对这种方法的理论证明较繁琐。本文给出一种较直观的证明,说明该方法可生成全体互异的支撑树。     

广义树网络中的多端割

给定一个边赋权图和k个顶点(称为终端)的集合,多端割问题是要找到一个最小 权的边集,该边集使得每一个终端与其他所有的终端分离.对于一般图来说,当k为不小于3的常数时,这一问题是NP-难解的.对于广义树网络给出了这一问题的一个多项式时间精确算法.     

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

图的标号问题的计算机算法

时至今日,寻找一个图是否有优美标号和序贯标号的充要条件的问题仍是开的。 实际中,寻找一个稍大一点的图的优美标号和序贯标号是一件困难的事。本文对这两件工作给出了一种统一的算法,使得我们利用电子计算机可解决:一、验证一个图是否有优美标号和序贯标号。二、若有,则给出所有的优美标号和序贯标号。 本文用BASIC语言给出了本算法的一个程序。