Бинарная диаграмма принятия решений
-
Основы BDD
- BDD — это структура данных, которая представляет булевы функции в виде двоичных деревьев.
- BDD используются в программном обеспечении САПР для логического синтеза и верификации схем.
-
История и развитие
- Основная идея BDD основана на расширении Шеннона, которое разбивает функцию на две подфункции.
- C.Y. Ли и Шелдон Б. Эйкерс независимо разработали BDD, а Ю.Бут представил «каноническую форму скобок».
- Рэндал Брайант расширил BDD, используя фиксированный порядок переменных и общие подграфы.
- Дональд Кнут назвал BDD фундаментальной структурой данных в компьютерной науке.
-
Приложения и эффективность
- BDD применяются в различных областях, включая анализ дерева ошибок и байесовские рассуждения.
- Аппаратная реализация BDD возможна с использованием мультиплексоров и ПЛИС.
- Проблема упорядочения переменных для BDD является NP-сложной, но существуют эвристические методы.
-
Логические операции и сложность
- Многие логические операции с BDD могут быть выполнены за полиномиальное время.
- Повторение операций может привести к экспоненциальному увеличению размера BDD.
- Построение BDD для булевых формул может быть NP-полным и занимать экспоненциальное время.
-
Дополнительные структуры данных и задачи
- Существуют связанные структуры данных, такие как BMD, ZDD, FBDD и другие, которые расширяют возможности BDD.
- Вычисление экзистенциальной абстракции и подсчет модели для BDD являются NP-полными задачами.
-
Рекомендации и дальнейшее чтение
- Для более глубокого изучения BDD доступны черновики брошюр и полные учебники.
- Ссылки на лекции и программные библиотеки BDD также предоставлены.