Diagrama de decisión binaria

Estructura de datos para funciones booleanas

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.

Estructuras de datos similares incluyen la forma normal de negación (NNF), polinomios de Zhegalkin y gráficos acíclicos dirigidos proposicionales (PDAG).

Definición

Una función booleana se puede representar como un gráfico 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 hijo bajo y hijo alto. El borde del nodo a un hijo bajo (o alto) representa una asignación del valor FALSO (o VERDADERO, respectivamente) a la variable . Un BDD de este tipo se denomina "ordenado" si diferentes variables aparecen en el mismo orden en todas las rutas desde la raíz. Se dice que un BDD está 'reducido' si se han aplicado las dos reglas siguientes a su gráfico: ${\displaystyle u}$ ${\displaystyle x_{i}}$ ${\displaystyle u}$ ${\displaystyle x_{i}}$

• Fusiona cualquier subgrafo isomórfico .
• Elimina cualquier nodo cuyos dos hijos sean isomorfos.

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

Ejemplo

La siguiente 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 de las cuales representa la función . En el árbol de la izquierda, el valor de la función se puede determinar para una asignación de variable determinada siguiendo una ruta por el gráfico hasta una terminal. En las figuras siguientes, las líneas de puntos representan los bordes para un niño bajo, mientras que las líneas continuas representan los bordes para un niño alto. Por lo tanto, para encontrar , comience en x ₁ , recorra la línea de puntos hasta x ₂ (ya que x ₁ tiene una asignación a 0), luego baje dos líneas continuas (ya que x ₂ y x ₃ tienen cada una una asignación a uno). Esto lleva al 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 de acuerdo con las dos reglas de reducción. El BDD 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}}$

Bordes complementados

Representación de un diagrama de decisión binaria utilizando aristas complementadas.

Un ROBDD se puede representar de forma aún más compacta, utilizando aristas complementadas. ^{[2] [3]} Los bordes complementados se forman anotando los bordes inferiores como complementados 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 de ese nodo). Los bordes altos no se complementan para garantizar que la representación BDD resultante sea una forma canónica. En esta representación, los BDD tienen un nodo de hoja única, por las razones que se explican a continuación.

Dos ventajas de utilizar aristas complementadas al representar BDD son:

• calcular la negación de un BDD requiere un tiempo constante
• El uso de espacio (es decir, la memoria requerida) se reduce.

Una referencia a un BDD en esta representación es un "borde" (posiblemente complementado) 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 están representadas por 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é es suficiente un solo nodo hoja: FALSO está representado por un borde complementado que apunta al nodo hoja, y VERDADERO está representado por un borde ordinario (es decir, no complementado) que apunta al nodo hoja.

Por ejemplo, supongamos que una función booleana se representa con un BDD representado 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 el borde de referencia, que apunta a la raíz del BDD, y seguimos la ruta definida por los valores de las variables dados (siguiendo un borde inferior si la variable que etiqueta un nodo es FALSO, y siguiendo el borde superior si la variable que etiqueta un nodo es VERDADERO), hasta llegar al nodo hoja. Mientras seguimos este camino, contamos cuántas aristas complementadas hemos atravesado. 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 variable dada es FALSO, en caso 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 VERDADERA.

A la derecha se muestra un diagrama de ejemplo de un BDD en esta representación, y representa la misma expresión booleana que se muestra en los diagramas anteriores, es decir ,. Los bordes inferiores son discontinuos, los bordes altos 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 al BDD, es decir, el borde de referencia es el borde que parte de 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})}$

Historia

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) asignando una variable (cf. forma normal if-then-else ). Si dicha subfunción se considera un subárbol, se puede representar mediante un árbol de decisión binario . Los diagramas de decisión binaria (BDD) fueron introducidos por CY Lee ^[4] y Sheldon B. Akers ^[5] y Raymond T. Boute los estudiaron y dieron a conocer más a fondo. ^[6] Independientemente de estos autores, se realizó un BDD bajo el nombre "forma de soporte canónico" Yu. V. Mamrukov en un CAD para el análisis de circuitos independientes de la velocidad. ^[7] Randal Bryant en la Universidad Carnegie Mellon investigó todo el potencial de los algoritmos eficientes basados ​​en la estructura de datos : sus extensiones clave fueron utilizar un orden de variables fijo (para la representación canónica) y subgráficos compartidos (para la compresión). La aplicación de estos dos conceptos da como resultado una estructura de datos y algoritmos eficientes para la representación de conjuntos y relaciones. ^{[8] [9]} Al extender el uso compartido a varios BDD, es decir, varios BDD utilizan un subgráfico, se define la estructura de datos Diagrama de decisión binaria ordenado, reducido y compartido . ^[2] La noción de BDD ahora se usa generalmente para referirse a esa estructura de datos en particular.

En su videoconferencia Fun With Binary Decision Diagrams (BDD) , ^[10] 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 los BDD son una de varias formas normales de 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.

Aplicaciones

Los BDD se utilizan ampliamente en software CAD para sintetizar circuitos ( síntesis lógica ) y en 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 . ^{[11] [12] [ cita necesaria ]}

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 puede implementarse directamente mediante un 4-LUT en una FPGA . No es tan sencillo convertir de una red arbitraria de puertas lógicas a un BDD ^{[ cita necesaria ]} (a diferencia del gráfico inversor-y ).

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

Ordenación de variables

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 para las cuales, dependiendo del orden de las variables, terminaríamos obteniendo un gráfico 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 el orden de variables , el BDD necesita nodos para representar la función. Usando el ordenamiento , el 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 preocuparse por 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 . ^[14] Para cualquier constante c  > 1, es incluso NP-difícil calcular un ordenamiento de variables que dé como resultado un OBDD con un tamaño que es como máximo c veces mayor que uno óptimo. ^[15] Sin embargo, existen heurísticas eficientes para abordar el problema. ^[dieciséis]

Hay funciones para las cuales el tamaño del gráfico es siempre exponencial, independientemente del orden de las variables. Esto es válido, 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. ^[17] (Si la función de multiplicación tuviera OBDD de tamaño polinomial, mostraría que la factorización de enteros está en P/poly , lo cual no se sabe que sea cierto. ^[18] ) ${\displaystyle n}$ ${\displaystyle 2^{\lfloor n/2\rfloor }/61-4}$

Los investigadores han sugerido mejoras en la estructura de datos BDD dando paso a una serie de gráficos relacionados, como BMD ( diagramas de momento binarios ), ZDD ( diagramas de decisión con supresión de ceros ), FBDD (diagramas de decisión binarios libres), FDD (diagramas de decisión funcionales). , PDD (diagramas de decisión de paridad) y MTBDD (BDD de múltiples terminales).

Operaciones lógicas en BDD

Muchas operaciones lógicas en BDD se pueden implementar mediante algoritmos de manipulación de gráficos de tiempo polinomial : ^{[19] : 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 un BDD exponencialmente grande. Esto se debe a que cualquiera de las operaciones anteriores para dos BDD puede dar como resultado 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 considerar nuevamente el orden de las variables; lo que puede ser un buen orden para (algunos de) el conjunto de BDD puede no ser un buen orden para el resultado de la operación. Además, dado que construir el BDD de una función booleana resuelve el problema de satisfacibilidad booleano NP-completo y el problema de tautología co-NP-completo , construir el BDD puede tomar un tiempo exponencial en el tamaño de la fórmula booleana incluso cuando el BDD resultante es pequeño.

Computar la abstracción existencial sobre múltiples variables de BDD reducidos es NP-completo. ^[20]

El recuento de modelos, es decir, el número de asignaciones satisfactorias de una fórmula booleana, se puede realizar en tiempo polinomial para BDD. Para 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.

Ver también

• Problema de satisfacibilidad booleana , el problema computacional canónico NP-completo
• L/poly , una clase de complejidad que contiene estrictamente el conjunto de problemas con BDD de tamaño polinómico ^{[ cita necesaria ]}
• Comprobación de modelos
• árbol de raíz
• teorema de barrington
• Aceleracion 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 algebraica , una generalización de BDD desde dos elementos hasta conjuntos finitos arbitrarios
• Diagrama de decisión sentencial , una generalización de los OBDD
• Diagrama de influencia

Referencias

1. Bryant, Randal E. (agosto de 1986). "Algoritmos basados ​​en gráficos para la manipulación de funciones booleanas" (PDF) . Transacciones IEEE en computadoras . C-35 (8): 677–691. CiteSeerX  10.1.1.476.2952 . doi :10.1109/TC.1986.1676819. S2CID  10385726.
2. Brace, Karl S.; Rudell, Richard L.; Bryant, Randal E. (1990). "Implementación eficiente de un paquete BDD". Actas de la 27ª Conferencia de Automatización de Diseño ACM/IEEE (DAC 1990) . Prensa de la Sociedad de Computación IEEE. págs. 40–45. doi :10.1145/123186.123222. ISBN 978-0-89791-363-8.
3. Somenzi, Fabio (1999). «Diagramas de decisión binaria» (PDF) . Diseño de sistemas de cálculo . Serie Científica F de la OTAN: Ciencias de la computación y de sistemas. vol. 173. Prensa IOS. págs. 303–366. ISBN 978-90-5199-459-9.
4. Lee, CY (1959). "Representación de circuitos de conmutación mediante programas de decisión binaria". Revista técnica del sistema Bell . 38 (4): 985–999. doi :10.1002/j.1538-7305.1959.tb01585.x.
5. Akers, Jr., Sheldon B (junio de 1978). "Diagramas de decisión binaria". Transacciones IEEE en computadoras . C-27 (6): 509–516. doi :10.1109/TC.1978.1675141. S2CID  21028055.
6. Boute, Raymond T. (enero de 1976). "La Máquina de Decisión Binaria como controlador programable". Boletín EUROMICRO . 1 (2): 16–22. doi :10.1016/0303-1268(76)90033-X.
7. Mamrukov, Yu. V. (1984). Análisis de circuitos aperiódicos y procesos asíncronos (Doctor). Instituto Electrotécnico de Leningrado.
8. Bryant., Randal E. (1986). "Algoritmos basados ​​en gráficos para la manipulación de funciones booleanas" (PDF) . Transacciones IEEE en computadoras . C-35 (8): 677–691. doi :10.1109/TC.1986.1676819. S2CID  10385726.
9. Bryant, Randal E. (septiembre de 1992). "Manipulación booleana simbólica con diagramas de decisión binaria ordenados". Encuestas de Computación ACM . 24 (3): 293–318. doi :10.1145/136035.136043. S2CID  1933530.
10. "Centro de Stanford para el desarrollo profesional". scpd.stanford.edu . Archivado desde el original el 4 de junio de 2014 . Consultado el 23 de abril de 2018 .
11. Jensen, RM (2004). "CLab: una biblioteca de C++ para una configuración rápida de productos interactivos sin retrocesos". Actas de la Décima Conferencia Internacional sobre Principios y Práctica de la Programación de Restricciones . Apuntes de conferencias sobre informática. vol. 3258. Saltador. pag. 816. doi :10.1007/978-3-540-30201-8_94. ISBN 978-3-540-30201-8.
12. Lipmaa, HL (2009). "Primer protocolo CPIR con computación dependiente de datos" (PDF) . Congreso Internacional sobre Seguridad de la Información y Criptología . Apuntes de conferencias sobre informática. vol. 5984. Saltador. págs. 193-210. doi :10.1007/978-3-642-14423-3_14. ISBN 978-3-642-14423-3.
13. Ballenay, John; Avots, Dzintars; Carbin, Michael; Lam, Mónica S. (2005). "Uso de registro de datos con diagramas de decisión binaria para análisis de programas". En Yi, Kwangkeun (ed.). Lenguajes y Sistemas de Programación . Apuntes de conferencias sobre informática. vol. 3780. Berlín, Heidelberg: Springer. págs. 97-118. doi :10.1007/11575467_8. ISBN 978-3-540-32247-4. S2CID  5223577.
14. Bollig, Beate; Wegener, Ingo (septiembre de 1996). "La mejora del orden de las variables de los OBDD es NP-completa". Transacciones IEEE en computadoras . 45 (9): 993–1002. doi : 10.1109/12.537122.
15. Sieling, Detlef (2002). "La no aproximabilidad de la minimización de OBDD". Información y Computación . 172 (2): 103-138. doi : 10.1006/inco.2001.3076 .
16. Arroz, Michael. "Un estudio sobre heurísticas de ordenamiento de variables estáticas para una construcción BDD/MDD eficiente" (PDF) .
17. Woelfel, Philipp (2005). "Límites del tamaño OBDD de la multiplicación de enteros mediante hash universal". Revista de Ciencias de la Computación y de Sistemas . 71 (4): 520–534. CiteSeerX 10.1.1.138.6771 . doi : 10.1016/j.jcss.2005.05.004 . 
18. Richard J. Lipton . "BDD y Factoring". La carta perdida de Gödel y P=NP , 2009.
19. Andersen, recursos humanos (1999). "Introducción a los diagramas de decisión binaria" (PDF) . Notas de lectura . Universidad de TI de Copenhague.
20. Huth, Michael; Ryan, marca (2004). Lógica en informática: modelado y razonamiento sobre sistemas (2ª ed.). Prensa de la Universidad de Cambridge. págs. 380–. ISBN 978-0-52154310-1. OCLC  54960031.

Otras lecturas

• 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.
• Knuth, DE (2009). Fascículo 1: Trucos y técnicas bit a bit; Diagramas de decisión binaria . El arte de la programación informática . vol. 4. Addison-Wesley. ISBN 978-0-321-58050-4.Borrador del fascículo 1b Archivado el 12 de marzo de 2016 en Wayback Machine disponible para descargar.
• Meinel, C.; Theobald, T. (2012) [1998]. Algoritmos y estructuras de datos en diseño VLSI: OBDD - Fundamentos y aplicaciones (PDF) . Saltador. 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.

enlaces externos

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