Бинарный граф решений: различия между версиями

Перейти к навигации Перейти к поиску
Строка 32: Строка 32:
<math>f(x_1, ... , x_n) = x_i \cdot f_{xi} + x'_i f_{x'i}</math>
<math>f(x_1, ... , x_n) = x_i \cdot f_{xi} + x'_i f_{x'i}</math>


Это наблюдение можно использовать для представления f в виде дерева Шеннона – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании.
Это наблюдение можно использовать для представления f в виде <math>дерево Шеннона|дерева Шеннона</math> – полного бинарного дерева [6, приложение B.5] высоты n, в котором каждый путь в вершину-лист определяет полное присваивание n переменным, над которыми определена функция f; а вершина-лист содержит значение 0 или 1 в зависимости от значения, которое f принимает при присваивании.
Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}<math>^n</math>, равна n, так что дерево имеет 2n листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона.
 
Дерево Шеннона нельзя назвать достаточно удобным представлением, поскольку высота дерева, представляющего любую булеву функцию на {0,1}<math>^n</math>, равна n, так что дерево имеет <math>2^n</math> листьев. Дерево Шеннона можно уменьшить при помощи слияния изоморфных поддеревьев и пренебрежения вершинами, имеющими идентичных потомков. На первый взгляд, использование сокращенного дерева Шеннона тоже не особенно практично, поскольку оно включает создание на первом этапе полного бинарного дерева. Более того, пока неясно, как можно на сокращенном дереве Шеннона эффективно производить такие операции, как проверка эквивалентности или вычисление конъюнкции функций, представленных в виде сокращенных деревьев Шеннона.
 
Брайант [5] пришел к выводу, что накладывание ограничения, согласно которому переменные появляются в фиксированном порядке от корня к листьям, значительно снижает сложность обработки сокращенных деревьев Шеннона. Это представление он назвал бинарной диаграммой решений (БДР).
Брайант [5] пришел к выводу, что накладывание ограничения, согласно которому переменные появляются в фиксированном порядке от корня к листьям, значительно снижает сложность обработки сокращенных деревьев Шеннона. Это представление он назвал бинарной диаграммой решений (БДР).


Источник — http://pco.iis.nsk.su/wega/index.php/Бинарный_граф_решений