Устройство для решения задач на вероятностных графах Советский патент 1993 года по МПК G06F15/419 

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

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

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

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

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

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

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

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

0 маршрутов, при этом выходы признака принадлежности К-й вершины множеству вершин текущего маршрута и признака принадлежности (К, М)-й дуги множеству дуг текущего маршрута регистрирующего блока

5 перечисления множества маршрутов (, 2, ..., В, , 2, ..., В, где В - количество вершин в графе) подключены к одноименным входам блока вычисления вероятности существования маршрута и блока определе0 ния параметров маршрута, информационный выход блока определения параметров маршрута подключен к информационному входу регистрирующего блока выбора максимума, второй выход блока синхронизации

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

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

На чертеже представлена функциональная схема устройства.

5 Устройство содержит блок 1 синхронизации, первый выход которого соединен с тактовым входом регистрирующего блока 2 перечисления множества маршрутов. Выходы признака принадлежности К-й вершины

0 множеству вершин текущего маршрута и признака принадлежности (К, Н)-й дуги множеству дуг текущего маршрута блока 2 подключены к одноименным входам блока 3 определения параметров маршрута и блока

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

блока 6 сравнения. Вход 7 пуска устройства соединен с входом пуска блока 1, второй выход которого соединен с входом опроса блока 4, установочный вход задания порога вероятности которого подключен к одно- именному входу 8 устройства. Вход 9 задания порога эффективности устройства подключен к второму информационному входу (входу задания порога эффективности) блока 6 сравнения, выход признака не меньше которого соединен с выходом 10 признака принадлежности текущего маршрута множеству маршрутов с заданным уровнем эффективности устройства. Вход 11 задания вероятности существования компонент маршрута устройства соединен с одноименным установочным входом блока 4. вход останова блока 1 и вход опроса блока 6 сравнения соединены с выходом признака исчерпания списка маршрутов блока 2.

Устройство работает следующим образом.

Перед началом работы в блоке 2 определяются полюса сети, отображаемой исс- ледуемым графом, в блоке 3 устанавливаются конкретные значения характеристик элементов графа. Также перед началом работы подается информация на входы 8/9, 11 устройства, которая записы- вается в соответствующие блоки.

На вход 7 пуска устройства подают импульс управления лог. 1. При этом блок 1 формирует на своих выходах последовательность сигналов. Сигнал управления лог. 1 с его первого выхода поступает на тактовый вход блока 2, который формирует на своих выходах набор потенциалов управления лог. 1 (принадлежность элемента графа текущему маршруту) и лог. О (отсутствие элемента графа в текущем маршруте), поступающих на соответствующие входы блоков 4 и 3. Блок 4 определяет вероятность существования текущего маршрута (Р) как вероятность сложного события в про- странстве простых событий с известными

вероятностями (вероятностями существования вершин и дуг графа).

Через время, достаточное для окончания указанных процессов, блок 1 формирует сигнал лог, 1 на своем втором выходе, поступающий на вход опроса блока 4. При этом если Р Рдоп, где РДОп - значение вероятности, записанное с входа 8 устройства, то на выходе признака превышения порога блока 4 формируется сигнал лог. 1, разрешающий запись значений определенных блоком 3 параметров маршрута в блок 5.

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

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

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

(56) Авторское свидетельство СССР iSh 1660015, кл. G 06 F 15/419, 19.01.90.

Авторское свидетельство СССР № 1832307, кл. G06F 15/419, 11.04.90.

Формула изобретения

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ВЕРОЯТНОСТНЫХ ГРАФАХ, содержащее блок синхронизации, блок перечисления множества маршрутов, блок вычисления вероятности существования маршрутов и блок сравнения, причем вход пуска устройства подключен к входу пуска .блока синхронизации, первый выход которого подключен к тактовому входу блока

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

стей устройства за счет определения веро- максимума/второй выход блока синхрони- ятности существования маршрутов с : зации подключен к входу опроса блока вы- заданным уровнем эффективности, в него | числения вероятности существования введены блок выбора максимума и блок маршрута, выход признака превышения определения параметров маршрутов, при- порога которого подключен к тактовому чем выходы признака принадлежности К-й входу блока выбора максимума, информа- вершины множеству вершин текущего мар- ционный выход которого подключен к пер- шрута и признака принадлежности (К, М)-й вому информационному входу блока дуги множеству дуг текущего маршрута 1П сравнения, второй информационный вход блока перечисления множества маршрутов которого является входом задания порога (К 1,2,.,,, В, М 1,2, .... В, где В - количе- эффективности блока сравнения, выход ство вершин в графе) подключены к одно- признака исчерпания списка маршрутов именным входам блока вычисления блока перечисления множества маршрутов вероятности существования маршрута и -J5 подключен к входу опроса блока сравне- блока определения параметров маршрута, ния, выход признака не меньше которого информационный выход блока on ре дел е- является выходом признака принадлежно- ния параметров маршрута подключен к йн- сти текущего маршрута множеству марш- формационному входу блока выбора рутов с заданным уровнем эффективности.

20