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

 

Союз Советских

Социал исткческмх

Респубпнк

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Ф

/ (6l ) Дополнительное к авт. свил-ву— (5l) M. Кл. (22)Заявлено 2 1.03.77 (21) 2464808/18-24 с присоединением заявки №вЂ” т: 06 б 7/122

Государственный комитет (23) Приоритет

Опубликовано25,05.80. Бюллетень ¹19

Дата опубликования описания 26 .05.80 по делам изобретений и открытий (u) удК 6». .333 (088.8}

A. Г. Додонов, В. В. федотов, Н. B. Федотов, В. В. Хаджанов и В. M. Шишмареа;;, 1

11

1-

I. (: =".VI 1, -; П -,., 1;;

) I (72) Авторы изобретения (71) Заявитель (54} МОДЕЛЬ ДВУНАПРАВЛЕННОЙ ВЕТВИ

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

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

Известна модель ветви, содержащая

15 счетчик, элементы И, элементы ИЛИ, элемент НЕ, триггер и узлы регистрации величины потока (1)

Указанная модель не обеспечивает достаточную точность.

Наиболее близкой по технической сущности к рассматриваемой является модель ветви, содержащая элементы И, ИЛИ, НЕ выпрямители, счетчики и триггеры f2).

К недостатку этой модели следует отнести невозможность определения кратчайшего пути в неориентированных графах.

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

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

736 12 соединен с первым входом третьего эпемента И, второй вход которого подключен к выходу второго триггера, соединенному со вторыми входами первого и второго элементов И, третьи входы которых сое5 динены и являются третьим входом модепи, четвертые входы первого и второго эпементов И подключены соответственно к первым выходам третьего и четвертого триггеров, входы которых соединены соответственно с выходами второго и первого элементов И, вторые выходы третьего и четвертого триггеров подкпючены ко вторым входам формирователей веса ветви и соответственно к первым входам шестого и седьмого эпементов И, вторые входы которых соединены и являютсяя третьи м входом модели, третьи входы шестого и седьмого элементов Иподключены к выходам счетчиков, выходы шестого и седьмого элементов И соединены со входами второго элемента

ИЛИ, выход которого подключен ко входу второго триггера, первый вход восьмого элемента И соединен с выходом пер- 5 вого триггера, вторые входы четвертого и восьмого элементов И подключены соответственно к выходам счетчиков, выходы четвертого и восьмого эпементов

И соединены со входами третьего элемента ИЛИ, выходы пятого элемента И и третьего элемента ИЛИ явпяются соответственно первым и вторым выходами модели.

На чертеже изображена схема модели дву ца правпе нной ветви.

Она включает вход 1 модепи эпементы И 2-9, эпементы ИЛИ 10-12, счетчики 13 и 14, триггеры 15-18, форми- роватепи 19 и 20 весов ветви, поптоса

21-24 являются входами и 25-26 выходами формирователей весов ветви, входы 27 и 28 модели, выходь| 29 и 30.

Формирователи 19 и 20 весов ветви представляют дискретную управляемую ли- 45 нию задержки с регенерацией исходной информации. Чаще всего в качестве формирователей весов ветви используют счетчики импульсов емкостью М

Работа модели двунаправпенной ветви происходит следующим образом, Предварительно в счетчики 13 и 14 адресов заносят адреса узлов инцидентных соответствующей ветви в обратном

55 коде. Под адресом узпа понимают номер, который ему присваивается в моделируемой сети. Этим обеспечивается формирование топологии модепируемой сети. Зане-, 1

4 сение адресов в счетчики 13 и 14 равносильно записи числа импульсов в каждый из соответствующих счетчиков, равного (Я -1) и (1Ч вЂ” j ), где N — емкость указанных счетчиков, а т и }, соответственно, номера узлов, инцидентных моделей двунаправпенной ветви.

Значение весов ветви з вписывается в каждый из соответствующих формироватепей 19 и 20 как число импульсов (М-й ) и (tA-Ì ), где 1т и тт — вес ветви в определенном (прямое и обратное) направлении между узпами 1 и j . Триггеры 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

При переполнении счетчика 14 пусковой импульс проходит элемент И 4 и устанавливает триггер 18 в единичное состояние.

Единичное состояние одного из триггеров 17 или 18 производит блокировку входа элемента И 3 или И 4 и, соответственно, поступает на вход 23 или 24 одного из формирователей 19 или 20 веса ветви. Тем самым производится подготовка одного из формирователей веса ветви в одном из направлений к работе.

Если триггер 17 находится в единичном состоянии, то подготавливается формирователь 19 веса ветви. При единичном со15 стоянии триггера 18 подготавливается к работе формирователь 20 веса ветви.

Одновременно с "пусковым" импульсом устройство управления подает импульсы тактового генератора ГИА на вход 1. Им20 пульсы ГИ2 сдвинуты относительно ГР „, Отсчитав необходимое для воспроизведения веса ветви число импульсов ГИ, формирователи выдают сигнал по соот25 ветствующему выходу 25 или 26. На полюсе 25 сигнал появляется при окончании воспроизведения веса ветви формирователем 19, а на полюсе 26 — при окончании воспроизведения веса формировате30 лем 20. Один из указанных сигналов проходит через элемент ИЛИ 10 и элемент

И 2 и устанавливает триггер 15 в единичное состояние. Единичное состояние этого триггера поступает на вход элемента И 5, В результате того, что на входе элемента И 5 есть два разрешающих сигнала, на его выходе появляется сигнал и, следовательно, на выходе 29 модели двунаправленной ветви. Этот сит

40 нал поступает в устройство управления.

По этому сигналу устройство управления прекращает подачу импульсов ГИ 1 на входы 1 всех моделей и разрешает поступление импульсов ГИ2 на входы 28..

Отсчитав необходимое для переполнения число импульсов, счетчик 13. или 14 выдает сигнал переполнения, Таким счетчиком в модели, связанной с начальным узлом моделируемой сети, является счетчик, в который занесен адрес, отличный от адреса начального узла. Импульс переполнения поступает на вход элементов

И 7, 6, 8 и 9. При этом, если счетчик

13 переполняется, то импульс переполнения поступает на элементы И 6 и И 8.

При переполнении счетчика 14 импульс переполнения поступает на элемент И 7 иИ9.

21 6

Один из этих импульсов проходит соответственно алемент И 8 либо И 9, так как на входе алементов есть разрешение с триггера 15 и алемент, ИЛИ 12. Таким образом, импульс переполнения поступает на выход 30 модели двунаправленной ветви.

С выхода 30 импульс поступает в устройство управления. По атому импульсу устройство управления прекращает пода чу импульсов ГИд на вход 28, выдает

2 пусковой импульс на вход 27 и разрешает поступать импульсам ГИ на вход l.

Пусковой " импульс блокирует модели, инцидентные начальному узлу, и производит запуск моделей, которые связаны. с выше упомянутыми.

Блокировка происходит следующим об-. разом: пусковой" импульс со входа 27 поступает на вход элементов И 6 и И 7.

Он проходит только через тот из этих элементов, на входах которого есть разрешение с одного из триггеров 17 или

18 и сигнал о переполнении счетчика .

13 или 14.

Если триггер 17 находится в единичном состоянии и счетчик 14 выдал сигнал переполнения, то "пусковой импульс проходит элемент И 7, При единичном состоянии триггера 18 и сигнала переполнения с счетчика 13, "пусковой импульс проходит элемент И 6 . Далее пусковой" импульс проходит элемент ИЛИ 11 и устанавливает триггер 16 в единичное состояние. Единичное состояние триггера—

16 снимает разрешение с элементов И

2-5, что обеспечивает блокировку модели по входу 27 и съем сигнала с выхода 29.

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

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

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

Модель двунаправленной ветви, содержащая формирователь веса ветвей, первый вход которого является первым входом модели, счетчики, входы которых объ736 12 единены и явпяются вторым входом модели, выходы счетчиков подключены соответственно к первым входам первого и второго элементов И, выход третьего эле мента И через первы и триггер с оедине н с первыми входами четверт ого и пятого элементов И, второй вход которого подключен к выходу второго триггера, и элементы ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональ-1О ных возможностей за счет опредепения кратчайшего пути в неориентированных графах, в модель введены дополнительно триггеры, элемент И и дополнительный формирователь веса ветви, вход которого 1З является первым входом модели, выходы формирователей веса ветви подключены соответственно ко входами первого элемента ИЛИ, выход которого соединен с первым входом третьего элемента И, вто- 2О рой вход которого подключена к выходу второго триггера, соединенному со вторыми входами первого и второго элементов

И, третьи входы которых соединены и являются третьим входом модели, четвер- 25 тые входы первого и второго эпементов

И подключены соответственно к первым выходам третьего и четвертого триггеров, входы которых соединены соответственно с выходами второго и первого элементов ЗО

1 8

И, вторые выходы третьего и четвертого триггеров подключены ко вторым входам формирователей веса ветви и соответственно к первым входам шестого и седьмого элементов И, вторые входы которых соединены и являются третьим входом модели, третьи входы шестого и седьмого элементов И подключены к выходам счетчиков 13 и 14, выходы шестого и седьГ мого элементов И соединены со входами второго элемента 11 ИЛИ, выход которого подключен ко входу второго триггера 16, первый вход восьмого элемента И соединен с выходом первого триггера, вторые входы четвертого и восьмого эпементов И подключены соответственно к выходам счетчиков, выходы четвертого и восьмого элементов И соединены со входами третьего элемента

ИЛИ, выходы пятого элемента И, третьего элемента ИЛИ являются соответственно первым и вторым выходами модели.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке % 23 83 7 1 2/1 8-24, кл. 9 06 F 15/20, 1976.

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

N": 470811, кл. 6 06 F 15/20, 1973 (прототип) .

11НИИПИ Заказ 2277/7 Тираж 751 Подписное

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