Матрица простых совокупностей. Оптимальная реализация слабо определенных булевых функций, страница 8

Если в матрице С_i существует столбец, содержащий лишь одну единицу, то это означает, что соответствующий интервал может быть использован для покрытия только одного из элементов непокрытого остатка. Интервал соответственно расширяется и включается в окончательное решение.

Наконец, если текущая ситуация такова, что ни одно из перечисленных условий не выполняется, то производится следующий выбор, который в большинстве случаев оправдывается, но может оказаться не наилучшим, что и приводит к тому, что описываемый алгоритм является лишь приближенным, ire гарантируя оптимальности получаемого окончательного решения. В частичном решении отыскивается некоторый минимальный по числу элементов интервал, а затем среди совместимых с ней элементов непокрытого остатка выбирается ближайший к нему. Расстояние измеряется при этом по Хэммингу. числом компонент, по которым элемент и интервал ортогональны. Такой выбор оправдывается статистически, так как при нем покрытие нового элемента обеспечивается минимальным расширением интервала, что сохраняет больше возможностей для последующих преобразований частичного решения.

Выполнение описанных операций преобразования частичного решения сопровождается удалением покрытых элементов из M_i^* и соответствующей корректировкой матрицы совместимости: Ci преобразуется в С_i+1. В исходной ситуации частичное решение оказывается пустым, а непокрытый остаток совпадает с множеством М¹: Vо = Æ и M₀* = М¹. Процесс конструирования решения завершается, когда пустым оказывается множество М_i^*, в этом случае частичное решение V_i принимается за окончательное.

Пример. Применим данный метод к минимизации рассмотренной перед этим булевой функции.

На первом шаге образуем первый элемент частичного решения — интервал, состоящий из единственного элемента множества М¹, а именно первого из перечисленных в матрице U_i. Этот интервал (назовем его а) оказывается несовместимым со вторым элементом множества М¹, который образует в связи с этим второй элемент частичного решения — интервал Ь. В возникающей при этом ситуации частичное решение V₂ будет иметь значение

а непокрытый остаток M₂^* —