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

011010   5, который оказывается определяющим. Действительно, соседними с ним являются элементы

011110    4,

010010    9,

111010   17,

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

                                           - 1 - - 1 0

полностью содержится в множестве М¹. В этом можно убедиться, найдя в множестве М¹ элемент                            110110   14, ортогональный элементу 5 по компонентам 1, 3 и 4, вместе с его соседями по этим компонентам

010110     8,

111110    16,

110010    15.

Исключив из текущего множества М* (равного вначале множеству М¹) перечисленные восемь элементов интервала - 1 - - 10, принимаемого в качестве первого элемента кратчайшего покрытия множества М¹, продолжим перебор в множестве М*.

Следующим определяющим оказывается элемент

110100   13.

У этого элемента три соседа

110000   12,

110110   14,

100100   19,

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

                                         1 - 0 - - 0,

содержащий четыре элемента из множества М*:

110000   12,

110100   13,

100000   18,

100100   19.

Каждый из них совместим с элементом 13 и минимальный поглощающий интервал для них

1 - 0 – 00

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

Интервал 1 - 0 - 00 оказывается максимальным ипринимается в качестве второго элемента решения, а текущее множество М* сокращается еще на четыре элемента, приводясь к следующему виду:

Следующий в порядке перебора элемент 20 также оказывается определяющим, и в решение включается соответствующий ему допустимый интервал

- 00 - 01, образуемый элементами 1, 2, 20 и 21, исключаемыми в связи с этим из текущего множества М*.

Затем перебор идет на второй круг, и последовательно находятся определяющие элементы 3,7,10, соответствующие которым допустимые интервалы

0 1 1 1 0 0 1 0 0 0 0 - 0 - 0 1

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

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

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

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

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