Un diagrama de decisión algebraica (ADD) o un diagrama de decisión binario multiterminal (MTBDD), es una estructura de datos que se utiliza para representar simbólicamente una función booleana cuyo codominio es un conjunto finito arbitrario S. Un ADD es una extensión de un diagrama de decisión binario ordenado reducido, o comúnmente llamado diagrama de decisión binario (BDD) en la literatura, cuyos nodos terminales no están restringidos a los valores booleanos 0 (FALSO) y 1 (VERDADERO). [1] [2] Los nodos terminales pueden tomar cualquier valor de un conjunto de constantes S.
Un ADD representa una función booleana de un conjunto finito de constantes S, o portador de la estructura algebraica . Un ADD es un grafo acíclico, dirigido y con raíz, que tiene varios nodos, como un BDD. Sin embargo, un ADD puede tener más de dos nodos terminales que son elementos del conjunto S, a diferencia de un BDD.
Una ADD también puede verse como una función booleana, o una función booleana vectorial , al extender el codominio de la función, de modo que con y para algún entero n. Por lo tanto, los teoremas del álgebra de Boole se aplican a ADD, en particular el teorema de expansión de Boole . [1]
Cada nodo de está etiquetado por una variable booleana y tiene dos aristas salientes: una arista 1 que representa la evaluación de la variable al valor VERDADERO y una arista 0 para su evaluación a FALSO.
Un ADD emplea las mismas reglas de reducción que un BDD (o BDD ordenado reducido ):
Los ADD son canónicos según un orden de variables particular.
Un ADD puede representarse mediante una matriz de acuerdo a sus cofactores. [2] [1]
Los ADD se implementaron por primera vez para la multiplicación de matrices dispersas y algoritmos de ruta más corta ( procedimientos Bellman-Ford , Repeated Squaring y Floyd-Warshall ). [1]
