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

4708 И СПИСАНИЕ ИЗОБРЕТЕН ЙЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУСова Советских Социалистических Республик(23) ПриоритетОпубликовано 15.05.75, Бюллетень18Дата опубликования описания 21.08,75 1) М. Кл. 6 06 15/2 Государственный комитет Совета Министров СССР 1.326 (088.8 3) У делам изоорвтени и открытий 2) Авторы изобретения А, Г. Додонов и В, В. Хаджинов Институт электродинамики АН Украинской ССР(54) МОДЕЛЬ ВЕТВИ ГРА Изобретение относится к области вычислительной техники, в частности, к моделирующим устройствам и может быть использовано при построении цифровых специализированных машин для решения задач исследования операций.Известна модель ветви графа, содержащая триггер, формирователь временного интервала, счетчики начального и конечного адреса и элементы И, Один вход первого элемента 10 И соединен с выходом формирователя временного интервала, первый вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом счетчика начального адреса. Выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов И. Второй вход третьего элемента И соединен со вторым входом второго элемента И, третий вход которого соединен с выходом триггера, а 20 выход счетчика начального адреса соединен со входом модели.Недостатком известной модели является необходимость затрат большого количества оборудования.25Цель изобретения - сокращение оборудования.Поставленная цель достигается тем, что модель ветви графа содержит второй триггер, вход которого соединен с выходом первого 30 элемента И, другой вход которого и первьш вход пятого элемента И соединены с выходом первого триггера. Второй вход пятого элемента И соединен с выходом второго триггера и со вторым входом четвертого элемента И. Вторые входы формирователя временного интервала и третьего элемента И соединены с соответствующими входами модели ветви, выходы которой соединены с выходами четвертого и пятого элементов И, а вход счетчика конечного адреса соединен со входом счетчика начального адреса.Блок-схема модели ветви представлена на чертеже.Модель ветви графа содержит элементы И 1 - 5, счетчик начального адреса 6, счетчик конечного адреса 7, триггеры 8 и 9, формирователь временного интервала 10, модель ветви 11, блок автоматического формирования топологии 12, блок управления 13, генератор импульсов 14, элементы ИЛИ 15 - 18, элементы И 19 и 20, инвертор 21, входы 22 - 24 модели ветви, выходы 25 и 26 модели ветви, группы входов 27 и 28 блока автоматического формирования топологии 12, входы 29 - 32 блока автоматического формирования топологии, выходы 33 - 35 блока автоматического формирования топологии, выходы 36 и 37 генератора импульсов 14, вход 38 и выходы 39 и 40 блока управления 13,Модель ветви работает следующим образом, Генератор импульсов 14 вырабатывает на своих выходах 36 и 37 импульсы ГИ, и 1 И 2, сдвинутые относительно друг друга.Г 1 редварительно в счетчики начального и конечного адресов 6 и 7 заносятся соответственно адреса начального и конечного узлов моделируемой ветви графа.В формирователь временного интервала О заносится длительность ветви, а триггеры 8 и 9 устанавливаются в нулевое состояние.Для запуска модели ветви 11 блок автоматического формирования топологии 12 подает на вход 23 модели ветви 11 импульсы серии ГИ, до тех пор, пока на выходе счетчика начального адреса б не появится сигнал. В этот момент блок управления 13 прекращает подачу импульсов серии ГИ, из блока автоматического формирования топологии 12 на вход 23 и одновременно с импульсом ГИ 2 подает на вход 22 модели ветви 11 через элемент ИЛИ 18 пусковой импульс из блока автоматического формирования топологии 12. Пусковой импульс со входа 22 поступает на второй вход элемента И 2. Сигнал с выхода триггера 9 поступает на третий вход элемента и 2. Если модель ветви 11 принадлежит ветви, исходящей из начального узла, сигнал с выхода счетчика начального адреса б поступает на первый вход элемента И 2. Выходной сигнал элемента И 2 разрешает для формирователя временного интервала 10 счет импульсов серии ГИ поступающий по входу 24 из блока автоматического формирования топологии 12. Отсчитав, число импульсов, пропорциональное длительности данной ветви, формирователь временного интервала 10 выдает сигнал, который поступает на первый вход элемента И 1. 11 ри наличии на втором входе элемента И 1 разрешающего сигнала с выхода григгера 9, сигнал с выхода этого элемента устанавливает в единичное состояние триггер 8. Сигнал с единичного выхода триггера 8 поступает на первый вход элемента И 5 и при наличии разрешающего сигнала на втором входе элемента И 5 с выхода триггера 9, сигнал с выхода элемента И 5 по выходу 25 поступает в блок автоматического формирования топологии 12 на один из входов группы входов 27 элемента ИЛИ 15, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже. Пройдя через элемент ИЛИ 15, сигнал поступает на вход инвертора 21, который вырабатывает запрет на одном из входов элемента И 20, Второй вход элемента И 20 соединен со входом 31 и далее с выходом 36 генератора импульсов 14, поэтому серия импульсов ГИ, больше не поступает на вход 24 модели ветви 11. Одновременно с выхода элемента ИЛИ 15 на один из входов элемента И 19 поступает разрешение, и через элемент И 19, второй вход которого соединен со входом 32 и далее - с выходом 37 генератора импульсов 14,5 10 15 20 25 30 35 40 45 50 55 60 65 4серия импульсов ГИ 2, пройдя элемент ИЛИ ,о, поступает по выходу 34 на вход 23 модели ветви 11.Серию импульсов 1 И 2 начинают считать одновременно счетчики начального и конечного адресов о и 7. Сигнал переполнения с выхода счетчика конечного адреса 7 поступает на входы элсментов И 3 и 4. Если данная ветвь закончилась, то на втором входе элемента И 4 имеется разрешающий сигнал с единичного триггера 8, и сигнал переполнения счетчика конечного адреса 7, пройдя через элемент И 4, поступит по выходу 26 в блок автоматического формирования топологии 12 на один из входов группы входов 28 элемента ИЛИ 17, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже, Выходной сигнал элемента ИЛИ 17 блока автоматического формирования топологии 12, пройдя через элемент ИЛИ 18, поступает через вход 22 модели ветви 11 на входы элементов И 2 и 3. Одновременное появление сигнала на входе 22 и выходе счетчика конечного адреса 7 свидетельствует о том, что данная ветвь закончилась ранее других ветвей, входящих в узел, адрес которого записан в счетчике конечного адреса , Так как счетчики начального и конечного адресов 6 и 7 считают импульсы одновременно, то на выходе счетчика начального адреса б модели ветви 11 и других моделей ветвей, исходящих из рассматриваемого узла, будут разрешающие потенциалы. В модели ветви 11 этот потенциал поступает на вход элемента И 1. И если на входе 22 имеется в этот момент разрешающий потенциал, то выходной сигнал элемента И 1 модели ветви 11, других моделей ветвей, исходящих из рассматриваемого узла, подготавливает формирователь временного интервала 10 для отсчета импульсов, поступающих на вход 24.Сигналы с выхода счетчика конечного адреса 7 поступают на вход элемента И 3 при наличии разрешения на входе 22. Во всех моделях ветвей, входящих в узел графа, выходной сигнал элемента И 3 устанавливает в единичное состояние триггер 9, и выходной сигнал триггера 9 запрещает прохождение сигнала с единичного выхода триггера 8 через э цемент И 5 на соответствующий выход 25 и запрещает установку в единичное состояние триггера 8 с выхода элемента И 1, если в модели ветви 11, входящей в данный узел, счет импульсов закончился позже.Импульсы серии ГИ, поступают на вход 23 модели ветви 11 до тех пор, пока на любом из входов группы входов 27 блока автоматического формирования топологии 12 присутствует сигнал. Таким образом, в случае одновременного окончания работы блоков-моделей ветвей, входящих в разные узлы графа, каждый из них опрашивается. 11 осле того, как опрашиваются все модели ветвей, в которых закончено формирование временного интервала, схема ИЛИ 15 блока автоматического фор. Сеаоаа едрс; Г. Подугуппна 1;(,01 ео 1 г 1. А,и едсп(то ) Изд, Ла 144 И 1 с сгдазст оситсг по дела; из Москва, Ж:1,о паз 1986/10Ц 111: и;пп ос Типограри, п . Сапупоза, 2 мирования топологии 12 запрещает подачу импульсов Г 1 Л 2 на входы 23 и разрешает поступление импульсов ГИ, на входы 24.При появлении сигнала на входе 22, фиксирующего окончание какой-либо ветви, входящей в конечный узел графа, блок управления 13 прекращаст работу.Суммарное количество импульсов, поступившее по входу 24 начала счета, равно величине кратчайшего пути. Единичный выход триггера 8 модели ветви 11 индуцирует принадлежность ветви дереву кратчайших путе 1,Модель ветви графа, содержащая триггер, формирователь временного интервала, счетчики начального и конечного адресов и элементы И, причем один вход первого элемента И соединен с выходом формирователя временногоо интервала, первый вход которого соединен с выходом второго элемента И, гсрвый вход которого соединен с выхода: с етчи -ка начального адреса, выход счетчика конечного адреса соединен с первыми входами третьего и четвертого элементов И, второй вход третьего элемента И соединен со вто рым входом второго элемента И, третийвход которого соединен с выходом триггера, а вход счетчика начального адреса соединен со входом модели, отличающаяся тем, что, с цельо сокращения оборудования, она 1 О содеркит второй триггер, вход которого соединен с выходом первого элемента И, второй вход которого и первый вход пятого элемента 1 Л соединены с выходом первого триггера, второй вход пятого элемента И соеди нен с выходом второго триггера и со вторымвходо., четвертого элс.пента 11., вторые входы формирователя временного интервала и третьего элемента И соединены с соответствующими входами модели ветви, выходы 20 которой соединены с выходами четвертого ипятого элезентов И, а вход счетчика конечного адреса соединен со входом счетчика на; а,";.и ого адреса.