множеств оказывается довольно большим, все же можно получить их все и решить далее задачу о кратчайшем покрытии, достроив предварительно соответствующую булеву .матрицу.
Однако с увеличением числа строк в матрице Р реализация данного метода очень скоро становится практически невозможной или по крайней мере нецелесообразной. В связи с этим рассмотрим приближенный метод решения данной задачи.
Самыми быстродействующими являются цепные алгоритмы, без возвратных движений по дереву поиска. Их реализация разбивается на этапы, и на каждом из этих этапов выбирается лишь один вариант его прохождения, причем оптимальность его условна и определяется некоторым эвристическим критерием, составляющим суть метода. Для решения рассматриваемой задачи мы используем двухступенчатое разбиение решающего процесса на этапы, при котором каждое звено цепного алгоритма будет реализовываться в свою очередь своей цепью, состоящей из более мелких звеньев.
Пусть результатом прохождения крупного этапа является включение в решение некоторого класса функций с общим числом аргументов, не превышающим 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. Задачи диагностики
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
