Модель двунаправленной ветви

Союз СоветскихСоциал исткческнхРеспубпнк ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ии 736121(23) Приоритет Опубликовано 25,05,80. Бюллетень 19Дата опубликования описания 26 .05.80 по делам изобретений и открытий(54) МОДЕЛЬ ДВУНАПРАВЛЕННОЙ ВЕТВИ 1Изобретение относится к вычислительной технике, в частности к моделирующим устройствам, и может быть использовано при построении цифровых специализированных машин для решения задач исследования операций.5Задача определения кратчайшего пути в неориентированных сетях заключается в нахождении минимального пути между заданной парой узлов, ветви этой сети характеризуются целочисленным неотри 1 О цательным параметром-весом, причем двунаправленная ветвь может иметь различный вес в каждом из направлений,Известна модель ветви, содержащая15 счетчик, элементы И, элементы ИЛИ, элемент НЕ, триггер и узлы регистрации величины потока 1Указанная модель не обеспечивает достаточную точность.Наиболее близкой по технической сущности к рассматриваемой является модель ветви, содержащая элементы И, ИЛИ, НЕ выпрямители, счетчики и триггеры 21. 2К недостатку этой модели следует отнести невозможность определения кратчайшего пути в неориентированных графах.Цель изобретения - расширение функциональных возможностей,Поставленная цель достигается тем,что в модель, содержащую формировательвеса ветвей, первый вход которого является первым входом модели счетчики,входы которых объединены и являютсявторым входом модели, выходы счетчиковподключены соответственно к первым входам первого и второго элементов И, выход третьего элемента И через первыйтриггер соединен с первыми входами четвертого и пятого элементов И, второйвход которого подключен к выходу вторсмго триггера, и элементы ИЛИ, введеныдополнительно триггеры, элементы И идополнительный формирователь веса ветви,вход которого является первым входоммодели, выходы формирователей веса ветви подключены соответственно ко входампервого элемента ИЛИ, выход которогосоединен с первым входом третьего апемента И, второй вход которого подключен к выходу второго триггера, соединенному со вторыми входами первого и второго эпементов И, третьи входы которых сое 5 динены и являются третьим входом модепи, четвертые входы первого и второго эпементов И подключены соответственно к первым выходам третьего и четвертого триггеров, входы которых соединены соответственно с выходами второгои первого элементов И, вторые выходыМтретьего и четвертого триггеров подкпючены ко вторым входам формирователейвеса ветви и соответственно к первым 15входам шестого и седьмого эпементов И,вторые входы которых соединены и являютсяя третьи м входом модели, третьи1входы шестого и седьмого элементов Иподключены к выходам счетчиков, выходышестого и седьмого элементов И соединены со входами второго элементаИЛИ, выход которого подключен ко входу второго триггера, первый вход восьмого элемента И соединен с выходом первого триггера, вторые входы четвертогои восьмого апементов И подключены соответственно к выходам счетчиков, выходы четвертого и восьмого эпементовИ соединены со входами третьего элемента ИЛИ, выходы пятого элемента Ии третьего элемента ИЛИ явпяются соответственно первым и вторым выходами модели.На чертеже изображена схема моделидвунаправленной ветви,Опа включает вход 1 модепи эпементы И 2-9, эпеметы ИЛИ 10-12, счетчики 13 и 14, триггеры 15-18, формироватепи 19 и 20 весов ветви, поптоса 4021-24 являются входами и 25-26 выходами формирователей весов ветви, входы 27 и 28 модели, выходь 29 и 30.Формирователи 19 и 20 весов ветвипредставляют дискретнуо управляемую линию задержки с регенерацией исходнойинформации. Чаще всего в качестве формирователей весов ветви используют счетчики импульсов емкостью МРабота модели двунаправпенной ветвипроисходит следующим образом,Предварительно в счетчики 13 и 14адресов заносят адреса узлов инцидентных соответствующей ветви в обратном55коде. Под адресом узпа понимают номер,который ему присваивается в моделируемой сети. Этим обеспечивается формирование топологии модепируемой сети. Зане,сение адресов в счетчики 13 и 14 равносильно записи числа импульсов в каждый из соответствующих счетчиков, равного ( К -1) и (1 Ч- ) ), где- емкость указанных счетчиков, а т и , соответственно, номера узлов, инцидентных моделей двунаправпенной ветви.Значение весов ветви записывается в каждый из соответствующих формироватепей.19 и 20 как число импульсов (М-И ) и (М-м ) где 1 т и тт - вес ветви в определенном (прямое и обратное) направлении между узпами 1 и т , Триггеры 15-18 устанавливаются в нулевое состояние,Адреса начального и конечного узлов сети, между которыми определяют кратчайший путь, задаются в устройстве управпения (на чертеже не показано).Запуск моделей ветвей, исходящих из начального узла сети, осуществляется в результате подачи импупьсов тактового генератора (на чертеже не показан) на вход 28 и разрешения "пусковой" импульс на вход 27, На вход 27 подается число импульсов ГИ , пропорциональное адресу начального узла. Тем самым осуществляется выбор моделей, выходящих из начального узла моделируемой сети. Это происходит спедующим образом: счетчики 13 и 14 накапливают импульсы ГИпоступающие на вход 27, до тех пор, пока на выходе одного из них не появляется сигнал переполнения. Первым перепопняется тот счетчик, в который был записан адрес начального узпа в обратном коде.Еспи переполняется счетчик 13, то в этом случае на вход элемента И 3 поступает сигнал о переполнении, На два других входа атого апемента поступает разрешение с нулевых выходов триггеров 18 и 16.Если переполняется счетчик 14, то сигнал переполнения поступает на вход элемента И 4, На другие два входа эпемента И 4 поступает разрешение с нулевых выходов триггеров 18 и 17.Одновременно со входа 27 поступает на входы элементов И 3 и 4 "пусковой импульс. Он проходит только тот апемент И, на котором в данный момент есть сигнап перепопнения с выхода счетчика.При переполнении счетчика 13 "пусковой"импульс проходит элемент И 3 иустанавпивает триггер 17 в единичное ссстояние,736 1 5При переполнении счетчика 14 пусковой импульс проходит элемент И 4 и устанавливает триггер 18 в единичное состояние. 10 Единичное состояние одного из триг геров 17 или 18 производит блокировку входа элемента И 3 или И 4 и, соответственно,поступает на вход 23 или 24 одного из формирователей 19 или 20 веса ветви. Тем самым производится подготовка одного из формирователей веса ветви в одном из направлений к работе, Если триггер 17 находится в единичном состоянии, то подготавливается формирователь 19 веса ветви, При единичном со15 стоянии триггера 18 подготавливается к работе формирователь 20 веса ветви.Одновременно с "пусковым" импульсом устройство управления подает импульсы тактового генератора ГИ 1 на вход 1. Им 20 пульсы ГИ 2 сдвинуты относительно Ю, Отсчитав необходимое для воспроизведения веса ветви число импульсов ГИ, формирователи выдают сигнал по соот 25 ветствующему выходу 25 или 26. На полюсе 25 сигнал появляется при окончании воспроизведения веса ветви формирователем 19, а на полюсе 26 - при окончании воспроизведения веса формировате 30 лем 20. Один из указанных сигналов проходит через элемент ИЛИ 10 и элемент И 2 и устанавливает триггер 15 в единичное состояние. Единичное состояние этого триггера поступает на вход элемента И 5, В результате того, что на входе элемента И 5 есть два разрешающих сигнала, на его выходе появляется сигнал и, следовательно, на выходе 29 модели двунаправленной ветви. Этот сиг 40 нал поступает в устройство управления.По этому сигналу устройство управления прекращает подачу импульсов ГИ 1 на входы 1 всех моделей и разрешает поступление импульсов ГИ 2 на входы 2845Отсчитав необходимое для переполнения число импульсов, счетчик 13. или 14 выдает сигнал переполнения, Таким счетчиком в модели, связанной с начальным узлом моделируемой сети, является счетчик, в который занесен адрес, отличный от адреса начального узла. Импульс переполнения поступает на вход элементов И 7, 6, 8 и 9. При этом, если счетчик 13 переполняется, то импульс переполнения поступает на элементы И 6 и И 8., При переполнении счетчика 14 импульс переполнения поступает на элемент И 7 иИ 9. 21 6Один из этих импульсов проходит соответственно алемент И 8 либо И 9,таккак на входе алементов есть разрешениес триггера 15 и алемент, ИЛИ 12. Таким образом, импульс переполнения поступает на выход 30 модели двунаправленной ветви.С выхода 30 импульс поступает вустройство управления. По атому импульсу устройство управления прекращает подачу импульсов ГИд на вход 28, выдаетпусковой импульс на вход 27 и разрешает поступать импульсам ГИ на вход 1,Пусковой импульс блокирует модели, инцидентные начальному узлу, и производит запуск моделей, которые связаныс выше упомянутыми.Блокировка происходит следующим об-.разом: пусковой" импульс со входа 27поступает на вход элементов И 6 и И 7.Он проходит только через тот из этихэлементов, на входах которого есть разрешение с одного из триггеров 17 или18 и сигнал о переполнении счетчика13 или 14.Если триггер 17 находится в единичном состоянии и счетчик 14 выдал сигнал переполнения, то "пусковой" импульспроходит элемент И 7, При единичномсостоянии триггера 18 и сигнала переполнения с счетчика 13, "пусковой" импульс проходит элемент И 6 . Далее пусковой" импульс проходит элемент ИЛИ 11и устанавливает триггер 16 в единичноесостояние. Единичное состояние триггера16 снимает разрешение с элементов И2-5, что обеспечивает блокировку моделипо входу 27 и съем сигнала с выхода 29.Одновременно с этим происходит запуск последующих моделей "пусковымимпульсом аналогично, как было описаноранее,Таким образом происходит выбор моделей, которые определяют кратчайшийпуть между начальным и конечным узлами ести. Число импульсовП 4 поступившее на вход 1 этих моделей, определяетвеличину атого пути.Рассматриваемая модель обеспечиваетопределение кратчайшего пути в неориентированных графах с большей точностью,чем устройства аналогичного назначения,формула изобретенияМодель двунаправленной ветви, содержащая формирователь веса ветвейпервый вход которого является первым входом модели, счетчики, входы которых объ73612 ЦНИИПИ Заказ 2277/7 Тираж 751 пис иал ППП "Патент", г, Ужгород, ул. Проектная единены и являются вторым входом модели, выходы счетчиков подключены соответственно к первым входам первогои второго элементов И, выход третьегоэлемента И через первый триггер соединен с первыми входами четвертого ипятого элементов И, второй вход которогоподключен к выходу второго триггера, иэлементы ИЛИ, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональОных возможностей за счет определениякратчайшего пути в неориентированныхграфах, в модель введены дополнительнотриггеры, элемент И и дополнительныйформирователь веса ветви, вход которого 15является первым входом модели, выходыформирователей веса ветви подключенысоответственно ко входами первого элемента ИЛИ, выход которого соединен спервым входом третьего элемента И, второй вход которого подключена к выходувторого триггера, соединенному со вторыми входами первого и второго элементовИ, третьи входы которых соединены иявляются третьим входом модели, четвертые входы первого и второго элементовИ подключены соответственно к первымвыходам третьего и четвертого триггеров,входы которых соединены соответственнос выходами второго и первого элементов 30 1 8И, вторые выходы третьего и четвертоготриггеров подключены ко вторым входамформирователей веса ветви и соответственно к первым входам шестого и седьмого элементов И, вторые входы которыхсоединены и являются третьим входом модели, третьи входы шестого и седьмогоэлементов И подключены к выходам счетчиков 13 и 14, выходы шестого и седьГмого элементов И соединены со входамивторого элемента 11 ИЛИ, выход которого подключен ко входу второго триггера 16, первый вход восьмого элемента И соединен с выходом первого триггера, вторые входы четвертого и восьмого элементов И подключены соответственно к выходам счетчиков, выходычетвертого и восьмого элементов И соединены со входами третьего элементаИЛИ, выходы пятого элемента И, третьего элемента ИЛИ являются соответственно первым и вторым выходами модели,Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРпо заявке % 2383712/18-24,кл. б 06 Е 15/20, 1976.2, Авторское свидетельство СССР