二元决策图

数学学术语

二元决策图（binary decision diagram, BDD)是一种基于Shannon分解的有向无环图，最早由Sheldon B.Akers于1978年提出的，它实质上是简化布尔函数的Shannon分结束得到的。BDD是被用来表达一个布尔函数的一种数据结构。

基本概念

二元决策图的描述

BDD是一种基于Shannon分解的有向无环图，最早由Sheldon B.Akers于1978年提出。设f是一组布尔变量集合X的布尔函数，且x为集合X中的变量，则Shannon分解及其if-then-else(ite)形式为：

式中x和分别代表，事件发生和不发生；（即F1）和（即F2）分别表示x发生和不发生的布尔函数。

BDD用二叉树形式表示布尔逻辑函数：

BDD是个有向无环图，包含终节点和非终节点，节点之间靠1或0分支连接。终节点分两种状态，1和0分别表示两种不交的逻辑状态即系统或部件的失效状态和正常状态。非终节点对应故障树的基本事件，每个非终节点的1分支代表基本事件失效，0分支代表基本事件正常。自BDD的根节点向下遍历直到到达一个终节点，整条路径构成一条BDD的通路，必然结束在0或1状态之一，分别表示顶事件不发生和发生，而终节点为1的路径中的节点构成系统的割集。图１中BDD示例所表示的顶事件发生的最小割集为到达终节点1的所有路径，即，。

决策树与二叉树

决策树

决策树（又称树分类器或分类树）是模式识别中进行分类的一种有效方法。利用树分类器可以把一个复杂的多类别分类问题转化为若干个简单的分类问题来解决。它不是企图用一个决策规则把多个类别的样本一次分开，而是采用分级的方法，使分类问题逐步得到解决。总结起来，决策树就是一个将输入空间逐步分割的过程，它把输入空间分为一组互不相交的子区域，其中某个类别的样本占有优势的区域标记为该样本的类别。

决策树示意图如下：

一般地，一个决策树由一个根节点，一组非终止节点和一些终止节点（也称叶节点、叶子）构成，每个叶节点标以相应的样本类别标签，不同的叶节点可以有相同的类别标签。

二叉树

决策树的一种简单形式是二叉树，二叉树结构的分类器可以把一个复杂的多类别分类问题化为多级、多个两类问题来解决，在每个节点都把样本集分为左右两个子集。分出的每个部分任然可能包含多个类别的样本，在下一级的节点，把每个部分再分为两个子集，依此进行，直到最后分出的每个部分只包含同一类别的样本，或某一类别样本占优势为止。

优点：概念简单、直观，便于解释。在各个节点上可以选择不同的特征和采用不同的决策规则。

二叉树示意图如下：

二元决策图分析故障树

采用BDD方法分析故障树，不需求解最小割集就可以得出顶事件发生概率，能够简化故障树定性和定量分析过程。

故障树向BDD转化

一个普遍的采用的构建BDD的方法是对故障树中每个门结构应用if-then-else(ite)规则。转化的递归算法思路是：从故障树最底层基本事件开始，用ite结构进行转化，用基本事件替换逻辑门，形成新的ite结构，然后继续向上一层进行ite结构转化，使得新的逻辑门都被基本事件替换，如此逐步向上，直到所有的逻辑门都被基本事件替换，则顶事件的BDD形成。

构建BDD过程中，先对故障树基本事件排序，然后对故障树中每个门结构进行BDD转化。令F和G分别表示BDD中的2个节点，其中，，转化规则如下：

如果在故障树基本事件排序中，X位于Y的前面，即X

如果X=Y，则：

式中，是故障树中逻辑门（AND或OR）的布尔算子。

基本步骤

典型的FT分析BDD方法的流程如下：

（1）FT结构预处理，结构简化，并进行模块化；

（2）将独立模块转化成相应的BDD结构，求解最小割集，进行定量分析；

（3）将各个独立模块看作初始故障树的底事件，求解最小割集；

（4）进行迭代，得到最终的最小割集，作定量分析。

全国各地天气预报查询

上海市