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

(для удобства мы сохраняем нумерацию элементов множества М¹). Матрица С₂ отношения совместимости будет иметь соответственно следующий вид:

Ситуация оказывается критической, поскольку в ней не выполняются условия, определяющие выбор «беспроигрышного» шага. Поэтому, следуя сформулированным для таких ситуаций правилам, мы фиксируем внимание на интервале а (он равен по размеру интервалу Ь, но оказывается первым в перечне) и измеряем расстояние от него до совместимых с ним элементов 4, 5, 6, 8, 9 и 10. Они оказываются равными соответственно 4, 6, 5, 5, 5 и 6. Выбираем ближний элемент 4 и соответственно расширяем интервал а, чтобы он поглотил этот элемент, т. е. находим для них минимальный поглощающий интервал, который будет принят в качестве нового значения растущего интервала а.

В возникающей при этом повой ситуации частичное решение будет иметь значение

V₃ =

из непокрытого остатка будет удален элемент 4, а матрица. совместимости окажется преобразованной к следующему виду:

С₃ =

Обратим внимание читателя на то, что после выполненного расширения интервал а стал несовместим с элементами 5, 9 и 10 множества М¹, с которыми он был раньше совместим. Например, минимальный поглощающий интервал

- - - - - 0 - - - 0 -

для интервала а и элемента 5 пересекается с множеством М°, так как они обладают общим элементом

01100011000.

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

10100010100 c.

Снова возникает критическая ситуация. Выбирается интервал b и отыскивается ближайший к нему элемент из непокрытого остатка. Им оказывается элемент 6, расстояние до которого равно 4. Интервал Ь соответственно расширяется, после чего наступает ситуация, в которой частичное решение принимает значение

V₅=

непокрытый остаток — значение

M₅^{* =}