Модель ветви графа Советский патент 1983 года по МПК G06F15/173 

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

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

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

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

Поставленная цель достигается

5 тем, что в устройство введены третий триггер, седьмой и восьмой элементы И и элемент ИЛИ, при этом единичный вход третьего триггера является запрещающим входом модеQ ли веТви, единичный выход третьего триггера соединен с первым входом седьмого элемента И, второй вход которого соединен с- выходом сдвигового регистра, а выход является фикс сирующим выходом модели ветви, первый вход восьмого элемента Иявляется разрешающим входом модели ветви,: второй вход, восьмого элемента И является вспомогательным входом модели ветви, выход восьмого элемента И соединен с первым входом элемейта ИЛИ, рторой вход которого является входом задания вероятности модели ветви, выход элемента ИЛК соединен со входом сдвигового регист5 ра а третий вход шестого элемента И является корректирующим входом модели ветви.

На чертеже представлена предложенная Структурная схема модели

0 ветви. - в

Модель ветви содержит элементы, И 1-8, счетчик начального адреса 5, счетчик конечного адреса 10, тригге ЕЫ 11 - 13, формирователь временного

5 интервала 14, сдвиговый регистр 15,.. инвертор 16 и элемент ИЛИ 17.

Работу модели ветви рассмотрим с момента, когда сформирован 1-тый узел графа с вероятностным выходом. Допустим, из 1-того узла выходят че Тыре ветви с вероятностями реализации R, Р 0,2/ Р 0,1,-; § 0,5.

Емкость регистра и реализуется альтернативный выбор одной из исходящих ветвей. Способ занесения

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

Допустим, что в процессе модели рования модел1 руется древовидный граф развивающегося процесса и. на этой модели осуществляется ве- , роятностный выбор наиболее достоверных гипотез. В таком случае пёрвонзчальйо априорная информация о вероятностях переходов, соответствующая вероятностям ветвей, исходящих из. Г-тогоузла, заносится в регистроа и процесс моделирования происходит с реализацией альтернативного выбора ветвей аналогично тому, как это осуществляется в ClJ. Указанный процесс моделиров ния для выявления наиболее достоверных гипотез требует многократного моделирс вания возможных путей графа с исключением гипотез, а значит и путей графа, не удовлетворяющих условиям соответствия ис-ходным данным задачи. При этом исключение путей графа сводится к исклчению некоторых ветвей, исходящих из некоторых узлов. Поскольку первоначально эти исключаемые впоследсвии ветви реализовали некоторое заданное значение вероятности. То после их исключения это значение вероятности необходимо перераспределить между остальными ветвями, исходящими из данного узла равномерно, сохранив случайный выбор неисключенных ветвей и обязательный выбор одной из них. Анализ получае{Ф1Х в . процессе моделирования гипотез на соответствие исходным данным задачи может выполнять специальное контролирующее устройство, входящее в .состав блока управления. В его функции входит выявление ветвей графа, которые необходимо исключить на кг1ждом этапе моделирования, и выдача (в -момент ожидаемого прихода первого сдвигового импульса случайной серии г сигнала запрета на запрещакяций вход каждой модели вет. ви, которая должна быть исключена из процесса моделирования. Допустим что сигналы запрета в указанный вьаие момент поступили- на запрещающие входы второй и третьей моделей ветви. Тогда, поскольку число сдвиговых импульсов случайно, могут иметь место след тощие ситуации. После окончания случайной серии импульсов (), поступающих на вероятностный вход и через элемент ИЛИ 17 на вход сдвигового регистра 15

каждой модели ветви, единичный

сигнал окажется на выходе регистра 15 первой или четвертой ветви, что допустимо, либо на выходе второй или третьей ветви, что недопустимо, так как эти ветви должны быть ис ключены из процесса Моделирования на данном этапе. Исключение запрещенных ветвей в предложеннсяч устройстве обеспечивается за счет дополнительных сдвиговых импульсов г пода.ваемых на вход сдви -ового регистра 15 каждой модели ветви, начиная с момомент, отстоящего от момента завершения формирования 1-того уэла на время, большее длительности N периодов импульсов случайной серии. Количество дополнительных сдвиговых импульсов равно.1,2,...,К«( N-1), гк& К - количество единиц, появлящихся ПОДР51Д .при дополнительных

сдвигах на выходах регистров 15

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

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

двиговых импульсов равно нулю и

лучайный выбор одной из ветвей граа считается завершенным.

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

Так, если в приведенном в таблице примере сдвиги в регистрах,15 моделей ветви осуществляются в сторону старших разрядов регистров, на чальные состояния регистров 15 в момент завершения формирования i-то узла соответствуют заданным таблице а число случайных сдвиговых импульсов равно пяти, то после поступлени 5-го случайного импульса на выходе регистра 15 третьей модели ветви (исключаемой из процесса) появится единичный сигнал, который поступит на второй вход элемента И 7. В момент ожидаемого лрихода 1-го случайного сдвигового импульса на запре1цаю1ций .вход каждой, исключаемой из процесса,модели ветви (в данном случае второй и третьей моделей ветви) пос тупит сигнал запрета.. Допустим, что в момент завершени формирования 1-го узла с вероятност ным выходом триггеры 13 всех моделей ветви находятся в состоянии О Тогда сигнал запрета в момент ожидаемого прихода i-ro случайного сдв гового импульса, воздействуя на еди ничный вход триггера 13 в каждой из исключаемых моделей ветви, изменит состояние этого триггера и на его единичном выходе появится сигнал ра решения , который поступит на первый вход элемента И 7. Этот сигнал разрешения пройдет на выход упомянутого элемента только в той, исключавмой из процесса, модели ветви (s данном случае третьей), на выходе |регистра 15 которой имеется единичный сигнал, и появится на фиксирующем выходе указанной модели ветви. При этом из блока управления на разрешающие входы всех моделей ветви поступает сигнал разрешения, а от генератора импульсов на вспомога тельные входы всех моделей ветви приходит первый импульс дополнитель ной серии, содержащей N-1 импульс. При наличии сигнала разрешения на разрешающих входах моделей ветви первый импульс дополнительной серии через элемент И 8 и элемент ИЛИ 17 Проходит на вход сдвигового регистр 15 каждой Модели ветви. В результат этого информация, находящаяся в регистрах 15 всех моделей ветви, сдвинется вправо на один разрядi Вследствие этого единичный сигна появится на выходе регистра 15 второй модели ветви, которая также должна быть исключена из процесса моделирования. Этот сигнал, воздействуя на второй вход элемента И 7/ второй модели ветви. по аналогии с предыдущим обеспечит прохождение сначала второго, а затем и третьего импульса дополнительной серии на вход сдвигового регистра 15 всех моделей ветви. В результате произой дет сдвиг;информации, находящейся в регистрах 15 всех моделей ветви, еще на два разряда вправо и единичный сигнал окажется на выходе регистра 15 первой модели ветви. Поскольку эта модель ветви не исключается из процесса моделирования, ни один, из оставшихся (N-K-1) (в данном случае шести) импульсов дополнительной серии Не пройдет,на вход регистра 15 каждой модели ветви на этапе формирования l+l-ro узла. В общем случае в момент окончания (N-l)-ro импульса допрлнительной серии единичный сигнал будет гарантирован на выходе регистра 15 только одной из неисключенных из процесса моделей ветви, чем и будет обеспечен альтернативный выбор данной, ветви. При этом реализованное значение вероятности выбранной веТви окажется выше, чем ее первоначальное значение (в рассмотренном примере реализованное значение Р 2/7у. Соответственно возрастут и вероятности реализации других ветвей , не исключенных из процесса моделирования в. рассмотренном примере Р 5/1 t а вероятности реализации исключенных ветвей будут равны нулю. Сумма же вероятностей реализации всех неисключенных ветвей составит единицу, что и соответствует новой полной группе событий. . Поскольку число сдвиговых импульсов случайно и при наличии дополнительных сдвиговых импульсов, появление в указанный выше момент единичного сигнала на выходе регистра 15 J-той, неисключенной из процесса, модели ветви является случайным событием., . После (окончания (N-l)-ro импульса дополнительной серии на корректирующий вход каждой модели ветви из б.ло ка управления поступает сигнал готовности, представляющий собой единичный импульс (например N-ый импульс, исключенный из дополнительной серии), который разрешает зафиксировать завершенный случайный выбор участвующих в процессе моделирования ветвей j: учетом дополнительной задержки на время, равное 2N периодов импульсов случайной (дополнительной ) серии (при Тцд,-), Исходные состояния элементов схемы каждой модели ветви, обеспе- ; чивающих фи1 сацию альтернативного выбора, с момента завершения формирования i-Toro узла и до прихода сигнала готовности не изменяются и соответствуют исходным состоянием тех же элементов модели ветви.прототипа, но в момент окончания формирования i-Toro узла. Таким образом, предложенная модель ветви графа может быть исполь710122688

зована для моделирования графов сходящих из узлов с вер оятнос гиь 1и

переменной вероятностной топологиейвыхояамя, когда часть-из этих вети перераспределе1}ием первоначальныхвей на данном этапе моделирования

j значений вероятностей ветвей, ис-должна быть исключена из процесса.

Г .. - - - - - .

МОДЕЛЬ ВЕТВИ ГРАФА по авт. св. 583439 f о т ли чающая-с я тем, что, с целькз расширения класса решаемых задач путеммоделирования графов с переменной вероятностной топологией, в нее введены третий триггер, седьмой и восьмой элементы и и элемент ИЛИ, при этом единичный вход третьего триггера является запрещающим входом модели ветви, единичный выход третьего триггера соединен с первьм входом седьмого элемента И, второй вход которого соединен с выходом сдвигового регистра, а выход является фиксирующим выходом модели ветви, первый вход восьмого элемента И.является разрешгиснцим входом модели ветви, второй вход восьмого элемента И является вспомогательным входом модели ветви, выход восьмого элемента И соединен с первым входсм элемента ИЛИ, второй вход которого является входом вероятности модели ветви, выход элемента ИЛИ соединен со входом сдвигового регистра, а третий вход шестого элемента И является корректкрукщтл входом модели ветви.