4 / 16
И.В. Рудаков, Р.Е. Гурин
52
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2016. № 4
нетерминалами и для каждой такой вершины
v N
определены значение порядка
( ) {
, }
1,
index v
n
и ровно две дочерние вершины
( ,)
low v
( ) .
high v V
Индексы
нетерминальных вершин
i
соответствуют аргументам определяемой функции.
Вершины множества
T
называются терминалами и не имеют дочерних
вершин. Для каждой терминальной вершины
v T
определено значение
( )
value v S
и выполнено условие: для любого нетерминала
v N
и любой его
дочерней вершины
v
либо
,
v T
либо
( )
( ).
index v index v
Теперь каждой
вершине
v V
можно сопоставить функцию
:
v
f
{0, 1
{0,1}
:
n
S
1
( ) 1
( )
( ) 1
( )
( ),
;
,
,
,
,
,
1,
;
,
,
,
0,
.
v
n
high v
n
index v
low v
n
index v
value v v T
f x x
f
x x x
v N
f
x x x
v N
Существует несколько разновидностей решающих диаграмм. Для задач, кото-
рые связаны с использованием булевых функций вида
:
v
f
{0, 1
}
n
{0, 1} и ко-
нечных множеств, широко используются BDD [10]. Для задач, связанных с исполь-
зованием функций вида
:
v
f
{0, 1
}
n
S
(где
S
— некоторое конечное непустое
множество) и для нечетких множеств приме-
няются многотерминальные бинарные реша-
ющие диаграммы (MTBDD), а также их моди-
фикации. Многокор-невые бинарные решаю-
щие диаграммы (MRBDD) являются альтерна-
тивой MTBDD, которые работают с конечно-
значимыми функциями, как с векторами из
булевых функций. Основным преимуществом
MRBDD перед MTBDD является меньший
размер диаграммы. Это свойство достигается
за счет более эффективного повторного ис-
пользования фрагментов одинаковой структу-
ры. Рассмотрим пример. Далее приведена таб-
лица истинности функции
f
(табл. 1), а на рис. 1 — ее представление в виде бинар-
ного дерева решений.
Проведем сжатие бинарного представления системы в соответствии с тре-
мя правилами:
слияние дубликатов терминалов с соответствующим перенаправлением
дуг;
слияние дубликатов нетерминалов, т.
е. если нетерминальные вершины
u
,
v
N
такие, что
( )
( ),
( )
( ),
index u index v low u low v
( )
( ),
high u high v
то
вершины
u
и
v
совмещаются с соответствующим перенаправлением дуг;
удаление нетерминалов с одной дочерней вершиной с перенаправлением в
нее входящих дуг.
Таблица 1
Таблица истинности функции
f
1
x
2
x
3
x
f
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1