Diagrama de decisión binaria

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de enero de 2020; las comprobaciones requieren 3 ediciones .

Un diagrama de decisión binario ( BDE ) o un programa de ramificación es una forma de representar una función booleana de variables como un gráfico acíclico dirigido , que consta de nodos de decisión internos (etiquetados ), cada uno de los cuales tiene dos hijos y dos nodos terminales (etiquetados 0 y 1), cada uno de los cuales corresponde a uno de los dos valores de la función booleana. En la literatura extranjera, los diagramas de decisión binarios y los programas de ramificación se denominan diagrama de decisión binario ( BDD ) y programas de ramificación ( BP ), respectivamente. $f(x_{1},x_{2},...,x_{n})$ $norte$ $x_{yo}$

Definición

Una función booleana se puede representar como un gráfico acíclico dirigido , que consta de varios nodos de decisión internos y dos nodos terminales, denominados nodo terminal 0 y nodo terminal 1. Cada nodo de decisión interno en un nivel está etiquetado con una variable booleana y tiene dos hijos , llamados hijo menor y hijo mayor. La transición de un nodo interno a un niño menor o mayor se realiza según el valor de la variable (0 o 1, respectivamente). Para los valores dados , la ruta desde el nodo raíz hasta el nodo 1-terminal corresponde al hecho de que en estos valores de entrada la función booleana toma el valor 1. $f(x_{1},x_{2},...,x_{n})$ $i$ $x_{yo}$ $x_{yo}$ $x_{yo}$ $x_{1},x_{2},...,x_{n}$ $f(x_{1},x_{2},...,x_{n})$

Se dice que un BDR está ordenado si diferentes variables aparecen en el mismo orden en todos los caminos desde el nodo raíz del gráfico hasta uno de los vértices terminales. Al mismo tiempo, algunas variables en los caminos pueden estar ausentes si la operación de reducción se realizó previamente en el gráfico.

Un BDR se denomina abreviado si se aplican al gráfico las siguientes dos reglas de abreviatura:

Fusión de subgrafos isomorfos .
Eliminación de todos los nodos con hijos isomorfos .

En la mayoría de los casos, un diagrama de decisión binario se entiende como un diagrama de decisión binario ordenado reducido ( SUBDR ). La ventaja de un BDD ordenado reducido es que es canónico (único) para una función particular y un orden dado de variables. [1] Esta propiedad hace que RUBMS sea útil para probar la equivalencia funcional.

Ejemplo

La figura de la izquierda muestra un árbol de decisión binario (sin aplicar las reglas de reducción) correspondiente a la tabla de verdad para la función booleana que se muestra en la misma figura . Para valores de entrada dados , puede determinar el valor de la función booleana moviéndose a lo largo del árbol desde el nodo raíz del árbol hasta los nodos terminales, eligiendo la dirección de transición desde el nodo según el valor de entrada . Las líneas punteadas en la figura representan transiciones a un niño más pequeño y las líneas continuas representan transiciones a un niño mayor. Por ejemplo, si se dan los valores de entrada ( , , ), entonces desde el nodo raíz debe ir a lo largo de la línea de puntos hacia la izquierda (ya que el valor es 0), luego debe ir a lo largo de las líneas continuas a la derecha (ya que los valores y y son iguales a 1). Como resultado, terminaremos en un nodo de 1 terminal, es decir, el valor es 1. $f(x_{1},x_{2},x_{3})$ $x_{1}$ $x_{2}$ $x_{3}$ $x_{yo}$ $x_{yo}$ $x_{1}=0$ $x_{2}=1$ $x_{3}=1$ $x_{1}$ $x_{1}$ $x_{2}$ $x_{3}$ $f(x_{1}=0,x_{2}=1,x_{3}=1)$

El árbol de decisión binario de la figura de la izquierda se puede convertir en un diagrama de decisión binario aplicando dos reglas de reducción. El BDR resultante se muestra en la figura de la derecha.

Historia

La idea principal para crear una estructura de datos de este tipo fue la descomposición de Shannon . Cualquier función booleana sobre una de las variables de entrada se puede dividir en dos subfunciones, denominadas complemento positivo y complemento negativo, de las cuales solo se selecciona una subfunción de acuerdo con el principio if-then-else , dependiendo del valor de la variable de entrada (sobre la cual se realizó la expansión de Shannon). Representando cada subfunción como un subárbol y continuando la expansión en las variables de entrada restantes, se puede obtener un árbol de decisión, cuya reducción dará un diagrama de decisión binario . La información sobre el uso de diagramas de decisión binarios o programas de bifurcación binaria se publicó por primera vez en 1959 en Bell Systems Technical Journal [2] [3] [4] . Mamrukov [5] implementó un BDD llamado forma canónica entre paréntesis en CAD para el análisis de circuitos independientes de la velocidad. Randal Bryant , de la Universidad Carnegie Mellon, exploró el potencial para crear algoritmos eficientes basados en esta estructura de datos : su enfoque consistía en utilizar un orden fijo de variables (para una representación canónica única de cada función booleana) y la reutilización de subgrafos comunes (para compacidad). ). La aplicación de estos dos conceptos clave permite aumentar la eficiencia de las estructuras de datos y los algoritmos para representar conjuntos y relaciones entre ellos. [6] [7] El uso de subgrafos comunes por varios BDR ha llevado a la aparición de la estructura de datos del diagrama de decisión binario ordenado reducido compartido . [8] El nombre BDR ahora se usa principalmente para esta estructura de datos en particular.

Donald Knuth , en su video conferencia Fun With Binary Decision Diagrams (BDD), llamó a los diagramas de decisión binarios " una de las estructuras de datos realmente fundamentales que han surgido en los últimos veinticinco años " y señaló que la publicación de Randal Bryant de 1986 [6 ] , que destacó el uso de diagramas binarios de decisión para la manipulación de funciones booleanas, fue durante algún tiempo la publicación más citada en informática.

Aplicación

Los BDR se utilizan ampliamente en sistemas de diseño asistido por computadora (CAD) para la síntesis de circuitos lógicos y en la verificación formal .

En electrónica, cada BDR específico (incluso no reducido y no ordenado) puede implementarse directamente reemplazando cada nodo con un multiplexor con dos entradas y una salida.

Orden de las variables

El tamaño del BDR está determinado tanto por una función booleana como por la elección del orden de las variables de entrada. Al compilar un gráfico para una función booleana, el número de nodos en el mejor de los casos puede depender linealmente de , y en el peor de los casos, la dependencia puede ser exponencial con una elección fallida del orden de las variables de entrada. Por ejemplo, dada una función booleana, si usa el orden de las variables , entonces necesita 2 n +1 nodos para representar la función en forma de BDD. En la figura de la izquierda se muestra un BDD ilustrativo para una función de 8 variables. Y si usa order , puede obtener un BDR equivalente de 2 n +2 nodos. En la figura de la derecha se muestra un BDD ilustrativo para una función de 8 variables. $f(x_{1},\ldots,x_{{n}})$ $norte$ $f(x_{1},\ldots,x_{{2n}})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{{2n-1}}x_{{ 2n}}.$ $x_{1}<x_{3}<\cdots <x_{{2n-1}}<x_{2}<x_{4}<\cdots <x_{{2n}}$ $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{{2n-1}}<x_{{2n}}$

La elección del orden de las variables es fundamental cuando se utilizan tales estructuras de datos en la práctica. El problema de encontrar el mejor orden de variables es un problema NP-completo . [9] Además, incluso el problema de encontrar un orden subóptimo de variables es NP-completo , tal que para cualquier constante c > 1 el tamaño del BDD es como mucho c veces mayor que el óptimo. [10] Sin embargo, existen heurísticas efectivas para resolver este problema.

Además, hay funciones para las que el tamaño del gráfico siempre crece exponencialmente a medida que aumenta el número de variables, independientemente del orden de las variables. Esto se aplica a las funciones de multiplicación, lo que indica la gran complejidad de la factorización .

La investigación sobre diagramas de decisión binarios ha llevado a la aparición de muchos tipos de gráficos relacionados, como BMD ( Diagramas de momento binario ), ZDD ( Diagrama de decisión con supresión cero ), FDD ( Diagramas de decisión binarios libres ), PDD ( Diagramas de decisión de paridad ) y MTBDD (Multiple terminal BDD).

Operaciones lógicas en diagramas de decisión binarios

Muchas operaciones lógicas ( conjunción , disyunción , negación ) se pueden realizar directamente en el BDR utilizando algoritmos que realizan manipulaciones de gráficos en tiempo polinomial. Sin embargo, repetir estas operaciones muchas veces, por ejemplo, al formar conjunciones o disyunciones de un conjunto de BDD, puede conducir a un BDD exponencialmente grande en el peor de los casos. Esto se debe a que cualquier operación previa en dos BDR generalmente puede dar como resultado un BDR con un tamaño proporcional al producto de los tamaños anteriores, por lo que para múltiples BDR, el tamaño puede aumentar exponencialmente.

Véase también

Notas

↑ Algoritmos basados en gráficos para la manipulación de funciones booleanas, Randal E. Bryant, 1986
↑ Cy Lee. "Representación de circuitos de conmutación por programas de decisión binaria". Boletín técnico de Bell Systems, 38:985-999, 1959.
↑ Sheldon B. Akers. Diagramas de decisión binarios Archivado el 7 de agosto de 2007 en Wayback Machine (enlace descendente desde el 13/05/2013 [3458 días] - historial ) , IEEE Transactions on Computers, C-27(6):509-516, junio de 1978.
↑ Raymond T. Boute, "La máquina de decisión binaria como controlador programable". Boletín EUROMICRO , vol. 1(2):16-22, enero de 1976
↑ Yu. V. Mamrukov, Análisis de circuitos aperiódicos y procesos asíncronos. Tesis doctoral LETI, 1984, 219p.
↑ 1 2 Randal E. Bryant. " Algoritmos basados en gráficos para la manipulación de funciones booleanas Archivado el 23 de septiembre de 2015 en Wayback Machine ". IEEE Transactions on Computers, C-35(8):677-691, 1986.
↑ RE Bryant, " Manipulación booleana simbólica con diagramas de decisión binarios ordenados" , archivado el 23 de septiembre de 2015 en Wayback Machine , ACM Computing Surveys, vol. 24, núm. 3 (septiembre de 1992), págs. 293-318.
↑ Karl S. Brace, Richard L. Rudell y Randal E. Bryant. " Implementación Eficiente de un Paquete BDD" . En Actas de la 27.ª Conferencia de Automatización de Diseño ACM/IEEE (DAC 1990), páginas 40-45. IEEE Computer Society Press, 1990.
↑ Beate Bollig, Ingo Wegener. La mejora del orden variable de los OBDD es NP-Complete , IEEE Transactions on Computers, 45(9):993-1002, septiembre de 1996.
↑ Detlef Seeling. "La no aproximación de la minimización de OBDD". Información y Computación 172, 103-138. 2002.

R. Ubar, "Generación de pruebas para circuitos digitales utilizando gráficos alternativos (en ruso)", en Proc. Universidad Técnica de Tallin, 1976, No.409, Universidad Técnica de Tallin, Tallin, Estonia, págs. 75–81.

Lectura sugerida

DE Knuth, "El arte de la programación informática Volumen 4, Fascículo 1: Trucos y técnicas bit a bit; Diagramas de decisión binarios" (Addison-Wesley Professional, 27 de marzo de 2009) viii+260pp, ISBN 0-321-58050-8 . Borrador del Fascículo 1b disponible para descargar.
H.R. Andersen " Introducción a los diagramas de decisión binarios ", Lecture Notes, 1999, Universidad de TI de Copenhague.
cap. Meinel, T. Theobald, " Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications" , Springer-Verlag, Berlín, Heidelberg, Nueva York, 1998. Libro de texto completo disponible para descargar.
Rudiger Ebendt; Gorschwin Fey; Rolf Drechsler. Optimización avanzada de BDD . — Springer, 2005. - ISBN 978-0-387-25453-1 .
Bernd Becker; Rolf Drechsler. Diagramas de Decisión Binaria : Teoría e Implementación . — Springer, 1998. - ISBN 978-1-4419-5047-5 .

Enlaces

ABCD : El paquete ABCD por Armin Biere, Johannes Kepler Universität, Linz.
CMU BDD , paquete BDD, Universidad Carnegie Mellon, Pittsburgh
CUDD : paquete BDD, Universidad de Colorado, Boulder
Instalación de CUDD en entornos Windows/Visual Studio.
Biddy : paquete BDD académico multiplataforma, Universidad de Maribor, Eslovenia
JavaBDD , un puerto Java de BuDDy que también interactúa con CUDD, CAL y JDD
El paquete CAL de Berkeley que realiza una manipulación en amplitud
A. Costa BFunc , incluye un simplificador lógico booleano BDD que admite hasta 32 entradas / 32 salidas (independientemente)
DDD : una biblioteca de C++ compatible con diagramas de decisión jerárquicos y de valores enteros.
JINC : una biblioteca de C++ desarrollada en la Universidad de Bonn, Alemania, que admite varias variantes de BDD y subprocesos múltiples.

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila