Алгебраическая диаграмма решений (ADD) или многотерминальная бинарная диаграмма решений (MTBDD) — это структура данных, которая используется для символического представления булевой функции, областью значений которой является произвольное конечное множество S. ADD — это расширение редуцированной упорядоченной бинарной диаграммы решений или, как ее обычно называют в литературе, бинарной диаграммы решений (BDD) , конечные узлы которой не ограничены булевыми значениями 0 (ЛОЖЬ) и 1 (ИСТИНА). [1] [2] Конечные узлы могут принимать любое значение из набора констант S.
ADD представляет собой булеву функцию от до конечного множества констант S, или носителя алгебраической структуры . ADD — это корневой, направленный, ациклический граф, имеющий несколько узлов, как и BDD. Однако ADD может иметь более двух конечных узлов, которые являются элементами множества S, в отличие от BDD.
ADD также можно рассматривать как булеву функцию или векторную булеву функцию , расширяя область значений функции, так что с и для некоторого целого числа n. Следовательно, теоремы булевой алгебры применимы к ADD, в частности, теорема Буля о расширении . [1]
Каждый узел помечен булевой переменной и имеет два исходящих ребра: 1-ребро, которое представляет оценку переменной до значения ИСТИНА, и 0-ребро для ее оценки до ЛОЖЬ.
ADD использует те же правила редукции, что и BDD (или редуцированный упорядоченный BDD ):
ADD являются каноническими в соответствии с определенным порядком переменных.
СДВГ может быть представлено матрицей в соответствии с ее кофакторами. [2] [1]
ADD были впервые реализованы для умножения разреженных матриц и алгоритмов кратчайшего пути ( процедуры Беллмана-Форда , повторного возведения в квадрат и Флойда-Уоршелла ). [1]
