由上述我们可以知道,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)=high(v)
b 没有节点u拥有相同的后继,即low(u)¹higt(u)
如图3:
[img]C:\Documents and Settings\gyk\桌面\bdd-picture\111.bmp[/img]
R(O)BDD有些有趣的特性,它提供了一种紧凑,高效的布尔表示,对于所有函数
f: Bn à B总有一个R(O)BDD去表述,同时由于R(O)BDD总为真或假,对它的测试也是在有限时间范围内的(NP--完全),它的终端节点总是一个布尔值,非终端节点则是INF表达式,分别表示:
t0 = 0
t1 = 1
tu = var(u)à thigh(u) , tlow(u) ,u是节点变量
另外如果是有序的BDD,我们把与每个节点u有关的函数fu映射到(b1,b2…bn)ÎBn 满足 tu[b1/x1,b2/x2,……bn/xn].我们可以得到以下引理
引理1:对于任何函数 f: Bn à B总有一个ROBDD去表述,u是变量有序的x1<x2…<xn 且 fu = f(x1,x2…xn).
对于变量的有序选择对ROBDD的构建有重要的影响,如我们如果按x1<x2<y1<y2的序列构造(x1<=>y1) ∧(x2<=>y2),可得
[img]C:\Documents and Settings\gyk\桌面\bdd-picture\333.bmp[/img]
有了ROBDD的概念后,就可以使BDD的算法更容易被表述,例还是对(x1<=>y1) ∧(x2<=>y2 按照x1<y1< x2<y2的有序表述(图2),同时对节点u标号,我们可以得到如下表:
[img]C:\Documents and Settings\gyk\桌面\bdd-picture\1.jpg[/img]
由此,我们得到了一个更为简便的BDD表述.
分享到:
相关推荐
bdd 简介bdd-1 简介
项目简介: 在BDD驾驶项目中,我们将自我驾驶的任务制定为未来的自我运动预测。 为了完成这项任务,我们与合作伙伴收集了,提出了FCN + LSTM模型,并使用tensorflow实现了该模型。 伯克利DeepDrive视频数据集(BDD-...
这是二元决策图库的 Lua 实现,如 Henrik Reif Andersen 的“二元决策图简介”中所述。 有关使用示例,请查看测试套件(取决于 lunatest)。 编写代码是为了清晰而不是性能(尽管它确实在几秒钟内找到了 10-queens ...
简介cucumber是BDD(Behavior-driven development,行为驱动开发)的一个自动化测试的副产品,这是自己理解后写的DEMO,包含常用的写法解释、样例应该是全的。
内容简介: 1)方向:多目标跟踪(Multi-Object Tracking) 2)应用:视频任务 3)背景:现有的多目标跟踪方法大多只能在相邻帧之间明确利用目标特征,缺乏对长期时间信息的建模能力。 4)方法:本文提出了一种...
基于零抑制 BDD 的异步电路验证 基于零抑制 BDD 的异步电路验证 Koichi Masukura、Minoru Tomisaka 和 ...信息科学与工程研究生院,计算机科学系,东京工业大学,东京,152 ...由于异步电路不使用时钟并根据信号...简介异步电
使用Jasmine BDD进行JavaScript测试的简介 本演示文稿和代码旨在对的一些基本功能进行高层次的概述, 是Pivotal Labs的人员JavaScript BDD框架。 如果您有兴趣学习有关Jasmine的知识,建议您并在浏览幻灯片的同时...
VilniusPHP聚会社区聚会的演讲。维尔纽斯PHP 0x63(2021-02-04) PHP NerijusŽutautas中的SOLID原理() “机器人的故事:在构建自己的WMS时吸取的...Andrejs Abrickis Ciaran McNulty的“ BDD简介” “设置为代码”
1、简介 包是添加功能到 Laravel 的主要方式。包可以提供任何功能,小到处理日期如 Carbon,大到整个 BDD 测试框架如 Behat。 当然,有很多不同类型的包。有些包是独立的,意味着可以在任何框架中使用,而不仅是 ...
会话2] Node.js速成课程异步Js会话(回调,承诺,异步等待) JavaScript高阶函数和数组Express JS会话带有Node&Express的TypeScript设置Flexbox速成课程具有图像跨度CSS网格布局堆栈数据结构Express和MongoDB的Node...
③提供了BDD式的测试模式:可以使用Given-When-Then section来做BDD测试; ④只用一个核心的assertion宏来做比较。用标准的C++运算符来做比较,但是可以分解表达式,记录表达式等号左侧和右侧的值; ⑤可以用任何...
Cloud-Raider简介CloudRaider是一个新的测试框架,用于在AWS中执行“故障模式影响分析”(FMEA)测试。 Cloud Raider还通过Cucumber框架提供了行为驱动的测试方法。 Cloud Raider提供了一种编程方式来执行受控故障,...
有关更多示例,请查看每个子文件夹中的测试,以及espresso / tests / bdd / features文件夹中的BDD方案。 最后,请加入[slack](pylada.slack.com)。 如果需要访问,请向其中一位作者发送电子邮件。 安装 最简单...
ui/e2e 测试来构建有价值的软件并提高开发人员的准确性、速度、信心和平静度的指南。 对于 AngularJS 1.X 项目。 寻找 , , 或 ? 有关 UGAT 测试理念的高级语言不可知概述,请查看此 repo: 目录 ## 第 1 部分:UGAT ...
通过在您的jenkins构建上的BDD生活文档。 目录 1.简介 Cucumber生活文档插件基本上会在jenkins工作区中扫描Cucumber json输出文件,以便从中生成生活文档。 使用json格式化程序在Cucumber测试后生成Cucumber json...
BDD 创建HTML表单是主要步骤。 对于业务逻辑:使用构造函数存储输入数据。 使用innerHTML输出欢迎警报。 创建一个将个人消息发送到我的邮箱的功能。 作者: 联系信息: Email: dennis95peters@gmail.com Phone: ...
简介是建立一个响应式服装网站,具有购物车和优惠券折扣等功能。 运行$rackup。 测试$ bundle exec Cucumber使用的技术Ruby/辛纳特拉jQuery / Handlebars.js RSpec / 水豚 / Cucumber工作清单完整的响应式设计 [ ]...
任务的简介很简单,但是我借此机会对解决方案进行了过度设计,并将其用作React,Flux和ECMAScript 6的学习工具。简要显示客户账单使用任何语言,工具或框架从给定端点将账单作为JSON消费: ...
简介: 扬声器甲板: 概括 经验丰富的软件架构师/工程师,专注于可扩展和分布式软件设计/开发,倡导软件开发最佳实践,每天使用 TDD 和 BDD。 后端工程专家,具有 C/C++、Java、PHP、Python、JavaScript 和 Scala ...