Задачи диагностики. Отображение интервалов. Задача диагностики для b-схемы

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

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

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

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

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

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

Назовем первый из описанных критериев критерием А, второй — критерием Б и применим данный алгоритм к матрице Р, которую надо разбить на как можно меньшее число таких строчных миноров, чтобы каждый из них имел единицы не более чем в пяти столбцах.

Согласно изложенному алгоритму конструирование первого минора начинается с включения в него строки 4, первой из оптимальных по критерию Б. Следующим допустимым приращением минора может служить любая из строк 5, 7, 11, 12 и 15, для которых критерий А принимает соответственно значения 1, 2, 2, 2 и 2 (например, для строк 4 и 5 находится лишь один столбец i, в котором обе строки имеют значение 1, а для строк 4 и 7 таких столбцов два: с и i). Анализируя более глубоко варианты выбора среди конкурирующих строк 7, 11, 12 и 15, мы бракуем строки 7 и 12, поскольку выбор любой из них приводит к тому, что множество последующих допустимых приращений сокращается до нуля. Выбирается строка 11, а затем единственная допустимая строка 15. Так в результате прохождения первого этапа определяется первый класс строк {4, 11, 15}.

Аналогично находятся классы {14, 6, 9}, {1, 3}, {2, 13, 5, 7,12}, {8,16} и {10}. Полученному разбиению заданного множества функций на шесть классов соответствует выделение из общего множества всех аргументов шести подмножеств, с мощностью каждого не более пяти. Это решение можно представить         булевой матрицей

справа которой показаны соответствующие строкам классы.

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

                 10. Задачи диагностики