Exact and Heuristic Minimization of the Average Path Length in Decision Diagrams
Shinobu Nagayama, Alan Mischenko, Tsutomo Sasao and Jon T. Butler
In a decision diagram,the average path length (APL) is the average number of nodes on a path from the root node to a terminal node over all assignments of values to variables. Smaller APL values result in faster evaluation of the function represented by a decision diagram. For some functions, the APL depends strongly on the variable order. In this paper, we propose an exact and a heuristic algorithm to determine the variable order that minimizes the APL. Our exact algorithm uses branch-and-bound. Our heuristic algorithm uses dynamic reordering, where selected pairs of variables are swapped. This paper also proposes an exact and a heuristic algorithm to determine the pairs of binary variables that reduce the APL of multi-valued decision diagrams (MDDs) for a 4-valued input 2-valued output function. Experimental results show that the heuristic algorithm is much faster than the exact one but produces comparable APLs. Both algorithms yield an improvement over an existing algorithm in both APL and runtime. Experimental results for 2-valued cases and 4-valued cases are shown.