• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Design and implementation of multiple-valued decision diagrams based on a binary decision diagram package.
【24h】

Design and implementation of multiple-valued decision diagrams based on a binary decision diagram package.

机译：基于二进制决策图包的多值决策图的设计和实现。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Many problems can be stated naturally using variables that have multiple values. Functions defined on these variables can also take on values from a discrete set. Compact representation and efficient manipulation of such multi-valued functions are key to the design of efficient algorithms that advance the frontier of the problems that can be solved exactly. Binary decision diagrams are such a compact representation for problems involving binary variables. It has long been supposed that since multi-valued functions can be represented as a binary input binary multi-output function, a simple relation exists between the two to map the number of nodes from a binary diagram into its resulting multi-valued diagram.;Working with this premise we will show why there is no simple relationship between the two for all general functions. The actual algorithm for the binary output sub-cases will then be demonstrated and formally defined. This algorithm will then be used to give an upper limit on the number of nodes that can be generated in the binary case from the simplest of the multi-valued diagrams. Furthermore we will show its impact on some benchmark functions.;This paper will explore just that phenomenon and formally define an algorithm that returns the number of nodes in the multi-valued diagram. This algorithm, it turns out, is only valid for multi-valued functions that have a binary output. Although this property has been observed and documented before, it has been assumed that the design can easily be extended to more general multi-valued functions. That is not the case, since the method by which subgraph merging operates differs between the binary and multi-valued cases. This causes a breakdown of the direct mapping property that has been observed and documented in the binary output case.
机译：使用具有多个值的变量可以自然地陈述许多问题。在这些变量上定义的函数也可以采用离散集中的值。此类多值函数的紧凑表示和有效操作是设计有效算法的关键，该算法将可以精确解决的问题推向前沿。二进制决策图是涉及二进制变量的问题的紧凑表示。长期以来人们一直认为，由于可以将多值函数表示为二进制输入二进制多输出函数，因此在两者之间存在一种简单的关系，可以将二进制图中的节点数映射到其最终的多值图中。在此前提下，我们将说明为什么对于所有常规功能而言，两者之间没有简单的关系。然后将演示并正式定义二进制输出子情况的实际算法。然后，该算法将用于根据最简单的多值图在二进制情况下可以生成的节点数给出上限。此外，我们还将展示其对某些基准函数的影响。；本文将仅探讨该现象，并正式定义一种算法，该算法返回多值图中的节点数。事实证明，该算法仅对具有二进制输出的多值函数有效。尽管以前已经观察到并记录了此属性，但已假定可以轻松地将设计扩展到更通用的多值函数。情况并非如此，因为在二值和多值情况下，子图合并操作的方法不同。这会导致直接映射属性的故障，在二进制输出情况下已经观察到并记录了该属性。

著录项

  • 作者

    Viswanathan, Kanish.;

  • 作者单位

    University of New Brunswick (Canada).;

  • 授予单位 University of New Brunswick (Canada).;
  • 学科 Computer Science.
  • 学位 M.C.S.
  • 年度 2005
  • 页码 81 p.
  • 总页数 81
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号