Модель ветви графа

 

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

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

09} (В

Э(59 6 06 8 15 20:

Г ОСУДАРСТВЕННЫЙ НОМИТЕТ СССР.

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ -8CC4% а"=.= " ю-ч к авторское свидкткльствь (61) 583439 (21) .3356485/18-24 (22) 11.11.81 (46). 15.04.83. Бюл. Р 14 (72) И.К.. Влазнев,.А.Г.,Цодонов. и A.È. Щетинин (71) Институт проблем моделирования в энергетике AH украинской. ССр (53) 681;333(088.8) (56 ) 1. Авторское свидетельство СССР

9583439.,кл.О 06 Fã 15/20,1977(прототип) (54)(57.) ИОДЕЛЬ ВЕТВИ ГРАФА по авт. св. Р 583439, о т л и ч а ю щ а я-с я тем, что, с .целью расширениякласса решаемых задач путем моделиро-. вания графов с переменной вероятностной топологией, в .нее введены третий -триггер, седьмой и восьмой элементы И и элемент ИЛИ, при этом единичный вход третьего триггера является запрещающим входом модели ветви, единичный выход третьего - триггера соединен с первым входом седьмогО элемента .И, второй вход ко торого соединен с выходом сдвигово- . го регистра, а выход является фиксирующим выходом модели ветви,.первый вход восьмого элемента И является разрешающим входом модели ветви, второй вход восьмого элемента И является вспомогательным входом модели ветви, выход восьмого элемента И соединен с первым входом элемента ИЛИ, второй вход которого является входом задания вероятности модели ветви, выход элемента ИЛИ соединен со входом сдвигового pe- I гистра, а третий вход шестого элемента Й является корректирующим входом модели ветви.

1012268

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

По основному авт. св. 9 583439,,известна модель ветви графа, со"держащая первый и второй триггеры, формирователь временного интервала, счетчики начального и конечного адресов, сдвиговый регистр, шесть элементов И и ийвертор, причем первый 10 вход первого элемента И соединен с выходом формирователя. временного интервала, первый вход которого соединен с выходом второго элемента И, первый вход которого соединен с вы- 15 ходом счетчика начального адреса, выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов И, второй вход третьего элемента И соединен со вторым входом второго элемента И, третий вход которого соединен с выходом первого триггера, вход счетчика начального адреса соединен со входом модели, вход второго триггера соединен с выходом первого элемента И, второй вход которого И пер-" вый вход пятого элемента И соединены с выходом первого триггера, второй вход пятого элемента И соединены с выходом второго триггера и со вторым входом четвертого элемента И, вторые входы формирователя временного интервала и третьего элемента И соединены с соответствующими входами модели ветви, выходы которой сое- З5 динены с выходами .четвертого и пятого элементов И, вход счетчика конечного адреса соединен с входом счетчика начального адреса, вход сдвигбвого регистра соединен .с до- 4Р полнительным входом модели ветви графа, а его выход через инвертор подключен к первому входу шестого элемента И, второй вход которого соединен с выходом второго элемента 45

И, а в ход — с дополнительным единичным входом первого триггера g1).

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

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

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

И является всПомогательным входом модели ветви, выход восьмогб элемента И соединен с первым входом элемен- та ИЛИ, второй вход которого является входом задания вероятности модели ветви, выход элемента ИЛИ соединен со входом сдвигового регистра, а третий вход шестого элемента

И является корректируюцим входом модели ветви.

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

Модель ветви содержит элементы;И

1 - 8, счетчик начального адреса 9, счетчик конечного адреса 10, тригге" ры 11 - 13, формирователь временного интервала 14, сдвиговый регистр 15, инвертор 16 и элемент ИЛИ 17.

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

Емкость регистра N=10 и реализуется альтернативный выбор одной из исходяцих ветвей. Способ занесения информации о вероятностях в разряды сдвиговых регистров аналогичен описанному в 1 .и приведен в таблице (в ней обозначены ветви графа, которые на данном этапе моделирования должны быть исключены из zipoцесиса)..

1012268

Ветвь

Разряды регистров

° 1 10

6 7 8

1 0

0

0 0

0 1

1 0

0 0

0 0 0

0 °

0 1

0 ° О. 1

60 единичный сигнал окажется на выхо«

Допустим, что в процессе модели-. рования моделируется древовидный граф развивающегося процесса и на этой модели осуществляется вероятностный выбор наиболее достоверных гипотез. В таком случае первоначально априорная информация о вероятностях переходов, соответствующая вероятностям ветвей, исходящих из. i-того узла, заносится в регистры и процесс моде- . лирования происходит с реализацией альтернативного выбора ветвей аналогично тому., как это осуществляется в 11. Указанный процесс моделирования для выявления наиболее достоверных гипотез требует многократного моделирования возможных путей графа с исключением гипотез, а значит и путей графа, не удовлетворяющих условиям соответствия ис-ходным данным задачи. При этом иск лючение путей графа сводится к исключению некоторых ветвей, исходящих из некоторых .узлов. Поскольку пер- воначально эти исключаемые впоследст.вии ветви реализовали некоторое заданное значение вероятности, то после их исключения это значение seроятности необходимо перераспределить между остальными ветвями, исходящими из данного узла равномерно, сохранив случайный выбор неисключениых ветвей и обязательный выбор одной из них. Анализ получаемых в . процессе моделирования гипотез на. соответствие исходным данным задачи может выполнять специальное контро".:

:лирующее устройство, входящее в

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

После окончания случайной серии импульсов (й ® 10), поступающих на вероятностный вход и через элемент ИЛИ

17 на вход сдвигового регистра 15 каждой модели ветви, единичный сигнал окажется на выходе регистра

15 первой или четвертой ветви, что допустимо, либо на выходе второй или третьей ветви, что недопустимо, так как эти ветви должны быть ис —,. ключены из процесса Моделирования на данном этапе. Исключение запрещенных ветвей в предложенном устройстве обеспечивается за счет дополни35 ваеммх на вход сдви1ового регистра

15 каждой модели ветви, начиная с момомента., отстоящего от момента завершения формировайия 1-того узла на время, большее длительностй и

40 периодов импульсов случайной серии.

Количество дополнительных сдвиговых импульсов равно,.1,2,...,K<(N-1), : где К - количество единиц, появляющихся подряд при дополнительных

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

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

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

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

5-го случайного импульса на выходе рег истра 15 третьей модели ветви (исключаемой из процесса) появится единичный сигнал, который поступит на второй вход элемента И 7. В момент ожидаемого .прихода 1-ro случайного сдвигового импульса на запрещающий ,вход каждой, исключаемой из процес- са, модели ветви (в данном случае второй и третьей моделей ветви) пос-, тупит сигнал запрета.

Допустим, что в момент завершения формирования i-го узла с вероятностным выходом триггеры 13 всех моделей ветви находятся в состоянии "0" °

Тогда сигнал запрета в момент ожидаемого прихода i-ro случайного сдвигового импульса, воздействуя на единичный вход триггера 13 в каждой иэ исключаемых моделей ветви, изменит состояние этого триггера и на его единичном выходе появится сигнал разрешения, который поступит на первый вход элемента И 7. Этот сигнал разрешения пройдет на выход упомянутого элемента только в той, исключаемой из процесса, модели ветви (в данном случае третьей), на выходе .регистра 15 которой имеется единичный сигнал, и появится на фиксирующем выходе указанной модели ветви.

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

При наличии сигнала разрешения на разрешающих входах моделей ветви первый импульс дополнительной серии через элемент И 6 и элемент ИЛИ 17 проходит на вход сдвигового регистра

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

Поскольку эта модель ветви не исключается из процесса моделирования, ни один. из оставшихся (N-К-1) (в данном случае шести) импульсов дополнительной серии не пройдет, на— вход регистра 15 каждой модели ветви на этапе формирования 1+1-го

101узла.

В общем случае в момент окончания (М-1)-го импульса дополнительной серии единичный сигнал будет гарантирован на выходе регистра 15 только одной из неисключенных из процесса моделей ветви, чем и будет обеспе15 чен альтернативный выбор данной. ветВследствие этого единичный сигнал появится на выходе регистра 15 второй модели ветви, которая также должна быть исключена из процесса моделирования. Этот сигнал, воздействуя на второй вход элемента И 7.. второй модели ветви,, по аналогии с предыдущим обеспечит прохождение сначала второго, а затем и третьего импульса дополнительной серии на вход сдвигового регистра 15 всех моделей ветви. В результате произойдет сдвиг информации, находящейся

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

Таким образом, предложенная модель ветви графа может быть исполь"

65 ви. При этом реализованное значение вероятности выбранной ветви окажет20 ся выше, чем ее первоначальное значение (в рассмотренном примере реализованное значение Р = 2/7).

Соответственно возрастут и вероятности реализации других ветвей; не исключенных из процесса моделирования в рассмотренном примере Р "=

5/7 > а вероятности реализации исключенных ветвей будут равны нулю.

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

Поскольку число сдвиговых импульсов случайно и при наличии дополнительных сдвиговых импульсов, появлеЗ5 ние в указанный выше момент единичного сигнала на выходе регистра 15

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

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

2М периодов импульсов случайной (дополнительной) серий (при T « =T> -), 1012268 зована для -моделирования граФов с переменной вероятностной топологией: .и перераспределением первоначальных

1 значений вероятностей ветвей, ис1

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

Составитель С. -Назаров

Редактор М. Келемеш Техред А, Вабинец, Корректор A. Ильин ,4»à 49iia

Заказ 2767/61 Тираж-704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4