ВСЕООЮЗНАЯ ПАТ?Г^О-ТСШ"КНАЯ'Б!'1БЛИОТ1'НА Советский патент 1971 года по МПК G06G7/122 

Изобретение относится к области вычислительной техники.

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

Все известные устройства имеют ограниченные функциональные возможности.

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

В предлагаемом устройстве это достигается тем что в нем выход счетчика в каждой модели ветви соединен с одним из входов схемы «И, выход которой соединен с единичным входом триггера, подключенного единичным выходом к одному из входов второй схемы «И и единичному входу второго триггера, нулевой выход которого соединен с одHHjvi из входов третьей схемы «И, подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выход третьей схемы «И соединен со входом инвертора, выход которого соединен с выходным полюсом модели ветви; единичный выход второго триггера соединен со входом четвертой схемы «И, подключенной вторым входом к шине управления рьшениел задачи о кратчайшем пути, а выходом к. одному из полюсов диода, другой полюс которого соедипен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертора, выход которого соединен со входами второй и пятой схем «И, причем выход второй схемы «И подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу; второй вход пятой схемы «И соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера.

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

Устройство содерлчит модели ветвей на инверторах /-3, двухвходовых схемах «И 4- 8, счетчике 9, триггерах 10, 11, диоде 12.

Устройство работает следующим образом. Модели ветвей соединяются между собой полюсами 13 и 14 в соответствии с топологией графа.

В счетчик 9 модели ветви предварительно заносится число импульсов, дополняющее длину ветви до полной емкости счетчика. Триггеры 10 и 11 находятся первоначально в нулевом состоянии, и на полюсах 13 и 14 нулевой потенциал. В некоторый момент времени на полюсе 13 модели ветви появится сигнал разрешения отсчета числа импульсов, равного числу импульсов максимальной емкости счетчика У. Этот сигнал откроет схему 5 совпадения и в счетчик 9 начнут поступать

импульсы тактовой серии через полюс 15. При появлении на выходе счетчика 9 импульса переполнения триггеры 10 и 11 установятся в единичное состояние. Сигнал с единичного выхода триггера 10 поступает на один из входов схемы 4 совпадения.

Сигнал с нулевого выхода триггера 11 поступает на один из входов схемы 6 совпадения, второй вход 16 которой управляется сигналами с шины управления регаением задачи о длиннейшем пути. Сигнал с выхода этой схемы совпадения поступает на вход схемы совпадения, которая образуется соединением инверторов 2 полюсами 14 моделей ветвей, сходящихся в одной из вершин графа.

Сигнал с единичного выхода триггера 11 постунает на один из входов другой схемы 6 совпадения, второй вход 17 которой управляется сигналами с шины управления решением задачи о кратчайшем пути. Сигнал с выхода -этой -4 соввадения поступает на вход -cx-e-MjjU . которая образуется сое.а,ине,9ие,1У1 диода -/2 .f, полюсом 14 модели ветви. - .

В случае решения задачи о длиннейшем пути на вход 16 подаете разрешающий нотенциал, а на вход 17 решением задачи о кратчайшем пути - запрещающий.

При этом на полюсе 14 появится разрешающий потенциал только тогда, когда все триггеры // моделей ветвей, входящих в одну вершину, установятся в единичное состояние. Если на выходном полюсе 14 модели ветви еще не появился разрешаюимй сигнал, то инвертор 3 дает разрешающий сигнал на схемы совпадения 7 и 8. На второй вход 18 схемы 8 совнадення поступают сдвинутые импульсы тактового генератора, т. е. вее установившееся в единичное состояние до появления на полюсе 14 разрешаюшего потенциала триггеры 10 будут установлены в нулевое состояние выходным сигналом схем 8 совпадения.

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

При решении задачи о кратчайшем пути разрешающий потенциал нодается на вход 17 модели ветви, а запрещающий - на вход 16.

В этом случае, как только триггеры 10 и // одной из моделей ветвей, входящих в одну верщину графа, установятся в единичное состояние, на полюсе 14 появится разрешающий потенциал. Тем самым будет снят разрешаюший потенциал со входов схем совпадения и 5, и триггеры 10 } 11 остальных моделей ветвей не установятся в единичное состояние. Таким образом, в этом случае находящиеея в единичном состоянии триггеры 10 моделей ветвей будут индицировать дерево кратчайших путей с корнем в начальной вершине.

Предмет изобретения

Устройство для моделирования экстремальных путей на графе, содержащее соединенные в соответствии с топологией графа модели ветвей на счетчиках, триггерах, логических схемах «НЕ, «И, «НЛИ и инверторах, отличающееся тем, что, с целью расширения функциональных возможностей, в нем выход счетчика в каждой модели ветви соединен с одним из входов схемы «И, выход которой соединен с единичным входом триггера, подключенного единичным выходом к одному из входов второй схемы «И и единичному входу второго триггера, нулевой выход которого соединен с одним из входов третьей схемы «PI, подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выход третьей схемы «И соединен со входом инвертора, выход которого соединен с выходным полюсом модели ветви; единичный выход второго триггера соединен со входом четвертой схемы «Н, нодключенной вторым входом к шине унравления решением задачи о кратчайшем пути, а выходом к одному из полюсов диода, другой полюс которого соединен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертора, выход которого соединен со входами второй и пятой схем «И, причем выход второй схемы «Н подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу; второй вход пятой схемы «Н соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера.