Diagrama de decisión binaria

En informática , un diagrama de decisión binaria ( DDB ) o programa de ramificación es una estructura de datos que se utiliza para representar una función booleana . En un nivel más abstracto, los DDB pueden considerarse como una representación comprimida de conjuntos o relaciones . A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente sobre la representación comprimida, es decir, sin descompresión.

Entre las estructuras de datos similares se incluyen la forma normal de negación (NNF), los polinomios de Zhegalkin y los grafos acíclicos dirigidos proposicionales (PDAG).

Una función booleana se puede representar como un grafo acíclico, dirigido y con raíz , que consta de varios nodos (de decisión) y dos nodos terminales. Los dos nodos terminales están etiquetados como 0 (FALSO) y 1 (VERDADERO). Cada nodo (de decisión)${\displaystyle u}$está etiquetado por una variable booleana${\displaystyle x_{i}}$y tiene dos nodos hijos llamados hijo bajo e hijo alto. La arista desde el nodo${\displaystyle u}$A un niño de bajo (o alto) nivel se le asigna el valor FALSO (o VERDADERO, respectivamente) a la variable.${\displaystyle x_{i}}$Un BDD se denomina "ordenado" si las diferentes variables aparecen en el mismo orden en todos los caminos desde la raíz. Un BDD se considera "reducido" si se han aplicado las dos reglas siguientes a su grafo:

• Fusiona cualquier subgrafo isomorfo .
• Elimine cualquier nodo cuyos dos hijos sean isomorfos.

En el uso común, el término BDD casi siempre se refiere al Diagrama de Decisión Binaria Ordenada Reducida ( ROBDD en la literatura, utilizado cuando es necesario enfatizar los aspectos de ordenación y reducción). La ventaja de un ROBDD es que es canónico (único salvo isomorfismo) para un orden de función y variable particular. ^{[ 1 ]} Esta propiedad lo hace útil en la verificación de equivalencia funcional y otras operaciones como el mapeo de tecnología funcional.

Una ruta desde el nodo raíz hasta el terminal 1 representa una asignación de variable (posiblemente parcial) para la cual la función booleana representada es verdadera. A medida que la ruta desciende a un hijo de menor (o mayor) nivel desde un nodo, la variable de ese nodo se asigna a 0 (o 1, respectivamente).

Bordes complementados

Un ROBDD puede representarse aún más compactamente, utilizando aristas complementadas, también conocidas como enlaces de complemento . ^{[ 2 ] [ 3 ]} El BDD resultante a veces se conoce como un BDD tipado ^{[ 4 ]} o BDD con signo . Las aristas complementadas se forman anotando las aristas bajas como complementadas o no. Si una arista está complementada, entonces se refiere a la negación de la función booleana que corresponde al nodo al que apunta la arista (la función booleana representada por el BDD con raíz en ese nodo). Las aristas altas no están complementadas, para asegurar que la representación BDD resultante sea una forma canónica. En esta representación, los BDD tienen un único nodo hoja, por razones que se explican más adelante.

Dos ventajas de utilizar aristas complementadas al representar BDD son:

• Calcular la negación de un BDD lleva tiempo constante
• El uso de espacio (es decir, la memoria requerida) se reduce (en un factor máximo de 2).

Sin embargo, Knuth ^{[ 5 ]} argumenta lo contrario:

Si bien este tipo de enlaces son utilizados por todos los paquetes BDD principales, resulta difícil recomendarlos, ya que los programas informáticos se vuelven mucho más complejos. El ahorro de memoria suele ser insignificante, y nunca supera el doble; además, los experimentos del autor muestran una escasa mejora en el tiempo de ejecución.

En esta representación, una referencia a un BDD es una arista (posiblemente complementada) que apunta a la raíz del BDD. Esto contrasta con una referencia a un BDD en la representación sin el uso de aristas complementadas, que es el nodo raíz del BDD. La razón por la que una referencia en esta representación debe ser una arista es que, para cada función booleana, la función y su negación se representan mediante una arista a la raíz de un BDD y una arista complementada a la raíz del mismo BDD. Por eso la negación requiere un tiempo constante. También explica por qué basta con un solo nodo hoja: FALSO se representa mediante una arista complementada que apunta al nodo hoja, y VERDADERO se representa mediante una arista ordinaria (es decir, no complementada) que apunta al nodo hoja.

Por ejemplo, supongamos que una función booleana se representa mediante un BDD utilizando aristas complementadas. Para hallar el valor de la función booleana para una asignación dada de valores (booleanos) a las variables, comenzamos en la arista de referencia, que apunta a la raíz del BDD, y seguimos la ruta definida por los valores de las variables (siguiendo una arista baja si la variable que etiqueta un nodo es FALSE, y siguiendo la arista alta si la variable que etiqueta un nodo es TRUE), hasta llegar al nodo hoja. Mientras seguimos esta ruta, contamos cuántas aristas complementadas hemos recorrido. Si al llegar al nodo hoja hemos cruzado un número impar de aristas complementadas, entonces el valor de la función booleana para la asignación de variables dada es FALSE; de lo contrario (si hemos cruzado un número par de aristas complementadas), entonces el valor de la función booleana para la asignación de variables dada es TRUE.

A la derecha se muestra un diagrama de ejemplo de un BDD en esta representación, que representa la misma expresión booleana que se muestra en los diagramas anteriores, es decir,${\displaystyle (\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})}$Las aristas bajas se representan con líneas discontinuas, las altas con líneas continuas y las aristas complementadas con un círculo en su origen. El nodo con el símbolo @ representa la referencia al BDD; es decir, la arista de referencia es la que parte de este nodo.

La idea básica a partir de la cual se creó la estructura de datos es la expansión de Shannon . Una función de conmutación se divide en dos subfunciones (cofactores) al asignar una variable (cf. forma normal if-then-else ). Si dicha subfunción se considera como un subárbol, puede representarse mediante un árbol de decisión binario . Los diagramas de decisión binarios (BDD) fueron introducidos por CY Lee, ^{[ 6 ]} y posteriormente estudiados y divulgados por Sheldon B. Akers ^{[ 7 ]} y Raymond T. Boute. ^{[ 8 ]} Independientemente de estos autores, Yu. V. Mamrukov implementó un BDD bajo el nombre de "forma de corchete canónico" en un CAD para el análisis de circuitos independientes de la velocidad. ^{[ 9 ]} Randal Bryant , de la Universidad Carnegie Mellon , investigó todo el potencial de los algoritmos eficientes basados ​​en la estructura de datos : sus extensiones clave fueron el uso de un orden fijo de variables (para la representación canónica) y subgrafos compartidos (para la compresión). La aplicación de estos dos conceptos da como resultado una estructura de datos eficiente y algoritmos para la representación de conjuntos y relaciones. ^{[ 10 ] [ 11 ]} Al extender el uso compartido a varios BDD, es decir, un subgrafo es utilizado por varios BDD, se define la estructura de datos Diagrama de Decisión Binaria Ordenada Reducida Compartida . ^{[ 2 ]} La noción de BDD se utiliza ahora generalmente para referirse a esa estructura de datos en particular.

En su videoconferencia " Diversión con diagramas de decisión binarios (BDD)" , Donald Knuth afirma que los BDD son "una de las pocas estructuras de datos realmente fundamentales que surgieron en los últimos veinticinco años" y menciona que el artículo de Bryant de 1986 fue durante un tiempo uno de los artículos más citados en ciencias de la computación. ^{[ 12 ]}

Adnan Darwiche y sus colaboradores han demostrado que los BDD son una de las diversas formas normales para funciones booleanas, cada una inducida por una combinación diferente de requisitos. Otra forma normal importante identificada por Darwiche es la forma normal de negación descomponible o DNNF.

Los BDD se utilizan ampliamente en software CAD para sintetizar circuitos ( síntesis lógica ) y en verificación formal y verificación de redes . Existen varias aplicaciones menos conocidas de BDD, como el análisis de árboles de fallos , el razonamiento bayesiano , la configuración de productos y la recuperación de información privada . ^{[ 13 ] [ 14 ]}

Cualquier BDD arbitrario (incluso si no es reducido u ordenado) puede implementarse directamente en hardware reemplazando cada nodo con un multiplexor de 2 a 1 ; cada multiplexor puede implementarse directamente con una LUT de 4 bits en una FPGA . No es tan sencillo convertir una red arbitraria de puertas lógicas a un BDD (a diferencia del grafo inversor AND ).

Los BDD se han aplicado en intérpretes Datalog eficientes . ^{[ 15 ]}

El tamaño del BDD está determinado tanto por la función que se representa como por el orden elegido de las variables. Existen funciones booleanas.${\displaystyle f(x_{1},\ldots ,x_{n})}$para lo cual, dependiendo del orden de las variables, terminaríamos obteniendo un grafo cuyo número de nodos sería lineal (en n ) en el mejor de los casos y exponencial en el peor (por ejemplo, un sumador de acarreo en cascada ). Consideremos la función booleana ${\displaystyle f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.}$Utilizando el orden de variables${\displaystyle x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}}$, el BDD necesita${\displaystyle 2^{n+1}}$nodos para representar la función. Utilizando el ordenamiento${\displaystyle x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}}$, el BDD consta de${\displaystyle 2n+2}$nodos.

Es de vital importancia considerar el orden de las variables al aplicar esta estructura de datos en la práctica. El problema de encontrar el mejor orden de variables es NP-difícil . ^{[ 16 ]} Para cualquier constante c  >  1, es incluso NP-difícil calcular un orden de variables que dé como resultado un OBDD con un tamaño que sea como máximo c veces mayor que uno óptimo. ^{[ 17 ]} Sin embargo, existen heurísticas eficientes para abordar el problema. ^{[ 18 ]}

Hay funciones para las cuales el tamaño de la gráfica siempre es exponencial, independientemente del orden de las variables. Esto se cumple, por ejemplo, para la función de multiplicación. ^{[ 1 ]} De hecho, la función que calcula el bit central del producto de dos${\displaystyle n}$-los números de bits no tienen un OBDD menor que${\displaystyle 2^{\lfloor n/2\rfloor }/61-4}$vértices. ^{[ 19 ]} (Si la función de multiplicación tuviera OBDD de tamaño polinomial, mostraría que la factorización entera está en P/poly , lo cual no se sabe que sea cierto. ^{[ 20 ]} ) Otro ejemplo notorio es la función de bit de peso oculto, considerada como la función más simple con un BDD de tamaño exponencial. ^{[ 21 ]}

Los investigadores han sugerido mejoras en la estructura de datos BDD, dando lugar a una serie de gráficos relacionados, tales como:

• BMD ( diagramas de momentos binarios ),
• ZDD ( diagramas de decisión con supresión de ceros ),
• FBDD ( diagramas de decisión binarios libres ), donde cualquier ruta desde la raíz hasta un nodo hoja lee cada variable como máximo una vez. Cualquier OBDD es un FBDD.
• FDD ( diagramas de decisión funcional ),
• MDD ( diagramas de decisión multivaluados ), que generalizan los BDD al permitir que las variables de decisión tomen más de dos valores, ^{[ 22 ]}
• PDD ( diagramas de decisión de paridad ),
• MTBDD (BDD de múltiples terminales),
• TDD ( diagramas de decisión ternarios ), donde se agrega una rama "desconocida" para hacer que las operaciones consecutivas de unión/disyunción sean perezosas , evitando el crecimiento exponencial del tamaño. ^{[ 23 ]}
• NDD ( diagramas de decisión de red ),

Muchas operaciones lógicas en BDD se pueden implementar mediante algoritmos de manipulación de grafos de tiempo polinomial : ^{[ 24 ] : 20}

• conjunción
• disyunción
• negación

Sin embargo, repetir estas operaciones varias veces, por ejemplo, formar la conjunción o disyunción de un conjunto de BDD, puede, en el peor de los casos, resultar en un BDD exponencialmente grande. Esto se debe a que cualquiera de las operaciones anteriores para dos BDD puede resultar en un BDD con un tamaño proporcional al producto de los tamaños de los BDD, y, en consecuencia, para varios BDD el tamaño puede ser exponencial en el número de operaciones. Es necesario reconsiderar el orden de las variables; lo que puede ser un buen orden para (algunos de) los BDD del conjunto puede no ser un buen orden para el resultado de la operación. Además, dado que la construcción del BDD de una función booleana resuelve el problema de satisfacibilidad booleana NP-completo y el problema de tautología co-NP-completo , la construcción del BDD puede tomar un tiempo exponencial en el tamaño de la fórmula booleana, incluso cuando el BDD resultante es pequeño.

El cálculo de la abstracción existencial sobre múltiples variables de BDD reducidos es NP-completo. ^{[ 25 ]}

El conteo de modelos, que consiste en contar el número de asignaciones que satisfacen una fórmula booleana, se puede realizar en tiempo polinomial para BDDs. Para fórmulas proposicionales generales, el problema es ♯P -completo y los mejores algoritmos conocidos requieren un tiempo exponencial en el peor de los casos.

• Problema de satisfacibilidad booleana , el problema computacional NP-completo canónico.
• L/poly , una clase de complejidad que contiene estrictamente el conjunto de problemas con BDD de tamaño polinomial.
• Verificación de modelos
• Árbol de raíz
• Teorema de Barrington
• aceleración de hardware
• Mapa de Karnaugh , un método para simplificar expresiones de álgebra booleana.
• Diagrama de decisión con supresión de ceros
• Diagrama de decisión algebraico , una generalización de los BDD desde conjuntos de dos elementos a conjuntos finitos arbitrarios.
• Diagrama de decisión sentencial , una generalización de OBDD
• Diagrama de influencia

• Ubar, R. (1976). "Generación de pruebas para circuitos digitales mediante grafos alternativos". Actas de la Universidad Técnica de Tallin (en ruso) (409). Tallin, Estonia: 75–81 .
• Meinel, C.; Theobald, T. (2012) [1998]. Algoritmos y estructuras de datos en el diseño VLSI: OBDD – Fundamentos y aplicaciones (PDF) . Springer. ISBN 978-3-642-58940-9.Libro de texto completo disponible para su descarga.
• Ebendt, Rüdiger; Fey, Görschwin; Drechsler, Rolf (2005). Optimización BDD avanzada . Saltador. ISBN 978-0-387-25453-1.
• Becker, Bernd; Drechsler, Rolf (1998). Diagramas de decisión binaria: teoría e implementación . Saltador. ISBN 978-1-4419-5047-5.

• Diversión con diagramas de decisión binarios (BDD) , conferencia de Donald Knuth
• Lista de bibliotecas de software BDD para varios lenguajes de programación.