Heuristics to Minimize Multiple-Valued Decision Diagrams
Heuristics to Minimize Multiple-Valued Decision Diagrams
复制标题
最小化多值决策图的启发式方法
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Tsutomu Sasao
中科院分区：
文献类型：
--
作者：
H. M. H. Babu;Tsutomu Sasao
本文提出了一种多输出函数的多值决策图最小化方法。我们认为：（1）用于编码2值输入的试探法;以及（2）用于基于采样对多值输入变量进行排序的试探法，其中每个样本是一组输出。我们首先从给定的2值输入2值函数生成一个4值输入2值多输出函数。然后，我们为每个样本构造MDD，并找到一个好的变量排序。最后，我们从代表样本的MDDs的排序中生成一个变量排序，并最小化整个MDDs。实验结果表明，该方法是快速得多，并为许多基准函数，它产生的MDD的节点比筛选少。特别是，所提出的方法产生更小的MDD在很短的时间内为基准函数时，几个2值的输入变量被分组，形成多值变量。关键词：二元决策图，多值决策图，多输出函数，多值决策图
In this paper, we propose a method to minimize multiple-valued decision diagrams (MDDs) for multipleoutput functions. We consider the following: (1) a heuristic for encoding the 2-valued inputs; and (2) a heuristic for ordering the multiple-valued input variables based on sampling, where each sample is a group of outputs. We first generate a 4-valued input 2-valued multiple-output function from the given 2-valued input 2-valued functions. Then, we construct an MDD for each sample and find a good variable ordering. Finally, we generate a variable ordering from the orderings of MDDs representing the samples, and minimize the entire MDDs. Experimental results show that the proposed method is much faster, and for many benchmark functions, it produces MDDs with fewer nodes than sifting. Especially, the proposed method generates much smaller MDDs in a short time for benchmark functions when several 2-valued input variables are grouped to form multiple-valued variables. key words: binary decision diagram (BDD), multiple-valued decision diagram (MDD), multiple-output function, multiple-