Выбор очередности выполнения проверок для поиска места отказа по эвристическому алгоритму

Очередность выполнения проверок влияет на среднее число проверок для поиска места отказа по условному алгоритму диагностирования.

Если отказы, учитываемые диагностической моделью, образуют полную группу несовместных случайных событий и алгоритм диагностирования применяется многократно, то среднее число проверок для поиска места отказа вычисляется по формуле

где р. — вероятность отказа е. е Е°;

т{ — число проверок, выполняемых для определения места отказа;

п — число отказов.

Таблицу связей двудольного орграфа допустимо рассматривать как форму задания префиксного кода с избыточностью кодирования, определяемой по формуле (10.34), и выбирать очередность выполнения проверок, основываясь на методе минимизации избыточности кодирования Хаффмена.

Если для поиска места отказа выбрано минимальное число проверок, то таблица связей содержит п1 отказов (строк) Е., которые отличаются только значениями проверки ик, и п2 отказов Е., отличающихся только значениями проверки uq.

Усечение таблицы связей исключением значений проверки ик из всех строк, кроме соответствующих отказам Е., не нарушает условия (8.5) и приводит к снижению избыточности кодирования I до 1к. Аналогично, исключение значений проверки uq из всех строк, кроме Е., приводит к уменьшению избыточности кодирования до lq. Выбор проверки для усечения таблицы связей основывается на следующей теореме:

Действительно, каждая строка исходной таблицы связей содержит т результатов проверок. После усечения таблицы связей число результатов проверок в строке уменьшается до т-1. Тогда исходя из формулы (10.35) получаем

что и требовалось доказать.

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

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

где е — общая часть строк.

Строки es, et редуцируются (объединяются), т. е. заменяются строкой est, которой сопоставляется вероятность

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

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

Отказы, отличающиеся значениями проверки, определяются сравнением попарно строк таблицы связей. В исходной таблице связей четыре пары отказов, в которых отказы различаются значениями одной из проверок. Для усечения таблицы связей выбрана проверка и5, поскольку суммарная вероятность отказов е4, е6 наименьшая. Редуцируемые строки показаны стрелками. Значения проверки и , которыми отличаются отказы е4, е6 указаны в соответствующих строках над стрелками.

На втором этапе выбрана проверка и2, значениями которой различаются отказы е2, е4 наименьшей суммарной вероятностью.

На третьем этапе выбрана проверка и6, превосходящая по затратам проверку и3.

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

От значения проверки, выбранной на последнем этапе, до значения проверки, выбранной на первом этапе, имеется

— Пример оптимизации очередности выполнения

Рисунок 10.2 — Пример оптимизации очередности выполнения

проверок

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

Очередность выполнения проверок при поиске места отказа задается схемой (графом) условного алгоритма диагностирования на рисунке 10.2, в. Среднее число выполняемых проверок при поиске места отказа составляет приблизительно 2,8.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >