...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability >Some disturbing facts about depth-first left-most variable ordering heuristics for binary decision diagrams
【24h】

Some disturbing facts about depth-first left-most variable ordering heuristics for binary decision diagrams

机译：关于二元决策图的深度优先的最左变量排序启发法的一些令人不安的事实

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

摘要

Binary decision diagrams (BDDs) have proven to be a very efficient tool to assess fault trees. However, the size of the BDD, and therefore the efficiency of the whole methodology, is highly dependent on the choice of variable ordering. The determination of the best variable ordering is intractable. Therefore, heuristics have been designed to select reasonably good variable orderings. The most popular of these heuristics consists in numbering variables by means of a depth-first left-most (DFLM) traversal of the formula, after possibly some rearrangements of the inputs of the gates. In this article, this heuristic is studied in a systematic way. It is shown to be very sensitive to the way the formula is written. A series of experiments shows also that the notion of locality of variables, which was believed to be a key issue in the determination of good orderings, must be handled with care. These facts are quite disturbing and raise questions about the design of good variable ordering heuristics.
机译：二进制决策图（BDD）已被证明是评估故障树的非常有效的工具。但是，BDD的大小以及整个方法的效率在很大程度上取决于变量排序的选择。最佳变量排序的确定是棘手的。因此，启发式设计用于选择合理的变量排序。这些启发式方法中最流行的方法是在可能对门的输入进行某些重新排列之后，通过对公式进行深度优先的最左端（DFLM）遍历，对变量进行编号。在本文中，对该启发式进行了系统的研究。它显示出对公式的编写方式非常敏感。一系列实验还表明，必须谨慎处理变量局部性的概念，该概念被认为是确定良好顺序的关键问题。这些事实非常令人不安，并提出了有关良好的变量顺序启发式方法设计的问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号