Модель двунаправленной ветви Советский патент 1980 года по МПК G06G7/122 

Изобретение относится к вычислитель ной технике, в частности к моделирующим устройствам, п может быть использовано при построении цифровых специализированных машин для решения задач исследования операций. Задача определения кратчайшего пу.ти в неориентированных сетях заключается в нахождении минимального пути между заданной парой узлов, ветви этой сети характеризуются целочисленным неотрицательным параметром-весом, причем дву направленная ветвь может иметь различный вес в каждом из направлений. Известна модель ветви, содержащая счетчик, элементы И, элементы ИЛИ, эле мент НЕ, триггер и узлы регистрации величины потока Г . Указанная модель не обеспечивает достаточную точность. Наиболее близкой по технической сущности к рассматриваемой является модель ветви, содержащая элементы И, ИЛИ, НЕ выпрямители, счетчики и триггеры Г2. К недостатку этой модели следует отнести невозможность определения кратчайшего пути в неориентированных графах. Цель изобретения - расширение функ- . шгональных возможностей. Поставленная цель достигается тем, что в модель, содержащую формирователь веса ветвей, первый вход которого является первым входом модели, счетчики, входы которых объединены и являются вторым входом модели, выходы счетчиков подключены соответственно к первым входам первого и второго элементов И, выход третьего элемента И через первый триггер соединен с первыми входами четвертого и пятого элементов И, второй вход которого подключен к выходу второго триггера, и элементы ИЛИ, введены дополнительно триггеры, элементы И и дополнительный формирователь веса ветви, вход которого является первым в ;одом модели, выходы формирователей веса ветви подключены соответственно ко входам первого элемента ИЛИ, выход которого 373 соединен с первым входом третьего элемента И, второй вход которого подключен к выходу второго триггера, соединенному со вторыми входами первого и второго элементов И, третьи входы которых соединены и являются третьим входом модели, четвертые входы первого и второго элементов И подключены соответственно к первым выходам третьего и четвер того триггеров, входь которых соединены соответственно с выходами второго и первого Элементов И, вторые выходьи третьего и четвертого триггеров подключены ко вторым входам формирователей веса ветви и соответственно к первым входам шестого и седьмого элементов И, вторые входы которых соединены и являются третьим входом модели,третьи входы шестого и седьмого элементов И под ключены к выходам счетчиков, выходы шестого и седьмого элементов И сое: динены со входами второго элемента ИЛИ, выход которого подключен ко вхо- : ду второго триггера, первый вход восьмого элемента И соединен с выходом пе вого триггера, вторые входы четвертого и восьмого элементов И подключены соответственно к выходам счетчиков, выходы четвертого и восьмого элементов И соединены со входами третьего элемонта ИЛИ, выходы пятого элемента И и третьего элемента ИЛИ являются соответственно первым и вторым выходами м дели. На чертеже изображена схема модели двунаправленной ветви. Она включает вход 1 модели элементы И 2-9, элементы ИЛИ 10-12, счетчики 13 и 14, триггеры 15-18, формирователи 19 и 20 весов ветви, потоса 21-24 являются входами и 25-26 выходами формирователей весов ветви, вхо ды 27 и 28 модели, выходы 29 и 30, Формирователи 19 и 20 весов ветви представляют дискретную управляемую ли нию задержки с регенерацией исходной информации. Чаще всего в качестве форм рователей весов ветви используют счетчики импульсов емкостью АЛ . Работа модели двунаправленной ветви происходит следующим образом,. Предварительно в счетчики 13 и 14 адресов заносят адреса узлов инцидент- iibix соответствуюи1ей ветви в обратном коде. Под адресом узла понимают номер который ему присваивается в модепируемой сети. Этим обеспечивается формирование -топологии моделируемой сети, За .4 сение адресов в счетчики 13 и 14 равносильно записи числа импульсов в каждый из соответствующих счетчиков, равного { N -1) и (14-J ), где N - емкость указанных счетчиков, а 1 и j , соответственно, номера узлов, инцидентных моделей двунаправленной ветвиГ Значение весов ветви записывается в каждый из соответствукияих формирователей 19 и число импульсов (-V1) и ( ), где VI и hi - вес ветви в определенном (прямое и обратное) направлении между узлами i и j . Триггеры 15-18 устанавливаются в нулевое состояние. Адреса начального и конечного узлов сети, между которыми определяют кратчайший путь, задаются в устройстве управления (на чертеже не показано). Запуск моделей ветвей, исходящих из начального узла сети, осуществляется в результате подачи импульсов тактового генератора (на чертеже не показан) на вход 28 и разрешения пусковой импульс на вход 27. На вход 27 подается число импульсов ГИ2 , пропорциональное адресу начального узла. Тем самым осуществляется выбор моделей, выходящих из начального узла моделируемой сети. Это происходит следующим образом: счетчики 13 и 14 накапливают импульсы ГИ 2 . поступающие на вход 27, до тех пор, пока на выходе одного из них не появляется сигнал переполнения. Первым переполняется тот счетчик, в который был записан адрес начального узла в обратном коде. Если переполняется счетчик 13, то в этом случае на вход элемента И 3 поступает сигнал о переполнении. На два других входа этого элемента поступает разрешение с нулевых выходов триггеров 18 и 16. 1Бсли переполняется, счетчик 14, то сигнал переполнения поступает на вход элемента И 4. На другие два входа элемента И 4 поступает разрешение с нулевых выходов триггеров 18 и 17. Одновременно со входа 27 поступает на входы элементов И 3 и 4 пусковой импульс. Он проходит только тот элемент И, на котором в данныи момент есть сигнал перепопнения с выхода счетчика. При переполнении счетчика 13 пусковойимпульс проходит элемент И 3 и устанавливает триггер 17 в единичное состояние. При переполнении счетчика 14 пусковой импульс проходит элемент И 4 и устанавливает триггер 18 в единичное состояние. Единичное состояние одного из триггеров 17 или 18 производит блокировку входа элемента И 3 или И 4 и, соответс венно поступает на вход 23 или 24 одного из .формирователей 19 или 20 веса ветви Тем самым производится подготовка одного из формирователей веса ветви в одном из направлений к работе. Если триггер 17 находится в единичном состоянии, то подготавливается формиро- ватель 19 веса ветви. При единичномсо стоянии триггера 18 подготавливается к работе формирователь 20 веса ветви. Одновременно с пусковым импульсом устройство управления подает импульсы тактового генератора ГИ1 на. вход 1. Им пульсы ГИ2 сдвинуты относительно ГИ.. Отсчитав необходимое для воспроизведения веса ветви число импульсов ГИ-j, формирователи выдают сигнал по соответствующему выходу 25 или 26. На полюсе 25 сигнал появляется при окончании воспроизведения веса ветви формироВ(ателем 19, а на полюсе 26 - при окончании воспроизведения веса формирователем 20. Один из указанных сигналов про ходит через Элемент ИЛИ 10 и элемент И 2 и устанавливает триггер 15 в единичное состояние. Единичное состояние этого триггера поступает на вход элемента И 5 В результате того, что на входе элемента И 5 есть два разрешающих сигнала, на его выходе появляется сигнал и, следовательно, на выходе 29 модели двунаправленной ветви. Этот си1г- нал поступает в устройство управления. По этому сигналу устройство управления прекращает подачу импульсов ГИ на входы 1 всех моделей и разрешает поступление импульсов ГИ 2 на входы 28. . Отсчитав необходимое для переполнения число импульсов, счетчик 13. или 14 выдает сигнал переполнения. Таким счетчиком в модели, связанной с начальным узлом моделируемой сети, является счетчик, в который занесен адрес, отличный от адреса начального узла. Импульс переполнения поступает на вход элементов И 7, 6, 8 и 9. При этом, если счетчик 13 переполняется, то импульс переполнения поступает на элементы И 6 и И 8 При переполнении счетчика 14 импульс переполнения поступает на элемент И 7 и И 9. 7 16 Один из этих импульсов проходит соответственно элемент И 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, Одновременно с этим происходит запуск последующих моделей пусковым импульсом аналогично, как было описано ранее. Таким образом происходит выбор моделей, которые определяют кратчайший путь между начальным и конечным узлами ести. ЧислоимпульсовШ поступившее на вход 1 этих моделей, определяет величину этого пути. Рассматриваемая модель обеспечивает определение кратчайшего пути в неориен„тированных графах с большей точностью, чем устройства аналогичного- назначения. Формула изобретения Модель двунаправленной ветви, -содержащая формирователь веса ветвей, первый вход которого является первым входом модели, счетчики, входы которых объ773единены и являются вторым входом модели, выходы счетчиков подключены соответственно к первым входам первого и второго элементов И, выход третьего элемента И через первый триггер соединен с первыми входами четвертого и пятого элементов И, второй вход которог подключен к выходу второго триггера, и элементы ИЛИ, отличающееся тем, что, с целью расширения функционап ных возможностей за счет определения кратчайшего пути в неориентированных графах, Б модель введены дополнительно триггеры, элемент И и дополнительный формирователь веса ветви, вход которого является первым входом модели, выходы формирователей веса ветви подключены соответственно ко входами первого элемента ИЛ1-1, выход которого соединен с первым входом третьего элемента И, вто рой вход которого подключена к выходу второго триггера, соединенному со вторы ми входами первого и,второго элементов И, третьи входы которых соединены и являются третьим входом модели, четвер тые входы первого и второго элементов И подключены соответственно к первым выходам третьего и четвертого триггеров входы которых соединены соответственно с выходами второго и первого элементов

Г

ДЛi г5

П . 8 И, вторые выходы третьего и четвертого триггеров подключены ко вторым входам формирователей веса ветви и соответственно к первым входам шестого и седьмого элементов И, вторые входь которых соединены и являются третьим входом модели, третьи входы шестого и седьмого элементов И подключеньг к выходам счетчиков 13 и 14, выходы шестого и седьмого элементов И соединены со входами второго элемента 11 ИЛИ, выход которого подключен ко входу второго триггера 16, первый вход восьмого элемента И соединен с выходом первого триггера, вторые входы четвертого и восьмого элементов И подключены соответственно к выходам счетчиков, выходы четвертого и восьмого элементов И соединены со входами третьего элемента ИЛИ, выходы пятого элемента И, третьего элемента ИЛИ являются соответственно первым и вторым выходами модели. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР по заявке № 2383712/18-24, кл. Gi 06 F 15/2О, 1976. 2.Авторское свидетельство СССР № 47О811, кл. Q 06 F 15/20, 1973 (прототип).