网络最大流问题求解的代数决策图(ADD)技术

Hachtel G.D.和 Somenzi F.提出的 0 - 1网络最大流问题的符号有序二叉决策图 (OBDD)算法在一定程度上缓减了“状态爆炸”问题 ,但算法仅局限于求解 0 - 1网络的最大流。Bachar R.I.等提出的代数决策图 (ADD)数据结构 ,是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用 ADD存储表示网络及描述网络最大流问题 ,给出一种求解网络最大流问题的符号 ADD技术新思路。实验结果说明了应用 ADD技术求解一般网络最大流问题的有效性 ,可处理 0 - 1网络最大流问题的符号 OBDD算法无法处理的非 0 - 1网络。

加权约束满足问题的改进RDS符号代数决策图求解算法

加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.

基于代数决策图的路由查找算法

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。

基于代数决策图的贝叶斯网络参数简化技术

贝叶斯网络是一种进行不确定性知识表达和推理的有效工具,推理算法是贝叶斯网络研究的主要内容之一.目前,贝叶斯网络推理算法采用条件概率表(CPT)来存储贝叶斯网络中各节点的条件概率分布(CPD).CPT中的概率参数随父节点数目的增加呈指数增长,使得网络中概率参数急剧增加,降低了网络推理效率.为提高网络推理效率,本文提出采用代数逻辑图(ADD)取代CPT存储网络中各节点CPD的方法.结合有序二分决策图理论,分析并验证了ADD通过捕捉贝叶斯网络中父子节点之间的环境独立性来减少网络中的概率参数的原理,进而推导出了CPT到等价ADD转化的算法.最后,通过实例验证了ADD存储方式的有效性.结果表明,对于具有环境独立特性的贝叶斯网络,相对于CPT的存储方式,等价ADD存储方式可有效减少网络中的概率参数,为贝叶斯网络推理效率的提高提供一种有效手段.

二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构,在KM算法基础上,提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念,将传统的匹配选择转化成布尔运算,"并行"地搜索匹配集合。实验结果表明:与传统算法相比,该算法可以改善问题的状态空间复杂度。

网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图(ADD)描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法。与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善。实验结果表明,本文算法是切实有效的,且可处理更大规模的问题。

基于符号ADD和线性多分支程序的分类算法安全评估

分类算法是机器学习和数据分析中重要的算法.当需要对分类算法本身以及算法的输入数据进行隐私保护时,就出现了分类算法安全评估问题.针对现有的分类算法安全评估协议效率较低的问题,文章给出了一种基于代数决策图和线性多分支程序的解决方案.首先,设计了基于代数决策图的安全函数评估协议,用以安全评估决策函数;其次,引入了线性多分支程序的概念,用其对分类算法进行表示.最后,借助线性多分支程序和基于代数决策图的安全函数评估协议,给出了一个私有线性多分支程序的安全评估协议.对新的协议的正确性和安全性进行了分析和证明.实验数据表明,与原有的解决方案相比,新的协议在效率上有明显的提高.

一种故障树预处理和最小割集的嵌套求解方法

故障树分析(Fault Tree Analyze,FTA)是一种系统安全性分析方法。求解故障树最小割集(Minimum Cut Set,MCS)是FTA的重要环节,其方法主要包括基于布尔代数的算法和基于二元决策图(Binary Decision Diagram,BDD)的算法,在使用普通计算机分析大规模故障树时,现有方法存在工作内存不足和计算时间过久的问题。为了解决上述问题,针对国内某百万千瓦级大型压水堆风险模型,提出了一种基于布尔代数的故障树预处理和最小割集嵌套求解算法(Pretreat and Nested Minimum Cut-Set Algorithm,PNMCS)。该算法由三个模块组成:故障树化简、故障树剪枝、最小割集嵌套计算。在国内某大型压水堆风险模型和几种实际应用风险模型上的应用表明,本算法在求得正确结果的同时,有效解决了工作内存不足和计算时间过久的问题。

有序二叉判定图及其构造算法研究

有序二叉判定图OBDD(orderedbinarydecisiondiagram)是一种数据结构 ,它把布尔函数表示为有向无回路图 ,是布尔函数的一种正则表示 ,可以用来检查布尔函数的一些性质如可满足性、等价性等等。本文将详细地介绍OBDD的数据结构及基于OBDD的布尔函数运算 。

弧一致性符号ADD算法及在CSP求解中的应用

约束满足问题(CSP)是人工智能领域中一个重要的研究课题,弧一致性(AC)技术是提高约束满足问题求解效率的一种有效技术。对传统弧一致性技术进行了改进,给出了弧一致性的符号代数决策图(ADD)算法并将其应用于CSP求解。传统弧一致性技术在压缩问题的搜索空间时,一次只能处理一条约束上的一个值对;而借助ADD技术来压缩问题搜索空间,可以一次处理多条约束。算法首先通过01编码将CSP问题描述成伪布尔函数,并由ADD进行表示。然后基于传统弧一致性技术的算法思想,利用ADD的交、并和提取操作来实现约束传播和变量域过滤。最后将弧一致性的符号ADD算法嵌入到BT搜索算法中来实现对CSP的求解。对标准库中的测试用例以及随机生成的测试用例进行了实验仿真,结果表明,该算法求解CSP的时间既优于带弧一致性维护的回跳算法MAC3+BJ和MAC2001+BJ,也优于采用传统数据结构进行预处理的CSP求解算法BT+MPAC和BT+MPAC*。

基于改进树分解技术的约束满足问题的符号ADD求解算法

为提高大规模约束满足问题(CSP)的求解效率,提出了基于改进树分解技术的符号ADD求解算法。通过CSP的ADD描述,将树分解技术的树聚类与符号ADD结合,以提高算法的求解效率。采用改进最大基数(MC)的变量选择法,提高构造弦图的效率,引导团的构造以及连接树的生成。对大量随机生成的测试用例进行实验仿真,结果表明,基于改进树分解技术的符号ADD求解算法求解效率优于BT-FC-ADD算法和BT-ADD算法。

一种新型基于子图的波长转换器配置算法

文章在已有的＂子图＋ADD（代数决策图）＂波长转换器配置算法的基础上,将节点在路由上的平均中心距离作为权值对节点进行排序,提出了用优先配置中心节点的启发式思想对该算法进行优化,得到了新的算法,即＂子图＋CNF（中心节点优先分配）＂算法。对本算法进行计算机仿真,结果显示新算法在保证结果准确的同时,有效降低了运算的时间复杂度。

基于图神经网络的子图匹配符号算法

子图匹配是图数据分析中的基础问题,具有重要的研究意义。针对子图匹配求解算法存在大量冗余搜索的问题,提出了一种基于图神经网络的子图匹配符号算法。该算法利用图神经网络技术聚合节点的邻域信息,得到包含图局部属性和结构的特征向量,以该向量作为过滤条件得到查询图的节点候选集C。此外,优化匹配顺序并利用符号ADD操作在数据图中构建C的各个候选区域,减少了子图枚举验证过程中的冗余搜索。实验结果表明,与VF3算法相比,该算法有效地提高了子图匹配的求解效率。

基于概率转移矩阵的电路可靠性并行计算方法

随着电路集成度的提高,软差错已经成为影响可靠性的关键因素.概率转移矩阵是一种用于估计软差错对电路影响的有效方法,它通过对门级电路建立概率模型来计算电路的可靠性.本文基于概率转移矩阵研究计算电路可靠性的并行方法,提出了一种电路分割算法,在对电路进行划分后,并行地计算各个模块的概率转移矩阵,再合成对应于整个电路的概率转移矩阵.其中,引入了代数决策图压缩矩阵存储空间.初步的实验结果表明,该并行算法可以有效地减少21.46%的平均时间开销.

波长转换器在国网OTN骨干网络的配置问题研究

为降低系统成本,文章通过部分配置波长转换器的方法缓解国网OTN骨干网络的波长连续性限制,并保障波长的资源利用效率。对国网OTN网络中波长转换器配置问题进行了理论研究,详细阐述了子图+ADD算法及其改进算法的设计思想,对各个算法的性能进行分析,在国家电网公司大容量骨干光传输网拓扑上进行仿真,并给出波长转换设备的最佳配置方案。仿真结果表明,通过合理地部署波长转换单元,可达到与全波转换相近的性能指标。

WDM光网络中一种改进的波长转换器配置算法

文章在一种已有的"子图+ADD(代数决策图)"的波长转换器配置算法的基础上,提出了用优先配置最大度节点的启发式思想对该算法进行改进,得到了新的"子图+BDF(大度节点优先分配)"算法。通过对两种算法进行计算机仿真,得到的模拟结果显示新算法在保持结果准确的同时,有效降低了运算的时间复杂度。

WDM网络中一种新型的波长转换器配置算法

在波分复用(WDM)光网络中,文章将经过各节点的最短路径的总长度作为权值对节点进行排序,利用优先配置最短路径总长度较长的节点的思想,对已有的"子图+代数决策图(ADD)"算法进行改进,得到了一种新的"子图+路径长度排序(PLS)"算法。对两种算法进行了计算机仿真,结果显示新算法在保证结果准确的同时,较有效地降低了运算的时间复杂度。

计算不交和的一个新算法

提出一个计算网络可靠度的有效算法。算法基于二分决策图,但采用新的法则选取shannon公式中的关键字母及因式分解技巧,与已有的某些算法相比,算例表明这个算法比较简单,产生比较少的不交和项及比较紧凑的公式。

基于加权约束求解技术的装配序列优化算法

针对符号约束求解技术无法解决装配序列择优的问题,提出一种装配序列优化算法。该算法通过筛选合适的装配评价指标构建装配评价函数,以装配联接图和带权移动向量函数为装配体模型,给出装配联接图和带权移动向量函数的ADD表示,并将装配序列规划问题描述为加权约束满足问题,利用深度优先分枝定界(DFBB)算法和符号ADD技术对加权约束满足问题求解。仿真实验表明,该装配序列优化算法能够求解最优装配序列,并增强了对装配序列的优化能力。

加权约束满足问题的符号ADD求解算法

加权约束满足问题(WCSP)是一类软约束满足问题.给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法.首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示.其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解.通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进.最后,对大量随机生成的测试用例进行实验分析.结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法.