二叉判定图理论研究及其应用

论文摘要

二叉判定图这种数据结构主要用来表示逻辑表达式,而现在人们已经研制了一些表示方法:比如二叉判定树、真值表、卡诺图等等,但是对于这些表达方式而言,存储空间的需要比较大,还存在着大量的冗余数据。二叉判定图则是在二叉判定树的基础上,消除了其中的冗余结点,减少了对存储空间的需求,从而提高了求解问题的速度。文中比较全面地介绍了二叉判定图的基本理论。首先由二叉判定树表示的布尔函数,引出了布尔函数的二叉判定图表示方法。之后详细的介绍了二叉判定图的构造算法。通过对二叉判定图理论的学习和研究,我提出了利用二叉判定图对极小碰集和约束满足问题求解的算法。极小碰集问题是在基于模型的诊断中遇到的问题。这种方法不会因剪枝而丢失解;而且不用求出全部的碰集,但是所求得的解却包含全部的极小碰集。约束满足问题作为人工智能领域的研究方向,在经过几十年的研究后,目前已经拥有了数量丰富的各种求解算法。本文给出了利用二叉判定图求约束满足问题的算法,并编程实现了对N皇后问题的求解。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 二叉判定图理论的国内外现状
• 1.2 二叉判定图理论研究的目的和意义
• 1.3 本文主要的研究内容
• 第二章 二叉判定图的基础知识
• 2.1 布尔函数和二叉判定图
• 2.1.1 相关概念和定理
• 2.1.2 变量顺序对二叉判定图大小的影响
• 2.2 BDD 的基本算法
• 2.2.1 一般的构造算法
• 2.2.2 深度优先BDD 构造算法
• 2.3 其它算法
• 2.4 小结
• 第三章 用ROBDD 计算极小碰集
• 3.1 模型诊断的相关概念
• 3.2 BDD 计算极小碰集的算法设计
• 3.2.1 析取式方程组的相关概念和性质
• 3.2.2 调用APPLY 算法和MK 算法
• 3.2.3 极小碰集的算法和应用
• 3.3 实验
• 第四章 用ROBDD 求解约束满足问题
• 4.1 约束满足问题
• 4.1.1 约束满足问题概念
• 4.1.2 约束满足问题的解法
• 4.2 BDD 计算约束满足问题的算法设计
• 4.3 实验
• 4.4 小结
• 第五章 结论与展望
• 5.1 结论
• 5.2 工作展望
• 致谢
• 参考文献