A Comparison of Free BDDs and Transformed BDDs

Ordered binary decision diagrams (OBDDs) introduced by Bryant (IEEE Trans. on Computers, Vol. 35, pp. 677–691, 1986) have found a lot of applications in verification and CAD. Their use is limited if the OBDD size of the considered functions is too large. Therefore, a variety of generalized BDD models has been presented, among them FBDDs (free BDDs) and TBDDs (transformed BDDs). Here the quite tight relations between these models are revealed and their advantages and disadvantages are discussed.     

基于ROBDD的布尔函数同构判定算法研究

布尔函数是密码体制设计与分析中一个不可缺少的工具,在布尔函数的应用中,判定两个布尔函数的同构问题具有广泛的需求,但是,判定布尔函数同构是NP-难问题,并且采取穷举法也将随着变量的增多,因极高的时间复杂度而使其难以实现.该文基于图的思想,提出了一种基于ROBDD(简化有序二元决策图)的布尔函数同构判定算法,其算法的复杂度...     

装配序列规划问题的CSP模型及其符号OBDD求解技术

完全、正确的可行装配序列的表示和生成是装配序列评价、优化和选择的前提,为此建立了单调非线性装配意义下的可行装配序列规划问题的约束满足问题(CSP)模型,并给出了基于有序二叉决策图(OBDD)的符号求解算法.首先以装配联接图和移动向量函数为装配体模型,给出了装配联接图模型的共享二叉决策图(SBDD)表示、移动向量函数的OBDD表示,以及装配序列规划问题的CSP描述;然后将生成所有可行装配序列的问题转化为对CSP求解所有可能解的问题,利用回溯算法对CSP问题进行符号OBDD求解,得到了满足几何可行性约束的所有可行装配序列.最后通过装配体实验验证了基于CSP模型和OBDD推理的装配序列生成技术的正确性和可行性.     

基于有序二叉决策图的路径规划可行性研究

对全局环境未知且存在障碍物情况下的移动机器人路径规划问题进行了研究.借助有序二又决策图的原理,首次采用有序二叉决策图数据结构来表示机器人工作空间中的信息环境模型,并对它们进行了二进制编码,建立一个有效紧凑的OBDD环境模型.利用该OBDD模型能自动规划了免碰撞路径,获取一条从起始状态(包括位置及姿态)到达目标状态的安全、高效的无碰路径.实验仿真结果表明,所提出的方法是正确和有效的.     

Limits of Using Signatures for Permutation Independent Boolean Comparison

This paper addresses problems that arise while checking the equivalence of two Boolean functions under arbitrary input permutations. The permutation problem has several applications in the synthesis and verification of combinational logic: it arises in the technology mapping stage of logic synthesis and in logic verification. A popular method to solve it is to compute a signature for each variable that helps to establish a correspondence between the variables. Several researchers have suggested a wide range of signatures that have been used for this purpose. However, for each choice of signature, there remain variables that cannot be uniquely identified. Our research has shown that, for a given example, this set of problematic variables tends to be the same–regardless of the choice of signatures. The paper investigates this problem.     

用改进的OBDD方法计算通信网可靠度*

提出一种改进的OBDD（ordered binary decision diagram）方法来计算通信网可靠度。该方法考虑了网络共因失效带来的部件故障,使得计算更加准确。在创建原始网络的OBDD结构后,根据共因变量集来计算网络可靠度。由于只创建并保存一个OBDD结构,可节省大量的计算时间和存储空间。实验证明,该方法能有效计算网络可靠度,其计算时间和存储空间要低于一般的OBDD方法。     

可追踪且可撤销的基于OBDD访问结构的CP-ABE方案

针对现有属性撤销方案中存在对恶意用户的不可追踪性、用户属性不能即时撤销的问题,提出了一种可追踪且可撤销的,基于有序二叉决策图(OBDD)访问结构的,高效、有表达力、可撤销的密文策略属性基加密(CP-ABE)方案。该方案实现了用户属性的即时撤销,也能对恶意用户进行追踪。同时,所提方案采用基于OBDD的访问结构,该类型的访问结构不仅能表示任何关于属性的布尔表达式,还能同时支持访问策略中属性的正负值。该方案将部分加/解密运算外包给代理服务器,从而降低用户的加/解密计算量。该方案基于DBDH假设,在标准模型下被证明是安全的。     

约束满足问题求解的符号OBDD桶消元算法

桶消元算法是求解约束满足问题的一种典型推理方法.针对桶消元算法面临的状态空间爆炸问题,将有序二叉决策图( OBDD)技术与该算法结合起来,给出了约束满足问题的一种求解算法.通过对约束满足问题中变量和域值的编码,将CSP问题转化为命题可满足性问题,给出了约束满足问题的OBDD表示方法;基于桶消元的算法思想,在约束满足问题...     

熵在决策树构建中的应用

决策树是对未知数据进行分类预测的一种方法。本文阐述熵理论和典型的ID3算法，并举例构建决策树。讨论选择具有最高信息增益的属性构建决策树，即选定具有最高区分度的属性作为当前节点。利用熵理论构建决策树,方法简单，结构清晰，容易转换成分类规则，并且不需要先验领域知识。     

熵在决策树构建中的应用

决策树是对未知数据进行分类预测的一种方法。本文阐述熵理论和典型的ID3算法,并举例构建决策树。讨论选择具有最高信息增益的属性构建决策树,即选定具有最高区分度的属性作为当前节点。利用熵理论构建决策树,方法简单,结构清晰,容易转换成分类规则,并且不需要先验领域知识。     

基于HGA算法的Rough集理论在故障诊断中的应用

知识约简问题是粗集理论的一个核心问题,文章提出了一种基于混合遗传算法的相对约简算法,把模拟退火融入到遗传算法中形成混合遗传算法,提高了遗传算法的优化效率,并在此基础上寻求最小条件属性集及最小属性值约简,论文最后以某导弹测控系统配电分系统故障诊断为例,证明该算法是一种行之有效的约简算法,从而为导弹系统的故障诊断提供了一条新思路.     

智能决策支持系统中的知识表示及基于粗集的推理

探讨了在智能决策支持系统中的知识表达系统以及数据粗集理论分析处理海量信息中信息的有用特征,通过分析、推理产生最小决策规则。最后以EDUDSS中农村小学布局决策为例作实例分析。     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

边排序质量影响因素研究

网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量。因此,边排序问题是网络可靠度BDD分析方法的重要问题。由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS和DFS,它们适用不同类型的网络。然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据。利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和BDD尺度(节点数目)之间的关系。实验结果表明,边界长度BSL与BDD尺度具有正相关性,即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值。这为特定网络选择(或设计)高性能边排序提供了重要的参考依据。     

融合语义网的故障检索系统设计与构建

针对雷达故障数据和经验性技术支持文档的信息提取,提出了一种融合语义网技术的故障检索系统的设计与实现方法;该系统采用故障树组织结构化的历史故障数据,将故障树转化为二元决策图从而获取顶层故障事件的最小割集,而后通过语义匹配获取精确的故障原因信息;同时,借助开源搜索引擎Lucene检索技术文档库,获得与用户检索条目相关的支持文档;其中,为了提升中文分词和文本匹配的精确性,该系统还利用本体语言构建了专业词汇语义网,考量了词语之间的语义相关度;该系统已应用于某型机载有源相控阵雷达电源单元的故障检索,取得了很好的技术辅助效果。     

高层次综合的实有化逻辑图自动生成关键技术的研究

研究的逻辑图自动生成系统是“九五”微电子重点科技预研项目的成果“实用化专用集成电路高层次自动化设计系统－Talent系统”的子系统,该系统通过对电路网表有效的识别与划分、逻辑单元的布局及互连信号线的布线等,自动生态具有一定逻辑功能且布局美观规范的逻辑原理图。该文重点研究逻辑图自动生成实用化过程中的关键技术,将人工智能基于规则的知识表示与形式化算法相结合,提出有效的自动布局方法;应用模式识别理论和方法解决逻辑图的自动布线问题,提出基于决策树的通道分配方法,并设计一套完整的规则体系;进而,文中给出详细的划分模型,并在此基础上,结合逻辑原理图的特点实现了两种有效的划分算法：（1）种子生成的构造式划分算法;（2）迭代改进划分算法。其中算法（1）的设计思想主要源于贪婪构造,而算法（2）则对经典的最小分割划分算法Kernigham－Lin算法进行改进。基于上述研究实现的逻辑图自动生成系统,能够在很短的时间内生成美观规范、可读性好的逻辑图,为整个系统实用化做出了贡献。     

一种二值图象欧拉数的并行快速算法

本文给出了一个求方格(square grid)上二值化图象欧拉数的并行快速算法,并通过将方格上的二值图象转化成数字图来引用图论方法对该算法进行了证明,且给出了若干实例以说明算法的有效性.     

基于二分决策图的特征模型验证方法

特征模型是领域分析活动产生的具有复用价值的软件需求模型.对特征模型的复用通常采用定制的方式.特征模型定制中的一个重要问题是验证问题.该问题的存在是因为特征之间往往具有一定的约束关系,而一个合法的定制结果必须保证特征之间所有约束关系的被满足性.由于特征模型验证问题NP-hard所具有的性质,如何高效地进行特征模型的验证就成为一件相对困难的事情.在深入挖掘特征模型验证问题特殊性的基础上,将这种特殊性和二分决策图的结构特点进行了有效的结合,提出了一种通过对二分决策图的一次遍历即能实现特征模型验证的方法.需要指出的是,该方法并非试图在一般意义上解决特征模型验证问题中NP-hard的困难性,而是尽可能地利用该问题的特殊性,以提高处理特征模型定制问题的规模和效率.实验数据表明,相比较以前采用的验证方法,基于BDD(binary decision diagram)的方法在处理特征模型验证问题的规模和效率上都具有显著的提高.     

二叉判定图最优化算法研究综述

对近年来二叉判定图(BDD)最优化算法的成果和发展趋势进行了综述和讨论，重点介绍精确排序算法和动态启发式排序算法．给出了BDD优化算法的改进建议：用不完全枚举法的优势和随机过程动态规划策略改进BDD优化算法．     

数据挖掘技术及算法综述

数据挖掘是目前非常热门的一门交叉学科，涉及到很多学科的研究领域。文中对数据挖掘的概念、实施步骤及各种算法进行了比较详细的归纳．并且对数据挖掘技术将来的研究方向也进行了预测。