Сжатие булевой матрицы. Методы сканирования булева пространства, страница 2

Пусть некоторый элемент а текущего множества М* принадлежит сразу нескольким максимальным интервалам множества М¹. Рассмотрим пересечения этих интервалов с множеством М*, называя их далее проекциями интервалов на множество М*. Если среди этих проекций найдется такая, которая содержит остальные в качестве своих подмножеств, то можно считать обоснованным выбор любого соответствующего ей максимального интервала (их может оказаться несколько) как очередного элемента конструируемого кратчайшего покрытия. Очевидно, что этот интервал обеспечивает покрытие всех элементов из М*, которые только можно покрыть интервалами множества М¹, покрывающими одновременно элемент а. Назовем такой интервал допустимым, обратив внимание читателя на относительный характер этого определения: интервал может оказаться допустимым лишь при данной последовательности предшествующих выборов элементов покрытия. Упомянутый элемент а будет называться в этом случае, как и прежде, определяющим.

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

Будем говорить, что некоторые два элемента множества М¹ совместимы, если поглощающий их минимальный интервал содержится в множестве М¹. Элемент а оказывается определяющим, если минимальный поглощающий интервал для всех элементов множества М*, совместимых с элементом а, содержится в множестве M¹. Описываемый метод реализует проверку этого отношения.

Перебор в множестве M*, производимый при поиске совместимых с а элементов, ускоряется тем, что он ограничивается рассмотрением элементов, принадлежащих минимальному поглощающему интервалу для всех соседей элемента а — очевидно, что совместимые с а элементы могут находиться только в этом интервале. Оба минимальных поглощающих интервала как для соседей элемента а, так и для совместимых с ним элементов строятся легко. Наконец, изложенным выше способом устанавливается, содержится ли последний из этих интервалов в множестве М¹. При получении положительного ответа на этот вопрос доказывается тем самым, что элемент а является определяющим. Допустимым в этом случае оказывается любой максимальный интервал множества M¹, содержащий найденный минимальный поглощающий интервал для совместимых с а элементов. В частности, эти два интервала могут совпасть.

Обратим внимание читателя на существенное отличие промежуточных ситуаций от начальной, заключающееся в том, что в начальной ситуации от определяющего элемента а требуется, чтобы в множестве М¹ содержался минимальный поглощающий интервал для всех совместимых с а элементов множества М¹, в то время как в текущей ситуации это требование ослаблено: там рассматривается минимальный поглощающий интервал только для тех совместимых с а элементов, которые принадлежат текущему множеству М*.

Это отличие и определяет цепной характер процесса конструирования кратчайшего интервального покрытия множества М¹. Включение в покрытие очередного допустимого интервала сопровождается соответствующим со

кращением множества М*, а это в свою очередь может привести к тому, что некоторые из остающихся в множестве М* элементов могут стать определяющими, что позволит включить в решение новые допустимые интервалы, далее сократить текущее множество М*  и т. д.

Пример. Продемонстрируем описанный процесс на конкретном примере, рассмотрев характеристическое множество М¹, заданное булевой матрицей В.

Будем анализировать подряд элементы этого множества, начав с элемента

000101   1.

Этот элемент имеет трех соседей

000001   2,

010101   10,

100101   20,

минимальный поглощающий интервал для которых

                                           - - 0 - 0 1

не содержится в множестве М¹ (например, там отсутствует элемент

110101, принадлежащий данному интервалу). Следовательно, элемент 1 не является определяющим.

Такой же результат мы получаем и для следующих элементов, пока не остановимся на элементе