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

СОЮЭ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК аю (в Э(59 6 06 815 20 . НОМИТЕТ СССР,РЕТЕНИЙ И ОТНРЫТИЙГОСУДАРСТВЕН О ДЕЛАМ ИЗОБ ИЕ ИЗОБРЕТЕУ Сидтпы:" у ОП ю к двтоеска(71) Институт проблем моделированияв энергетике АН украинской. ССР(54)(57 ) ИОДЕЛЬ ВЕТВИ ГРАФА по авт.св. Р 583439, о т л и ч а ю щ а я -с я тем, что, с .целью расширениякласса решаемых задач путеммоделиро-.вания графов с переменной вероятностной топологией,в .нее введенытретий триггер, седьмой и восьмойэлементы И и элемент ИЛИ, при этомединичный вход третьего триггера является запрещающим входом моделиветви, единичный выход третьеготриггера соединен с первым входомседьмогО элемента И, второй вход которого соединен с выходом сдвигово- .го регистра, а выход является фиксирующим выходом модели ветви,.первый вход восьмого элемента И является разрешающим входом модели ветви,второй вход восьмого элемента И является вспомогательным входоммодели ветви, выход восьмого эта И соединен с первым входоммента ИЛИ, второй вход которогявляется входом задания вероятмодели ветви, выход элемента ИЛИсоединен со входом сдвигового регистра, а третий вход шестого элемента Й является корректирующим входом модели ветви.Изобретение относится к области вычислительной техники, в частности к электронным моделирующим устройствам.По основному авт. св, 9 583439, ,известна модель ветви графа, со" "держащая первый и второй триггеры, Формирователь временного интервала, счетчики начального и конечного ад" ресов, сдвиговый регистр, шесть элементов И и ийвертор, причем первый 10 вход первого элемента И соединен с выходом формирователя. временного интервала, первый вход которого соединен с выходом второго элемента И, первый вход которого соединен с вы ходом счетчика начального адреса, выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов И, второй вход третьего элемента И соединен со вторым входом второго элемента И, третий вход которого соединен с выходом первого триггера, вход счетчика начального адреса соединен со входом модели, вход второго триггера соединен с выходом первого элемента И, второй вход которого И пер-" вый вход пятого элемента И соединены с выходом первого триггера, второй вход пятого элемента И соединены с выходом второго триггера и со вторым входом четвертого элемента И, вторые входы формирователя временного интервала и третьего элемента И соединены с соответствующими входами модели ветви, выходы которой сое динены с выходами .четвертого и пятого элементов И, вход счетчика конечного адреса соединен с входом счетчика начального адреса, вход сдвигового регистра соединен .с до полнительным входом модели ветви графа, а его выход через инвертор подключен к первому входу шестого элемента И, второй вход которого соединен с выходом второго элемента 45 И, а выход - с дополнительным единичным входом первого триггера 1.Недостатком известной модели ветви графа является то, что она не позволяет реализовать дополнительные структурные ограничения, налагаемые в процессе моделирования на топологию графа. Такие ограничения связаны с перераспределением значений вербятностей между ветвями, исключаемыми из процесса моделирова ния, и ветвями, продолжающими участвовать в нем. таким образом, чтобц вероятности оставшихся возможных путей составили снова полную группу событий. В то же время решение за О дач диагностики и прогнозирования развивающихся процессов требует создания специализированных вычислительных устройств и связано с преодолением указанных ограничений.Цель изобретения - расширение класса решаемых задач путем моделирования графов с переменной вероятностной топологией, в том числе стохастических и альтернативных графов, первоначальная топология которых в процессе моделирования.подвергается изменениям и требует перераспределения значений вероятностей ветвей.Поставленная цель достигается тем, что в устройстВо введены третий триггер, седьмой и восьмой элементы И и элемент ИЛИ, при этом единичный вход третьего триггера является запрещающим входом модели ветви, единичный выход третьеготриггера соединен с первым входом седьмого элемента И, второй вход которого соединен с. выходом сдвигово-го регистра, а выход является фиксирующим выходом модели ветви, первый вход восьмого элемента И является разрешающим входом модели ветви,: второй вход. восьмого элемента И является всПомогательнцм входом модели ветви, выход восьмогб элемента И соединен с первым входом элемен- та ИЛИ, второй вход которого является входом задания вероятности модели ветви, выход элемента ИЛИ соединен со входом сдвигового регистра, а третий вход шестого элемента И является корректирующим входом модели ветви.На чертеже представлена предложенная структурная схема моделиМодель ветви содержит элементы;И 1 - 8, счетчик начального адреса З, счетчик конечного адреса 10, тригге" ры 11 - 13, Формирователь временного интервала 14, сдвиговый регистр 15, инвертор 16 и элемент ИЛИ 17.Работу модели ветви рассмотрим с момента, когда сформирован 1-тый узел графа с вероятностным выходом, допустим, из 1-того узла выходят четыре ветви свероятностями реализации Р = Р= 0,2, Р = 0,1,= 0,5,Емкость регистра И=10 и реализуется альтернативный выбор одной из исходящих ветвей. Способ занесения информации о вероятностях в разряды сдвиговых регистров аналогичен описанному в Ц и приведен в таблице в ней обозначены ветви графа, которые на данном этапе моделирования должны быть исключены из процесса)1012268 Ветвь Разряды регистровГ 1 О о о о о 0 о о . 0 о 0 о о о о о о о о. о о О О. 1 0 20 25 30 60 единичный сигнал окажется на выхо 65 Допустим, что в процессе модели-. рования моделируется древовидный граф развивающегося процесса и на этой модели осуществляется вероятностный выбор наиболее достоверных гипотез. В таком случае первоначально априорная информация о вероятностях переходов, соответствующая вероятностям ветвей, исходящих из 1-тогоузла, заносит-" ся в регистры и процесс моделирования происходит с реализацией альтернативного выбора ветвей аналогично тому., как это осуществляется в 11. Указанный процесс моделирования для выявления наиболее достоверных гипотез требует многократного моделирования возможных пу" тей графа с исключением гипотез, а значит и путей графа, не удовлетворяющих условиям соответствия ис ходным данным задачи; При этом исключение путей графа сводится к исключению некоторых ветвей, исходящих из некоторых .узлов. Поскольку пер. воначально эти исключаемые впоследст.вии ветви реализовали некоторое заданное значение вероятности, то после их исключения это значение вероятности необходимо перераспределить между остальными ветвями, исходящими из данного узла равномерно, сохранив случайный выбор неисключениых ветвей и обязательный выбор одной из них. Анализ получаемых в . процессе моделирования гипотез на соответствие исходным данным задачи может выполнять специальное контро".: :лирующее устройство, входящее в состав блока управления, В его . функции входит выявление ветвей гра= фа, которые необходимо исключить на каждом этапе моделирования, и выдача (в момент ожидаемого прихода первого сдвигового импульса случайнойсерии) сигнала запрета на запрещающий вход каждой модели ветви, которая должна быть исключена из процесса моделирования, допустим, что сигналы запрета в указанный выше момент поступили. на запрещаю 6 7 8, 9 щие входы второй и третьей моделей ветви. Тогда, поскольку числосдвиговых импульсов случайно, могутиметь место следующие ситуации.После окончания случайной серии импульсов (НОВ 10), поступающих на веро-ятностный вход и через элемент ИЛИ17 на вход сдвигового регистра 15каждой модели ветви, единичныйсигнал окажется на выходе регистра15 первой или четвертой ветви, чтодопустимо, либо на выходе второйили третьей ветви, что недопустимо,так как эти ветви должны быть ис - ,. ключены из процесса Моделированияна данном этапе. Исключение запрещенных ветвей в предложенном устройстве обеспечивается за счет дополнительных сдвиговых импульсов, пода;ваемюх на вход сдви 1 ового регистра15 каждой модели ветви, начиная с момомента отстоящего от момента завершения формировайия 1-того узлана время, большее длительностй й 40 периодов импульсов случайной серии.Количество дополнительных сдвиговыхимпульсов равно, 1,2К%(И),где К - количество единиц, появляющихся подрядпри дополнительных 45; сдвигах на выходах регистров 15всех запрещенных моделей ветви, при условии, что после окончания случайной серии импульсов на одном из указанных выходов оказалась единица. В 50 случае, если после окончания случайной серии импульсов единица оказалас;ь на выходе регистра 15 однойиз нейсключаемых из процесса моделейветви, то количество дополнительныхсдвиговых импульсов равно нулю ислучайный выбор одной из ветвей гра-фа считается завершенным. Рассмотрим .случай, когда после окончания случайной серии импульсовде регистра 15 одной из исключаемых из процесса моделей ветви.Так, если в приведенном в таблице примере. сдвиги в регистрах 15 моделей ветви осуществляются в сто 1012268рону старших разрядов регистров, начальные состояния регистров 15 в момент завершения формирования -того узла соответствуют заданным таблицей, а число случайных сдвиговых импульсов равно пяти, то после поступления 5-го случайного импульса на выходе регистра 15 третьей модели ветви (исключаемой из процесса) появится единичный сигнал, который поступит на второй вход элемента И 7. В момент ожидаемого, прихода 1-го случайного сдвигового импульса на запрещающий ,вход каждой, исключаемой из процес-са, модели ветви (в данном случае второй и третьей моделей ветви) пос-, тупит сигнал запрета.Допустим, что в момент завершения формирования 1-го узла с вероятностным выходом триггеры 13 всех моделей ветви находятся в состоянии "ОфТогда сигнал запрета в момент ожидаемого прихода -го случайного сдвигового импульса, воздействуя на единичный вход триггера 13 в каждой иэ исключаемых моделей ветви, изменит состояние этого триггера и на его единичном выходе появится сигнал разрешения, который поступит на первый вход элемента И 7. Этот сигнал разрешения пройдет на выход упомянутого элемента только в той, исключаемой из процесса, модели ветви (в данном случае третьей), на выходе регистра 15 которой имеется единичный сигнал, и появится на Фиксирующем выходе указанной модели ветви.При этом из блока управления на разрешающие входы всех моделей ветви поступает сигнал разрешения, а от генератора импульсов на вспомогательные входы всех моделей ветви приходит первый импульс дополнительной серии, содержащей Мимпульс. При наличии сигнала разрешения на разрешавицих входах моделей ветви первый импульс дополнительной серии через элемент И В и элемент ИЛИ 17 проходит на вход сдвигового регистра 15 каждой модели ветви. В результате этого информация, находящаяся в регистрах 15 всех моделей ветви, сдвинется вправо на один разряд; еще на два разряда вправо и единичный сигнал окажется на выходе регистра 15 первой модели ветви.Поскольку эта модель ветви не исключается из процесса моделирования, ни один. из оставшихся (М-К) (в данном случае шести) импульсов дополнительной серии не пройдет, на - вход регистра 15 каждой модели ветви на этапе формирования 1+1-го 10 1 узла,В общем случае в момент окончания (М)-го импульса дополнительной серии единичный сигнал будет гарантирован на выходе регистра 15 только одной из неисключенных из процесса моделей ветви, чем и будет обеспе 15 чен альтернативный выбор данной.ветВследствие этого единичный сигнал появится на выходе регистра 15 второй модели ветви, которая также должна быть исключена из процесса моделирования. Этот сигнал, воздействуя на второй вход элемента И 7 второй модели ветви по аналогии с предыдущим обеспечит прохождение сначала второго, а затем и третьего импульса дополнительной серии на вход сдвигового регистра 15 всех моделей ветви, В результате произойдет сдвиг информации, находящейся в регистрах 15 всех моделей ветви,Исходные состояния элементов схемы каждой модели ветви, обеспе-; чивающих фиксацию альтернативного выбора, с момента завершения формировайия )-того узла и до прихода сигнала готовности не изменяются и соответствуют исходным состоянием тех же элементов схемы модели ветви. прототипа, но в момент окончания формировайия 1-того узла.Таким образом, предложенная модель ветви графа может быть исполь" 55 60 65 ви. При этом реализованное значениевероятности выбранной ветви окажет-2 О ся выше, чем ее первоначальное значение (,в рассмотренном примере реализованное значение Р= 2/7).Соответственно возрастут и вероятности реализации других ветвей; неисключенных из процесса моделирова"ния в рассмотренном примере Р"=5/7а вероятности реализации иск"люченных ветвей будут равны нулю.Сумма же вероятностей реализациивсех неисключенных ветвей составитединицу, что и соответствует новойполной группе событий.Поскольку число сдвиговых импульсов случайно и при наличии дополнительных сдвиговых импульсов, появлеЗ 5 ние в указанный выше момент единичного сигнала на выходе регистра 15)-той, неисключенной из процесса,модели ветви является случайным событием.40 После цкончания (М)-го импульсадополнительной серии на корректирующий вход каждой модели ветви из блока управления поступает сигнал готовности, представляющий собой еди ничный импульс (например М-ый импульс, исключенный из дополнительной серии), который разрешает зафиксировать завершенный случайныйвыбор участвующих в процессе моде-лирования ветвей с. учетом дополнительной задержки на время, равное2 М периодов импульсов случайной (дополнительной) серин (при ТМсс =Тле)1012268 Составитель С. НазаровРедактор М. Келемеш Техред А, Вабинец . КорректорА. Ильине 4 ааю 46 ь ееаавЗаказ 2767/61 Тираж 704ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва,. ж, Раушская наб., д.4/5 филиал ППП "Патентф, г. Ужгород, ул. Проектная, 4 зована для моделирования графов спеременной вероятностной топологией:.и перераспределением первоначальныхзначений вероятностей ветвей, ис 8ходящих из узлов с вероятностниаи выходами, когда часть из этих ветвей на данном этапе моделирования должна быть искаочена из йроцесса