The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours
The Theory of Zero-Suppressed BDDs and the Number of Knight's Tours
复制标题
零抑制 BDD 理论和骑士巡演次数
DOI：
10.1023/a:1008681625346
复制
发表时间：
1998
影响因子：
0.8
通讯作者：
I. Wegener
中科院分区：
文献类型：
--
作者：
Olaf Schröer;I. Wegener
Minato[14-17]引入了零抑制二进制决策图（zbdd），提出了在立方体集表示、故障仿真、时序分析和n皇后问题上的应用。研究了zbdd的结构特性，提出了一种通用的合成算法，并进行了分析。证明了对于同一函数，在n个变量上，zbdd最多可以比有序bdd （obdd）小或大n + 1倍。使用zbdd，骑士在8 × 8棋盘上的游数上限得到了显著改善。
Zero-suppressed binary decision diagrams (ZBDDs) have been introduced by Minato [14–17] who presents applications for cube set representations, fault simulation, timing analysis and the n-queens problem. Here the structural properties of ZBDDs are worked out and a generic synthesis algorithm is presented and analyzed. It is proved that ZBDDs can be at most by a factor n + 1 smaller or larger than ordered BDDs (OBDDs) for the same function on n variables. Using ZBDDs the best known upper bound on the number of knight's tours on an 8 × 8 chessboard is improved significantly.