2008-06-02
全文显示

BDD简介---2

由上述我们可以知道，BDD是由1个或2个终端节点（0或1）出度为2（low(u)和high(u)）图所组成的，它把BDT从2n 个节点进行裁减，从而减少空间复杂度，然而却增加了时间复杂度，为使其了更有效，我们引入OBDD和R（O）BDD的概念。 OBDD（Ordered Binary Decision Digram）是所有BDD路径都是基于给定线性序列的BDD。如图2 就是 遵循x1<y1<x2<y2的线性序列。 R（O）BDD则满足：a 没有2个不同得节点u,v使之满足 var(u)=var(v),low(u)=low(v),high(u)=hig ...
2008-05-28
全文显示

BDD简介 ---1

BDD(Binary Decision Digrams)是最新流行于人工智能模型诊断方面的一种求解算法,主要用于诊断求解,配置和约束满足等方面,下面我将对BDD做一下简单的介绍. 在学习BDD之前首先要有一点离散数学的基本概念,知道∧,∨,﹁,=>,<=>等基本符号的意义和各范式的表达,定义if-then-else 操作为: x=>y0,y1 = (x∧y0) ∨(x∧y1) 所以x=>y0,y1 为真时当且仅当x ,y0同为真或x为假,y1为真.从这种if-then-else 操作演化来的形式被称作if-then-else Normal Form(INF).我们指定布尔表达式 ...
guyikun
搜索本博客
最近加入圈子
最新评论