Всеооюзная патго-тсш”кнаяб1блиот1на

О П И С А Н И Е 305484ИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Фоез Советоких Социалистических РеспубликЗависимое от авт. свидетель аМПК б 06 д 7/34 явлено 08,Х 11,1969 ( 1383901/18-24 с присоединением заяПриоритет комитет по делам изобретений и открытий прн Совете Министров СССР. Васильев, А. одоиов и А. И. Леви Институт кибернетики АН аинской СС явитель СТРОЙСТВО ДЛЯ МОДЕЛИРОВ ПУТЕЙ НА ГРИЯ ЭКСТРЕМАЛЬНЬфЕ Изобретение относится к области вычислительной техники.Известны устройства для моделированияэкстремальных путей на графе, содержащиесоединенные в соответствии с топологией графа модели ветвей на счетчиках, триггерах,логических схемах НЕ, И, ИЛИ и инверторах,Все известные устройства имеют ограниченные функциональные возможности. 10Цель изобретения - расширение функциональных возможностей устройства.В предлагаемом устройстве это достигается тем что в нем выход счетчика в каждоймодели ветви соединен с одним из входов 15схемы И, выход которой соединен с единичным входом триггера, подключенного единичным выходом к одному из входов второй схемы И и единичному входу второго триггера, нулевой выход которого соединен с одним из входов третьей схемы И, подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выходтретьей схемы И соединен со входом инвертора, выход которого соединен с выходным полюсом модели ветви; единичный выходвторого триггера соединен со входом четвертои схемы И, подключннои ьгор.м входом к шине управления решением задачи ократчаишем пути, а выходом к одному из по люсов диода, другои полюс которого соединен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертора, выход которого соединен со входами второй и пятой схем И, причем выход второй схемы И подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу", второй вход пятой схемы И соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера,На чертеже приведена схема устройства.Устройство содержит модели ветвей на инверторах 1 - 3, двухвходовых схемах И 4 - 8, счетчике 9, триггерах 10, 11, диоде 12.Устройство работает следующим образом, Модели ветвей соединяются между собой полюсами 13 и 14 в соответствии с топологией графа.В счетчик 9 модели ветви предварительно заносится число импульсов, дополняющее длину ветви до полной емкости счетчика. 1 риггеры 10 и 11 находятся первоначально в нулевом состоянии, и на полюсах 13 и 14 нулевой потенциал. В некоторый момент времени на полюсе 13 модели ветви появится сигнал разрешения отсчета числа импульсов, равного числу импульсов максимальной емкости счетчика 9. этот сигнал откроет схему 5 совпадения и в счетчик 9 начнут поступать5 1 О 15 импульсы тактовой серии через полюс 16. При появлении на выходе счетчика 9 импульса переполнения триггеры 10 и 11 установятся в единичное состояние, Сигнал с единичного выхода триггера 10 поступает та один из входов схемы 4 совпадения,Сигнал с нулевого выхода триггера 11 поступает на один из входов схемы 6 совпадения, второй вход 16 которой управляется сигналами с шины управления решением задачи о длиннейшем пути. Сигнал с выхода этой схемы совпадения поступает на вход схемы совпадения, которая образуется соединением инверторов 2 полюсами 14 моделей ветвей, сходящихся в одной из вершин графа.Сигнал с единичного выхода триггера 11 поступает на один из входов другой схемы б совпадения, второй вход 17 которой управляется сигналами с шины управления решением задачи о кратчайшем пути, Сигнал с выхода этой смемы 4 совмадения поступает на вход схем 1 И,ДИ; которая образуется соединецием диада 12.с, полюсом 14 модели ветви.В случае решения задачи о длиннейшем пути на вход 16 подается разрешающий потенциал, а на вход 17 решением задачи о кратчайшем пути - запрещающий.При этом на полюсе 14 появится разрешающий потенциал только тогда, когда все триггеры 11 моделей ветвей, входящих в одну вершину, установятся в единичное состояние. Если же на выходном полюсе 14 модели ветви еще не появился разрешающий сигнал, то инвертор 3 дает разрешающий сигнал на схемы совпадения 7 и 8, На второй вход 18 схемы 8 совпадения поступают сдвинутые импульсы тактового генератора, т. е, все установившееся в единичное состояние до появления на полюсе 14 разрешающего потенциала триггеры 10 будут установлсны в нулевое состояние выходным сигналом схем 8 совпадения. Те же триггеры 10, которые установились в единичное состояние, с появлением сигнала на полюсе 14 останутся в единичном состоянии, так как будет снят разрешаюгций потенциал со входа схемы 8. Таким образом, состояния триггеров 10 моделей ветвей будут индицировать дерево длиннейших путей с корнем в начальной вершине,го 25 зо 35 4 о 45 50 При решении задачи о кратчайшем пути разрешающий потенциал подается на вход 17 модели ветви, а запрещающий - на вход 16,В этом случае, как только триггеры 10 и 11 одной из моделей ветвей, входящих в одну вершину графа, установятся в единичное состояние, на полюсе 14 появится разрешающий потенциал. Тем самым будет снят разрешающий потенциал со входов схем совпадения б и 8, и триггеры 10 и 11 остальных моделей ветвей не установятся в единичное состояние. Таким образом, в этом случае находящиеся в единичном состоянии триггеры 10 моделей ветвей будут индицировать дерево кратчайших путей с корнем в начальной вершине. Предмет изобретенияУстройство для моделирования экстремальных путей на графе, содержащее соединенные в соответствии с топологией графа модели ветвей на счетчиках, триггерах, логических схемах НЕ, И, ИЛИ и инверторах, отличающееся тем, что, с целью расширения функциональных возможностей, в нем выход счетчика в каждой модели ветви соединен с одним из входов схемы И, выход которой соединен с единичным входом триггера, подключенного единичным выходом к одному из входов второй схемы И и единичному входу второго триггера, нулевой выход которого соединен с одним из входов третьей схемы И, подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выход третьей схемы И соединен со входом инвертора, выход которого соединен с выходным полюсом модели ветви; единичный выход второго триггера соединен со входом четвертой схемы И, подключенной вторым входом к шине управления решением задачи о кратчайшем пути, а выходом к одному из полюсов диода, другой полюс которого соединен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертора, выход которого соединен со входами второй и пятой схем И, причем выход второй схемы И подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу; второй вход пятой схемы И соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера.305484И- ИСоставитель Г. Сорокинактар Ю. Полякова Техред 3. Н. Тараненко Корректор Т. А. Китае Заказ 2511/12 Тираж 473 Подписи ЦНИИПИ Комитета по делам изобретений и открытий прп Совете Министров ССС Москва, Ж, Раушская наб., д. 4 г 5биография, пр. Сапунова, 2