Например, достаточной является совокупность всех максимальных интервалов, которым принадлежит некоторый элемент а множества М1. Достаточной в текущей ситуации оказывается совокупность максимальных интервалов, которым принадлежит некоторый элемент а множества М* и которые обладают различными, не содержащимися друг в друге проекциями на множество М*. Число элементов в этих допустимых совокупностях, как правило, меньше, если у задающего их элемента а мало соседей.
Отсюда следует определенная рекомендация, направленная на сокращение перебора при поиске оптимального решения данной задачи: предварительно взвесить все элементы множества М1, определяя при этом вес элемента как число его соседей, а последующие переборы в множестве М1 организовывать в порядке неубывания этих весов.
Описанный метод порождает многочисленные приближенные методы, в которых не рассматриваются обязательно все варианты, связанные с выбором различных элементов достаточных совокупностей. Например, в каждой точке ветвления может выбираться лишь один путь, «лучший» по какому-то статистически оправдываемому критерию. Может быть упрощен и сам способ образования точек ветвления, в результате чего задача нахождения минимальной достаточной совокупности может решаться также приближенно или даже не ставиться.
16. Методы сканирования булева пространства
Описанный выше способ анализа характеристического множества М1 минимизируемой булевой функции f обладает одним существенным недостатком, связанным с необходимостью рассмотрения большого числа различных сочетаний элементов в множестве М1. Например, отыскивая в множестве М1 соседей, мы должны проверить по данному способу все пары элементов этого множества. А число таких пар для функции от n переменных можно приближенно оценить как 22n - l если f является «случайной» булевой функцией, у которой значения 0 и 1 распределены равномерно по n-мерному булеву пространству М.
Этот перебор можно значительно сократить, задавая рассматриваемую функцию f непосредственно на булевом пространстве., элементы которого упорядочены и каким-то образом пронумерованы. Если на некотором элементе пространства М функция f принимает значение 1, т. е. если этот элемент принадлежит множеству М1, то, отыскивая его соседей в множестве М1, не обязательно перебирать все элементы этого множества (их число равно в среднем 2n-1) и сравнивать их с данным, а достаточно просмотреть лишь соседние элементы булева пространства М (а их число равно n) и выбрать из них те, на которых функция f также принимает значение 1. Таким образом, сплошной перебор элементов в характеристическом множестве М1 заменяется упорядоченным выбором и анализом элементов в булевом пространстве М. Назовем этот последний способ сканированием булева пространства. Он позволяет сократить число перебираемых элементов примерно в 50 раз при n =10 и в 1000 раз при n =15.
Но для этого надо уметь быстро находить любые заданные элементы булева пространства, а также соседние с ними элементы. Рассмотрим, как это делается в следующих двух методах, опирающихся на те же понятия и принципы, что и изложенные выше методы, но отличающиеся от них механизмом перебора элементов в пространстве М. Между собой эти методы различаются ориентацией на технику вычислений: один из них ориентирован на машинную реализацию, другой — на ручную.
Метод минимального соседства. Так мы назовем метод минимизации ДНФ булевой функции, основанный на выборе в множестве М1 элементов в порядке возрастания числа их соседей.
Минимизируемая булева функция f представляется при этом непосредственно в табличной форме, где в левом столбце перечислены все элементы булева пространства М — наборы значений аргументов, упорядоченные в соответствии с позиционным двоичным кодом натуральных чисел,— а справа значения на наборах функцией f.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.