Алгебраическая диаграмма решений

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

Определение

ADD представляет собой логическую функцию из $\{0,1\}^{n}$ конечному набору констант S или носителю алгебраической структуры . ADD — это корневой направленный ациклический граф, который имеет несколько узлов, как и BDD. Однако ADD может иметь более двух конечных узлов, которые являются элементами множества S, в отличие от BDD.

ADD также можно рассматривать как булеву функцию или векторную булеву функцию , расширяя кодомен функции, так что $f:\{0,1\}^{n}\to Q$ с $S\subseteq Q$ и $card(Q)=2^{n}$ для некоторого целого числа n. Следовательно, к ADD применимы теоремы булевой алгебры , особенно теорема разложения Буля . ^[1]

Каждый узел помечен логической переменной и имеет два исходящих ребра: 1-ребро, которое представляет оценку переменной как значение ИСТИНА, и 0-ребро для ее оценки как ЛОЖЬ.

ADD использует те же правила сокращения, что и BDD (или сокращенный упорядоченный BDD ):

объединить любые изоморфные подграфы и
исключить любой узел, два дочерних узла которого изоморфны.

ADD являются каноническими в соответствии с определенным порядком переменных.

Матричное разбиение

ADD может быть представлен матрицей в соответствии со своими кофакторами. ^[2]^[1]

Приложения

ADD были впервые реализованы для умножения разреженных матриц и алгоритмов кратчайшего пути ( процедуры Беллмана-Форда , повторного возведения в квадрат и Флойда-Уоршалла ). процедуры ^[1]

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Бахар, Род-Айленд; Фром, Э.А.; Гаона, СМ; Хачтель, Джорджия; Маций, Э.; Пардо, А.; Соменци, Ф. (1993). «Алгебраические диаграммы решений и их приложения» . Материалы Международной конференции по компьютерному проектированию (ICCAD) 1993 года . IEEE-компьютер. Соц. Нажимать. стр. 188–191. дои : 10.1109/iccad.1993.580054 . ISBN 0-8186-4490-7 . S2CID 43177472 .
^ Перейти обратно: ^а ^б Фудзита, М.; МакГир, ПК; Ян, JC-Y. (1 апреля 1997 г.). «Многотерминальные двоичные диаграммы решений: эффективная структура данных для матричного представления» . Формальные методы проектирования систем . 10 (2): 149–169. дои : 10.1023/А:1008647823331 . ISSN 1572-8102 . S2CID 30494217 .

[:1-1] Перейти обратно: ^а ^б ^с ^д Бахар, Род-Айленд; Фром, Э.А.; Гаона, СМ; Хачтель, Джорджия; Маций, Э.; Пардо, А.; Соменци, Ф. (1993). «Алгебраические диаграммы решений и их приложения» . Материалы Международной конференции по компьютерному проектированию (ICCAD) 1993 года . IEEE-компьютер. Соц. Нажимать. стр. 188–191. дои : 10.1109/iccad.1993.580054 . ISBN 0-8186-4490-7 . S2CID 43177472 .

[:0-2] Перейти обратно: ^а ^б Фудзита, М.; МакГир, ПК; Ян, JC-Y. (1 апреля 1997 г.). «Многотерминальные двоичные диаграммы решений: эффективная структура данных для матричного представления» . Формальные методы проектирования систем . 10 (2): 149–169. дои : 10.1023/А:1008647823331 . ISSN 1572-8102 . S2CID 30494217 .

[1]

[2]