Устройство для решения задач на вероятностных графах

 

ОПИСАНИЕ ИЗОБРЕТЕН

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК

ГОСУДАРСТВЕННОЕПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4797971/24 (22) 28.0290 (46) 30.1293 Бюл. Иа 48-47 (71) Ростовское высшее военное командно-инженерное училище ракетных войск (72) Червяцов В.Н„. Евстафьев В.В. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА

ВЕРОЯТНОСТНЫХ ГРАФАХ (57) Изобретение относится к вычислительной технике и может быль использовано для исследования надежности и живучести систем, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет определена вероятности существования маршрутов с заданным уровнем эффективности Устройство содержит блок 1 синхронизации, регистрирую(1 2 SU (11) 183926З А1 (51) щий блок 2 перечисления множества маршрутов, блок 3 определения параметров маршрутов, регистрирующий блок 4 вычисления вероятности существования маршрута, регистрирующий блок 5 выбора максимума, блок 6 сравнения, вход 7 пусщ вход 8 задания порога вероятности, вход 9 задания порога эффективности, выход 10 признака принадлежности текущего маршрута множеству маршрутов с заданным уровнем эффективности и вход 11 задания вероятности существования компонент маршрута. При поступлении на вход 7 пуска устройства импульса уровня логической "1" блок 1 синхронизации формирует последовательность сигналов, под управлением которой на выходе 10 устройства формируются искомые оценки эффективности 3 ип

1839263

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

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

Недостатком устройств является то, что 1О маршрутов, при этом выходы признака прихарактеристики графов определяются без надлежности К-й вершины множеству веручета подграфов, на которые распадается шин текущего маршрута и признака исходный граф, и не определяется состоя- принадлежности(К, M)-йдугимножествудуг ние отказа системы, что снижает точность и текущего маршрута регистрирующего блока полноту анализа исследуемых систем на "5 перечисления множества маршрутов (К=1, указан н ых устройствах. 2, ..., В, M=1, 2, ..., В, где  — количество

Наиболее близким по технической сущ- вершин в графе) подключены к одноименности к изобретению является устройство ным входам блока вычисления вероятности для решения задач на графах, содержащее существования маршрута и блока определеблок синхронизации, регистрирующий блок 2О ния параметров маршрута, информационперечисления множества маршрутов, блок ный выход блока определения параметров вычисления вероятности существования маршрута подключен к информационному маршрутов и блок сравнения, причем вход входу регистрирующего блока выбора макпуска устройства подключен к входу пуска симума, второй выход блока синхронизации блока синхронизации, первый выход. кото- 25 подключен к входу опроса блока вычислерого подключен к тактовому входу регистри- ния вероятности существования маршрута, рующего блока перечисления множества выход признака превышения порога котомаршрутов, выход признака исчерпания рого подключен к тактовому входу регистрисписка маршрутов которого подключен к рующего блока выбора максимума, входу останова блока синхронизации, вхо- 30 информационный выход которого подклюды задания вероятности существования ченкпервомуинформационномувходублокомпонент маршрута устройства и задания ка сравнения, второй информационный порога вероятности устройства подключе- вход которого является входом задания поны к одноименным установочным входам рога эффективности блока сравнения, выблока вычисления вероятности существова- 35 ход признака исчерпания списка ния маршрута. маршрутов регистрирующего блока переК недостатку указанного устройства от- числения множества маршрутов подключен носится отсутствие возможности учета ве- к входу опроса блока сравнения, выход прироятностей существования элементов знака не меньше-которого является выхосистемы и их характеристик при определе- 4О дом признака принадлежности текущего нии общих характеристик системы, что не маршрута множеству с заданным уровнем позволяет моделировать отказы типа сни- эффективности. жения характеристики пути, имеющего мак- На чертеже представлена функциональсимальное ее значение ниже допустимого. ная схема устройства, Целью изобретения является расшире- 45 Устройство содержит блок 1 синхрониниефункциональныхвозможностейустрой- зации, первый выход которого соединен с ства за счет определения вероятности тактовым входом регистрирующего блока 2 существования маршрутов с заданным перечислениямножествамаршрутов. Выхоуровнем эффективности. ды признака принадлежности К-й вершины

Цель достигается тем, что в устройство, 5О множеству вершин текущего маршрута и содержащее блок синхронизации, регист- признака принадлежности (К, Н)-й дуги мнорирующий блок перечисления множества жеству дуг текущего маршрута блока 2 подмаршрутов, блок вычисления вероятности ключены к одноименным входам блока 3 существования маршрутов и блок сравне- определения параметров маршрута и блока ния, причем вход пуска устройства подклю- 55 4 вычисления вероятности существования чен к входу пуска блока синхронизации, маршрута. Выходпризнакапревышенияпопервый выход которого подключен к такто- рога блока 4 соединен с тактовым входом вому входу регистрирующего блока пере- регистрирующего блока 5 выбора максимучисления множества маршрутов, выход ма, информационный выход которого соеприэнакаисчерпанияспискамаршрутовко- динен с первым информационным входом

1839263

10

30

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

11 задания вероятности существования компонент маршрута устройства соединен с одноименным установочным входом блока 4. вход останова блока 1 и вход опроса блока 6 сравнения соединены с выходом признака исчерпания списка маршрутов блока 2.

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

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

На вход 7 пуска устройства подают импульс управления лог. "1". При этом блок 1 формирует на своих выходах последовательность сигналов. Сигнал управления лог.

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

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

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ВЕРОЯТНОСТНЫХ ГРАФАХ, содержащее блок синхронизации, блок перечисления множества маршрутов, блок вычисления вероятности существования маршрутов и блок сравнения, причем вход пуска устройства подключен к входу пуска .блока синхронизации, первый выход которого подключен к тактовому входу блока вероятностями (вероятностями существования вершин и дуг графа), Через время, достаточное для окончания указанных процессов, блок 1 формирует сигнал лог, "1" на своем втором выходе, поступающий на вход опроса блока 4. При этом если Р Ppon, где Ppon — значение вероятности, записанное с входа 8 устройства, то на выходе признака превышения порога блока 4 формируется сигнал лог, "1", разрешающий запись значений определенных блоком 3 параметров маршрута в блок 5.

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

"0" на выходе признака меньше.

При наличии сигнала лог, "1" на выходе признака исчерпания списка маршрутов блока 2 блок 1 прекращает генерацию управляющих сигналов на своих выходах, На этом работа устройства заканчивается. (56) Авторское свидетельство СССР

¹ 1660015, кл. 6 06 F 15/419, 19.01.90.

Авторское свидетельство СССР

N 11883322330077, кл. G 06 F15/419,,11.04.90. перечисления множества маршрутов, выход признака исчерпания списка маршрутов которого подключен к входу останова блока синхронизации, входы задания вероятности существования компонент маршрута устройства и задания порога вероятности устройства подключены к одноименным установочным входам блока вычисления вероятности существования маршрута, отличающееся тем, что, с целью расширения функциональных возможно1839263

Составитель В. Червяцов

Редактор Т, Юрчикова Техред М. Моргентал Корректор П. Гереши

Тираж Подписное

НПО "Поиск" Роспатента

113035, Москва, Ж-35, Раушская наб., 4/5

Заказ 3407

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 стей устройства за счет определения вероятности существования маршрутов с заданным уровнем эффективности, в него введены блок выбора максимума и блок определения параметров маршрутов, причем выходы признака принадлежности К-й вершины множеству вершин текущего маршрута и признака принадлежности (К, M)-й дуги множеству дуг текущего маршрута блока перечисления множества маршрутов (К = 1, 2, „„В, М = 1,2, ..., B, где В - количество вершин в графе) подключены к одноименным входам блока вычисления вероятности существования маршрута и блока опредегения параметров маршрута, информационный выход блока определения параметров маршрута подключен к информационному входу блока выбора максимума, второй выход блока синхронизации подключен к входу опроса блока вычисления вероятности существования

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

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