Каково значение и значение "пути" в BDD или FDD?

Question

Я прочитал статью под названием " Многоуровневый логический синтез на основе диаграмм функциональных решений", которая посвящена диаграммам функциональных решений (FDD) и представляет собой вариант диаграмм двоичных решений (BDD). В этом абзаце упоминается "путь":

В качестве важного результата наблюдается, что даже при почти одинаковом количестве узлов мы получаем уменьшение количества путей по сравнению с BDD (см. Табл. 1). Поскольку число путей равно числу пи-членов канонического двухуровневого RME, это означает уменьшение сложности в представлении функции.

Я предполагаю, что "путь" означает количество дорог от корня до терминала в BDD или FDD.

Например:

Путь этого примера 9(вы можете проверить это).

У меня вопрос, каково значение этого параметра или функции "путь"?

Answer 1

Да, путь - это любой путь от корня до листа. Грубо говоря, набор путей в диаграмме решений можно рассматривать как минимальный набор значений переменных, который полностью описывает функцию.

Например, вы можете нарисовать диаграмму решений, оставив ВСЕ переменные и ВСЕ пути. Вы можете видеть, что некоторые из них являются избыточными (возможно, с узла обе ссылки ведут на один и тот же узел). В этом случае мы тратим память.

Вся цель диаграмм принятия решений состоит в том, чтобы представить булеву функцию наиболее компактным и наиболее эффективным (с точки зрения операций) способом. Авторы довольны, потому что нашли более компактный способ, не знают об эффективности.