Diagrama de decisió binari

En les ciències de la computació, un diagrama de decisió binari (DDB) és una estructura de dades utilitzada per representar una funció booleana. Els DDBs poden ser considerats com una representació de conjunts o relacions. A diferència d'altres representacions comprimides, les operacions es realitzen directament en els DDB, sense necessitat de descomprimir-los.

Definició

Una funció booleana pot representar-se com un graf acíclic dirigit amb arrel, el qual posseeix varis nodes de decisió i dos nodes terminals anomenats terminal-0 i terminal-1. Cada node de decisió està etiquetat per una variable booleana (0 o 1) i té dos nodes fills, anomenats fill menor i fill gran. L'aresta que uneix un node amb un fill menor (major) representa una assignació de la variable amb el valor 0 (1).

Un DDB està ordenat si les diferents variables apareixen en el mateix ordre per tots els camins des de l'arrel. Un DDB està reduït si s'han aplicat dues regles següents al seu graf:

• Unir els isomorfismes dels subgrafs.
• Eliminar els nodes dels quals els seus dos fills siguin isomorfs.

En l'ús popular, el terme DDB també es refereix a Diagrama de decisió binari reduït ordenat (DDBRO, millor conegut en la literatura en anglès com ROBDD: Reduced Ordered Binary Decision Diagram). Un avantatge d'un DDBRO és que és canònic per a una funció particular i un ordre de variables. Aquesta propietat és útil per exemple en la verificació de funcions d'equivalència.^[1]

Un camí des del node arrel a la terminal-1 representa una assignació de variables (possiblement parcial) per a la qual la funció booleana és veritable. Si el camí descendeix des d'un node fins a un fill menor (major), la variable del node adquireix el valor 0 (1).^[2]

Història

La idea bàsica d'on prové aquesta estructura de dades és l'expansió de Shannon. Una funció booleana es divideix en dues sub-funcions (cofactors) mitjançant la incorporació d'una variable. Si tal sub-funció es considera com un sub-arbre, es pot representar per un arbre de decisió binari.

El màxim potencial d'aquesta estructura de dades per a ser utilitzada en la implementació d'algoritmes eficients va ser investigada per Randal Bryant a la Universitat Carnegie Mellon. La seva aportació clau va ser el fet d'utilitzar un ordre fixe de variables (per aconseguir una representació canònica) i sub-grafs compartits (per a més compressió). Aplicant tots dos conceptes va aconseguir una estructura de dades i algoritmes eficients per a la representació de conjunts i relaciones. Així es va definir l'estructura de dades Diagrama de decisió binari reduït ordenat i compartit (en anglès «Shared Reduced Ordered Binary Decision Diagram»), que permet que un sub-graf sigui utilitzat per diversos DDBs. Actualment, la noció de DDB s'utilitza generalment per referir-se a aquesta estructura de dades particular.^[3]

En la seva ponència en vídeo Fun With Binary Decision Diagrams (BDDs) («Diversió amb els diagrames de decisió binaris»), Donald Knuth es refereix als DDBs com «una de les úniques estructures de dades realment fonamentals que han aparegut en els últims 25 anys», i destaca el fet que article de Bryant de 1986 fos durant un temps un dels articles més citats en ciències de la computació.

Referències