Diagrama de decisión binario

En ciencias de la computación, un diagrama de decisión binario (DDB), tal como una forma normal de negación (FNN) o un grafo acíclico dirigido proposicional (GADP), es una estructura de datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en los DDB, sin necesidad de descomprimirlos.

Definición

Una función booleana puede representarse como un grafo acíclico dirigido con raíz, el cual posee nodos de decisión y dos nodos terminales llamados terminal-0 y terminal-1. Cada nodo de decisión está etiquetado por una variable booleana (0 o 1) y tiene dos nodos hijos, llamados hijo menor e hijo mayor. La arista que une un nodo con un hijo menor (mayor) representa una asignación de la variable con el valor 0 (1).

Un DDB está ordenado si las distintas variables aparecen en el mismo orden para todos los caminos desde la raíz. Un DDB es reducido si se han aplicado las siguientes dos reglas a su grafo:

• Unir los isomorfismos de subgrafos.
• Eliminar los nodos cuyos dos hijos sean isomorfos.

En el uso popular, el término DDB también se refiere a Diagrama de decisión binario reducido ordenado (DDBRO, mejor conocido en la literatura en inglés como ROBDD: Reduced Ordered Binary Decision Diagram).^[1]​ Una ventaja de un DDBRO es que es canónico (único) para una función particular y un orden de variables.^[2]​ Esta propiedad es útil por ejemplo en la verificación de funciones de equivalencia.

Un camino desde el nodo raíz al terminal-1 representa una asignación de variables (posiblemente parcial) para la cual la función booleana es verdadera. Si el camino desciende desde un nodo hasta un hijo menor (mayor), la variable del nodo adquiere el valor 0 (1).

Historia

La idea básica de donde proviene esta estructura de datos es la expansión de Shannon. Una función booleana se divide en dos sub-funciones (cofactores) mediante la incorporación de una variable (cf. forma normal if-then-else). Si tal sub-función se considera como un sub-árbol, entonces se puede representar por un árbol de decisión binario. Los diagramas de decisión binarios fueron introducidos por Lee,^[3]​ y más adelante estudiados y dados a conocer mejor por Akers^[4]​ y Boute.^[5]​

El máximo potencial de esta estructura de datos para ser utilizada en la implementación de algoritmos eficientes fue investigada por Randal Bryant en la Universidad Carnegie Mellon: su aporte clave fue el utilizar una ordenación fija de variables (para lograr una representación canónica) y sub-grafos compartidos (para mayor compresión). Aplicando ambos conceptos logró una estructura de datos y algoritmos eficientes para la representación de conjuntos y relaciones.^[6]​^[7]​ Así se definió la estructura de datos Diagrama de decisión binario reducido ordenado y compartido (en inglés «Shared Reduced Ordered Binary Decision Diagram»), que permite que un sub-grafo sea utilizado por varios DDBs.^[8]​ Actualmente, la noción de DDB se utiliza generalmente para referirse a esta estructura de datos particular.

En su ponencia en vídeo Fun With Binary Decision Diagrams (BDDs) («Diversión con los diagramas de decisión binarios (DDBs)»), Donald Knuth se refiere a los DDBs como «una de las únicas estructuras de datos realmente fundamentales que han aparecido en los últimos 25 años», y destaca el hecho de que artículo de Bryant de 1986 fuese durante un tiempo uno de los artículos más citados en ciencias de la computación.

Véase también

• Aprendizaje basado en árboles de decisión
• Problema de satisfacibilidad booleana
• Estructura de datos
• Model checking
• Forma normal negativa (FNN)
• Grafo acíclico dirigido proposicional (GADP)

Referencias

1. The Art of Computer Programming, vol 4A, Donald E. Knuth
2. Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986
3. C. Y. Lee. "Representation of Switching Circuits by Binary-Decision Programs". Bell Systems Technical Journal, 38:985–999, 1959.
4. Sheldon B. Akers. Binary Decision Diagrams (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)., IEEE Transactions on Computers, C-27(6):509–516, June 1978.
5. Raymond T. Boute, "The Binary Decision Machine as a programmable controller". EUROMICRO Newsletter, Vol. 1(2):16–22, January 1976.
6. Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation Archivado el 23 de septiembre de 2015 en Wayback Machine.". IEEE Transactions on Computers, C-35(8):677–691, 1986.
7. R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293–318.
8. Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "Efficient Implementation of a BDD Package". In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), pages 40–45. IEEE Computer Society Press, 1990.

Bibliografía

• H. R. Andersen "An Introduction to Binary Decision Diagrams," Lecture Notes, 1999, IT University of Copenhagen.
• D. E. Knuth, "The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison-Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8. Draft of Fascicle 1b Archivado el 12 de marzo de 2016 en Wayback Machine. available for download.
• Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
• R. Ubar, "Test Generation for Digital Circuits Using Alternative Graphs (in Russian)", in Proc. Tallinn Technical University, 1976, No.409, Tallinn Technical University, Tallinn, Estonia, pp. 75–81.

Enlaces externos

• Wikimedia Commons alberga una categoría multimedia sobre Diagrama de decisión binario.