2.3.1.4. Построение всех безызбыточных покрытий
Имея все безызбыточные покрытия, можно выбрать среди них минимальные и кратчайшие покрытия.
Приведем алгоритм построения всех безызбыточных покрытий. С этой целью сопоставим строкам таблицы Квайна заглавные буквы латинского алфавита (рис. 2.2).
Алгоритм
1. Сопоставим каждому столбцу таблицы Квайна элементарную дизъюнкцию, составленную из букв латинского алфавита, отмеченных в столбце единицами.
2. Построим конъюнктивную нормальную форму (КНФ) из полученных элементарных дизъюнкций.
3. Перейдем от КНФ к ДНФ, раскрывая скобки и выполняя операцию поглощения конъюнкций.
Каждая
конъюнкция
полученной ДНФ сопоставляется некоторому
безызбыточному покрытию таблицы Квайна
и, следовательно, безызбыточной ДНФ
функции f(
,…,
).
ДНФ строится из конъюнкций, соответствующих
строкам таблицы Квайна, отмеченным
буквами в
.
Заметим, что для получения минимальных покрытий достаточно приписать конъюнкциям суммы весов строк, отмеченных входящими в конъюнкцию буквами.
Конъюнкции с минимальными суммами представляют всевозможные минимальные ДНФ функции f( ,…, ).
Конъюнкции минимальных рангов представляют всевозможные кратчайшие ДНФ функции f( ,…, ). Проиллюстрируем алгоритм поиска всех безызбыточных покрытий на таблице Квайна рис. 2.2.
Имеем следующую КНФ:
(C D E)(F G) C (D F)E A G B.
Примем во внимание, что для элементарных дизъюнкций, так же как и для элементарных конъюнкций, возможны операции поглощения на основании следующего тождества: (x y) y = y.
Выполнив всевозможные поглощения дизъюнкций, получим более простую КНФ:
C (D F) E A G B.
Далее к ней, применяя п. 3 алгоритма, строим ДНФ:
A B C D E G A B C E F G.
Находим по ее конъюнкциям все безызбыточные ДНФ булевой функции:
=
,
= .
Обе ДНФ являются кратчайшими и минимальными.
Отметим, что алгоритм поиска всех безызбыточных ДНФ булевой функции также связан с большим объемом вычислений. Он, как и алгоритм Квайна, относится к множеству алгоритмов, сложность которых экспоненциально растет с ростом числа переменных функции f( ,…, ).
На практике, имея таблицу Квайна, прибегают к более эффективным в смысле вычислительных затрат алгоритмам, позволяющим найти одно (любое) кратчайшее покрытие, не претендуя на поиск минимального покрытия. Для функций большого числа переменных часто отказываются от построения сокращенной ДНФ, ограничиваясь поиском подмножества простых импликант и поиском безызбыточных покрытий, по возможности близким к кратчайшим.
Важно отметить, что алгоритмы получения покрытий столбцов булевой матрицы ее строками применимы к любым булевым матрицам. При этом строки и столбцы булевой матрицы получают интерпретацию, соответствующую природе решаемой задачи.
Напомним, что поиск хроматического числа в графе сводится к нахождению кратчайшего покрытия столбцов строками булевой матрицы. Строки сопоставляются максимально совместимым подмножествам, а столбцы – вершинам графа.
Сведение той или иной задачи к покрытию столбцов или строк булевой матрицы часто оказывается полезным, с одной стороны, в связи с тем, что уже существуют достаточно быстродействующие алгоритмы, позволяющие находить кратчайшие покрытия для матриц приемлемых размеров, а с другой – для оценки сложности решаемой задачи.
Рассмотрим ситуацию, когда булева функция задана не таблицей, а представлена некоторой ДНФ D = … , существенно более компактной, чем совершенная ДНФ этой функции. Нельзя ли в этом случае обойтись без получения совершенной ДНФ за счет применения в обратном порядке операции простого склеивания, ведь на получение ДНФ D уже могли быть затрачены усилия, связанные с выполнением склеиваний и поглощений конъюнкций? Оказывается, можно. Такую возможность предоставляет метод Блейка.
КАДР