Diagrama de decisión binaria

En informática , un diagrama de decisión binaria ( BDD ) 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 BDD 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.

Las estructuras de datos similares incluyen la forma normal de negación (NNF), los polinomios de Zhegalkin y los gráficos 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) está etiquetado por una variable booleana y tiene dos nodos secundarios llamados secundario bajo y secundario alto. La arista del nodo a un secundario bajo (o alto) representa una asignación del valor FALSO (o VERDADERO, respectivamente) a la variable . Una BDD de este tipo se denomina "ordenada" si aparecen diferentes variables en el mismo orden en todas las rutas desde la raíz. Se dice que una BDD está "reducida" si se han aplicado las dos reglas siguientes a su grafo:${\estilo de visualización u}$$Estilo de visualización x_{i}}$${\estilo de visualización u}$$Estilo de visualización x_{i}}$

• Fusionar todos los subgrafos isomorfos .
• Elimina cualquier nodo cuyos dos hijos sean isomorfos.

En el uso popular, el término BDD casi siempre se refiere a Diagrama de decisión binaria ordenado reducido ( ROBDD en la literatura, utilizado cuando se necesita enfatizar los aspectos de ordenamiento y reducción). La ventaja de un ROBDD es que es canónico (único hasta el isomorfismo) para una función particular y un orden de variable. ^[1] Esta propiedad lo hace útil en la comprobació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 bajo (o alto) desde un nodo, la variable de ese nodo se asigna a 0 (respectivamente a 1).

La figura de la izquierda muestra un árbol de decisión binario (no se aplican las reglas de reducción) y una tabla de verdad , cada una representando la función . En el árbol de la izquierda, el valor de la función se puede determinar para una asignación de variable dada siguiendo una ruta hacia abajo en el gráfico hasta una terminal. En las figuras siguientes, las líneas punteadas representan aristas hacia un hijo bajo, mientras que las líneas continuas representan aristas hacia un hijo alto. Por lo tanto, para encontrar , comience en x ₁ , recorra hacia abajo la línea punteada hasta x ₂ (ya que x ₁ tiene una asignación a 0), luego hacia abajo dos líneas continuas (ya que x ₂ y x ₃ tienen cada uno una asignación a uno). Esto conduce a la terminal 1, que es el valor de .${\displaystyle f(x_{1},x_{2},x_{3})}$${\displaystyle f(0,1,1)}$${\displaystyle f(0,1,1)}$

El árbol de decisión binario de la figura de la izquierda se puede transformar en un diagrama de decisión binario reduciéndolo al máximo según las dos reglas de reducción. El diagrama de decisión binario resultante se muestra en la figura de la derecha.

Otra notación para escribir esta función booleana es .${\displaystyle {\overline {x}}_{1}{\overline {x}}_{2}{\overline {x}}_{3}+x_{1}x_{2}+x_{2}x_{3}}$

Un ROBDD se puede representar de forma aún más compacta, utilizando aristas complementadas, también conocidas como enlaces de complemento . ^{[2] [3]} El BDD resultante a veces se conoce como BDD tipado ^[4] o BDD firmado . Las aristas complementadas se forman anotando las aristas bajas como complementadas o no. Si una arista es 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 se complementan, para garantizar que la representación BDD resultante sea una forma canónica. En esta representación, las BDD tienen un solo nodo hoja, por las razones que se explican a continuación.

Dos ventajas de utilizar aristas complementadas al representar BDD son:

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

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

Aunque todos los paquetes BDD más importantes utilizan estos enlaces, es difícil recomendarlos porque los programas informáticos se vuelven mucho más complejos. El ahorro de memoria suele ser insignificante y nunca supera un factor de 2; además, los experimentos del autor muestran una pequeña ganancia en el tiempo de ejecución.

Una referencia a una BDD en esta representación es una "arista" (posiblemente complementada) que apunta a la raíz de la BDD. Esto contrasta con una referencia a una BDD en la representación sin el uso de aristas complementadas, que es el nodo raíz de la 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 una BDD y una arista complementada a la raíz de la misma BDD. Esta es la razón por la que la negación lleva un tiempo constante. También explica por qué un solo nodo hoja es suficiente: 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 con una BDD representada mediante aristas complementadas. Para encontrar 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 de la BDD, y seguimos el camino que está definido por los valores de las variables dadas (siguiendo una arista baja si la variable que etiqueta un nodo es igual a FALSO, y siguiendo la arista alta si la variable que etiqueta un nodo es igual a VERDADERO), hasta que llegamos al nodo hoja. Mientras seguimos este camino, contamos cuántas aristas complementadas hemos atravesado. Si cuando llegamos 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 variable dada es FALSO, 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 variable dada es VERDADERO.

A la derecha se muestra un diagrama de ejemplo de una BDD en esta representación, que representa la misma expresión booleana que se muestra en los diagramas anteriores, es decir, . Los bordes inferiores están discontinuos, los bordes superiores son sólidos y los bordes complementados se indican mediante un círculo en su origen. El nodo con el símbolo @ representa la referencia a la BDD, es decir, el borde de referencia es el borde que comienza desde este nodo.${\displaystyle (\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})}$

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) mediante la asignación de una variable (cf. forma normal if-then-else ). Si dicha subfunción se considera como un subárbol, se puede representar mediante un árbol de decisión binario . Los diagramas de decisión binarios (BDD) fueron introducidos por CY Lee, ^[6] y estudiados y difundidos por Sheldon B. Akers ^[7] y Raymond T. Boute. ^[8] Independientemente de estos autores, Yu. V. Mamrukov realizó 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 investigó todo el potencial de los algoritmos eficientes basados ​​en la estructura de datos en la Universidad Carnegie Mellon : sus extensiones clave fueron utilizar un ordenamiento de variables fijo (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 la compartición 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 ahora se utiliza generalmente para referirse a esa estructura de datos particular.

En su videoconferencia Fun With Binary Decision Diagrams (BDDs) , ^[12] Donald Knuth llama a los BDD "una de las únicas 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 algún tiempo uno de los artículos más citados en informática.

Adnan Darwiche y sus colaboradores han demostrado que las BDD son una de las diversas formas normales de las 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 la verificación formal . Existen varias aplicaciones menos conocidas de BDD, incluido el análisis de árboles de fallas , el razonamiento bayesiano , la configuración de productos y la recuperación de información privada . ^{[13] [14] [ cita requerida ]}

Cada BDD arbitrario (incluso si no está reducido ni ordenado) se puede implementar directamente en hardware reemplazando cada nodo con un multiplexor 2 a 1 ; cada multiplexor se puede implementar directamente mediante una LUT de 4 en un FPGA . No es tan simple convertir una red arbitraria de puertas lógicas a un BDD ^{[ cita requerida ]} (a diferencia del grafo inversor-y ).

Los BDD se han aplicado en intérpretes de registros de datos eficientes . ^[15]

El tamaño de la BDD está determinado tanto por la función que se representa como por el orden elegido de las variables. Existen funciones booleanas para las cuales, 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 de ondulación ). Considere la función booleana Usando la variable ordering , la BDD necesita nodos para representar la función. Usando ordering , la BDD consta de nodos.${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.}$${\displaystyle x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}}$${\displaystyle 2^{n+1}}$${\displaystyle x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}}$${\displaystyle 2n+2}$

Es de crucial importancia tener cuidado con el orden de las variables al aplicar esta estructura de datos en la práctica. El problema de encontrar el mejor orden de las variables es NP-difícil . ^[16] Para cualquier constante c  > 1 es incluso NP-difícil calcular un orden de las variables que resulte en 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]

Existen funciones para las cuales el tamaño del gráfico es siempre 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 medio del producto de números de dos bits no tiene un OBDD menor que los vértices. ^[19] (Si la función de multiplicación tuviera OBDD de tamaño polinomial, demostraría que la factorización de enteros está en P/poly , lo cual no se sabe si es cierto. ^[20] )${\displaystyle n}$${\displaystyle 2^{\lfloor n/2\rfloor }/61-4}$

Los investigadores han sugerido refinamientos en la estructura de datos BDD que dan lugar a una serie de gráficos relacionados, como BMD ( diagramas de momento binario ), ZDD ( diagramas de decisión con supresión de cero ), FBDD (diagramas de decisión binarios libres), FDD (diagramas de decisión funcional), PDD (diagramas de decisión de paridad) y MTBDD (BDD de múltiples terminales).

Muchas operaciones lógicas en BDD se pueden implementar mediante algoritmos de manipulación de gráficos en tiempo polinomial : ^{[21] : 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 dar como resultado una BDD exponencialmente grande. Esto se debe a que cualquiera de las operaciones anteriores para dos BDD puede dar como resultado una BDD con un tamaño proporcional al producto de los tamaños de las BDD y, en consecuencia, para varias BDD, el tamaño puede ser exponencial en el número de operaciones. El ordenamiento de las variables debe considerarse de nuevo; lo que puede ser un buen ordenamiento para (algunas de) las BDD del conjunto puede no ser un buen ordenamiento para el resultado de la operación. Además, dado que la construcción de la BDD de una función booleana resuelve el problema de satisfacibilidad booleana NP-completa y el problema de tautología co-NP-completa , la construcción de la BDD puede llevar un tiempo exponencial en el tamaño de la fórmula booleana incluso cuando la BDD resultante es pequeña.

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

El conteo de modelos, es decir, el conteo de la cantidad de asignaciones satisfactorias de una fórmula booleana, se puede realizar en tiempo polinomial para las BDD. Para las fórmulas proposicionales generales, el problema es ♯P -completo y los algoritmos más conocidos requieren un tiempo exponencial en el peor de los casos.

• Problema de satisfacibilidad booleano , 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 ^{[ cita requerida ]}
• Comprobación de modelos
• Árbol de base
• Teorema de Barrington
• Aceleración de hardware
• Mapa de Karnaugh , un método para simplificar expresiones del álgebra de Boole
• 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 hasta conjuntos finitos arbitrarios
• Diagrama de decisión oracional , una generalización de los OBDD
• Diagrama de influencia

• Ubar, R. (1976). "Generación de pruebas para circuitos digitales utilizando gráficos alternativos". Proc. 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 descargar.
• 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.

Wikimedia Commons tiene medios relacionados con Diagramas de decisión binaria .

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