Diagrama de decisión binario
# 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). Una ventaja de un DDBRO es que es canónico (único) para una función particular y un orden de variables. 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, y más adelante estudiados y dados a conocer mejor por Akers y Boute.

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. 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. 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.

