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.

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

Definición

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: ${\displaystyle u}$ ${\displaystyle x_{i}}$ ${\displaystyle u}$ ${\displaystyle 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 Ordenada Reducida ( ROBDD en la literatura, utilizado cuando se necesita enfatizar los aspectos de ordenación 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).

Ejemplo

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}}$

Bordes complementados

Representación de un diagrama de decisión binario utilizando aristas complementadas

Un ROBDD se puede representar de forma aún más compacta, utilizando aristas complementadas. ^{[2] [3]} 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, los 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
• Se reduce el uso del espacio (es decir, la memoria requerida).

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})}$

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) 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, ^[4] y estudiados y difundidos por Sheldon B. Akers ^[5] y Raymond T. Boute. ^[6] 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. ^[7] 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. ^{[8] [9]} 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) , ^[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 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.

Aplicaciones

Los BDD se utilizan ampliamente en el 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 . ^{[11] [12] [ 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 . ^[13]

Ordenación variable

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 . ^[14] Para cualquier constante c  > 1 es incluso NP-difícil calcular un orden de las variables que dé como resultado un OBDD con un tamaño que sea como máximo c veces mayor que uno óptimo. ^[15] Sin embargo, existen heurísticas eficientes para abordar el problema. ^[16]

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. ^[17] (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. ^[18] ) ${\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 terminales múltiples).

Operaciones lógicas en BDD

Muchas operaciones lógicas en BDD se pueden implementar mediante algoritmos de manipulación de gráficos en 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 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. ^[20]

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

Véase también

• Problema de satisfacibilidad booleano , 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 ^{[ 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

Referencias

1. Bryant, Randal E. (agosto de 1986). "Algoritmos basados ​​en grafos para manipulación de funciones booleanas" (PDF) . IEEE Transactions on Computers . 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 del diseño ACM/IEEE (DAC 1990) . IEEE Computer Society Press. 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 . NATO Science Series F: Ciencias informáticas y de sistemas. Vol. 173. IOS Press. 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". Bell System Technical Journal . 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". IEEE Transactions on Computers . 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 asincrónicos (PhD). Instituto Electrotécnico de Leningrado.
8. Bryant, Randal E. (1986). "Algoritmos basados ​​en gráficos para la manipulación de funciones booleanas" (PDF) . IEEE Transactions on Computers . 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 binarios ordenados". Encuestas de computación ACM . 24 (3): 293–318. doi :10.1145/136035.136043. S2CID  1933530.
10. "Stanford Center for Professional Development". 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 C++ para la configuración rápida e interactiva de productos sin retroceso". Actas de la Décima Conferencia Internacional sobre Principios y Práctica de la Programación con Restricciones . Apuntes de clase en Ciencias de la Computación. Vol. 3258. Springer. pág. 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) . Conferencia internacional sobre seguridad de la información y criptología . Notas de clase en informática. Vol. 5984. Springer. págs. 193–210. doi :10.1007/978-3-642-14423-3_14. ISBN. 978-3-642-14423-3.
13. Whaley, John; Avots, Dzintars; Carbin, Michael; Lam, Monica S. (2005). "Uso de Datalog con diagramas de decisión binarios para el análisis de programas". En Yi, Kwangkeun (ed.). Lenguajes y sistemas de programación . Apuntes de clase en 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). "Mejorar el ordenamiento de variables de los OBDD es NP-completo". IEEE Transactions on Computers . 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. Rice, Michael. "Un estudio de las heurísticas de ordenamiento de variables estáticas para la construcción eficiente de BDD/MDD" (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 factorización". La carta perdida de Gödel y P=NP , 2009.
19. Andersen, HR (1999). "Introducción a los diagramas de decisión binarios" (PDF) . Apuntes de la clase . Universidad de Tecnología de la Información de Copenhague.
20. Huth, Michael; Ryan, Mark (2004). Lógica en informática: modelado y razonamiento sobre sistemas (2.ª ed.). Cambridge University Press. pp. 380–. ISBN 978-0-52154310-1.OCLC 54960031  .

Lectura adicional

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

Enlaces externos

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