Устройство для исследования графов Советский патент 1987 года по МПК G06G7/122 

ределения приоритетов моделей узлов. Устройство для исследования графов содержит генератор импульсов 2, блок управления 3, модели узлов 5, модели ветвей 1, блок индикации 4, наборное поле 6, первый и второй коммутаторы 7, 8, Преимуществами Данного устройства является расширение функциональных возможностей за счет введения дополнительных первого и второго коммутаторов и изменения структурных связей между элементами, что позволяет решать качественно новый класс задач сетевого планирования и управления, в которых требуется определить экстремальные пути на сети (последовательность работ),

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

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

На фиг. 1 представлена блок-схема предлагаемого устройства;на фиг.2 - схема модели ветви; на фиг. 3 - схема блока управления; на фиг. 4 - схе-20 ма блока индикации на фиг. 5 - схема модели узла; на фиг. 6 - схема .первого коммутатора; на фиг. 7 - схема второго коммутатора; на фиг. 8 - схема сравнения; на фиг. 9 - схема пер- вого узла памяти; на фиг. 10 - схема узла пуска; на фиг. 11 - схема второго узла памяти.

Устройство для исследования графов (фиг. 1) содержит модели 1 вет- -30 вей, генератор 2 тактовых импульсов, блок 3 управления, блок 4 индикации, модели 5 узлов, наборное поле 6, первый 7 и второй 8 коммутаторы.

последовательно преобразующие исходное состояние в виде п-разрядного двоичного кода в конечное состояние (п-разрядный двоичный код). При этом преобразование кода моделируется с помощью узлов, а передача кода моделируется с помощью ветвей. Это позволяет .использовать предлагаемое устройство для построения и исследо-; вания адаптивных и интеллектуальньпс систем управления, имеющих сложную сет.евую структуру, кроме этого, в данном устройстве автоматически определяются исходная и конечная моде- ;ли узлов экстремальных путей с указанием приоритета модулей узлов. 1 з.п. ф-лы, 11 ил.

Модель 1 ветви (фиг. 2) содержит счетчик 9 импульсов, дешифратор 10, триггер 11, группу триггеров 12, элемент И 13, группу элементов И 14, первый 15 и второй 16 элементы ИЛИ, элемент 17 задержки, группу информационных входов 18, входы установки в О 19j, запуска 19,j и тактовых импульсов 19з , группу информационных выходов 20, группу приоритетных выходов 21,.группу информационных выходов 22 и установочный выход 23.

Блок 3 управления (фиг. 3) содержит выходы разрешения сброса , разрешения начала работы 19 и тактовых импульсов 19з группу входов 23 установки нуля, коммутационный элемент 24 (Сброс), узел 25 пуска, триггер 26, схему 27 сравнения, первый 28 и второй 29 элементы И, первый 30 и второй 31 счетчики импульсов, первьй 32 и второй 33 дешифраторы, элемент И-НЕ 345 первый 35 и второй 36 элементы задержки, первьй 37 и второй 38 элементы ИЛИ, умножитель 39 частоты, первый 40 и второй 41 узлы памяти, вход 42 тактовых импульсов, группу информационных входов 43, группу выходов 44 разрешения индикации адреса модели узла конца пути, группу выходов 45 разрешения индикации адреса модели узла начала пути, группу выходов 46, выход 47,

разрешения индикации и выход 47 окончания работы.

Блок 4 индикации (фиг. 4) содержит цервый 48 и второй 49 коммутаторы, первую группу 50 светодиодов, cocTOHtilyro из первой 5бх и второй 50 подгрупп светодиодов, содержащих по k светодиодов, причем у второй подгруппы 50 светодиодоБ первой группы аноды соответствуют входам моделей , 0 узлов, а катоды - выходам моделей УЗЛОВ, вторую группу 51 светодиодов, содержащую k подгрупп светодиодов, третий светодиод 52, источник 53 постоянного тока, транзисторный ключ t5 54, обмотку реле 55, нормально разомкнутые контакты 56 реле 55, источник 57 напряжения и группу из k сопротивлений 58.

Модель 5 узла (фиг. 5) содержит 20 дизъюнктивную программируемую логическую матрицу, состоящута из группы нагрузочных сопротивлений 59 и группы диодов 60, группу элементов ИЛИ 61, первую 62 и вторую 20 группы инфор- мационных входов и группу выходов 18.

Первьй коммутатор 7 (фиг. 6) представляет собой п-разрядный кс&1мута- тор и содержит группу из п параллельно соединенных одноразрядных коммута- -30 торов 63, группу управляющих входов

44,группу информационных входов 22 и грзшпу выходов 43. Каждый коммутатор 63 содержит k входов адресования, выход и k информационных входов. 35 Группа информационных входов состоит

из k подгрупп входов, а каждая подгруппа - из п входов.

Второй 8 коммутатор (фиг. 7) представляет собой п-разрядный коммутатор О и Ьодержит группу из п параллельно соединенных одноразрядных коммутаторов 64, группу .управляющих входов

45,группу информационных входов и группу выходов 62. Каждьш коммутатор 45 64 содержит k входов адресования, информационный вход и k выходов. Группа выходов 62 состоит из k подгрупп выхо дов, а каждая погруппа - из п выходов.

.50

Схема 27 сравнения (фиг. 8) содержит группу элементов РАВНОЗНАЧНОСТЬ 65, элемент И 66, первую 43 и вторую 68 группы входов, третий вход 67 и выход 47( . °55

Первый 40 узел з: амяти (фиг. 9) содержит группу триггеров 69, группу элементов И 70, элемент 71 задержки.

первый 72 и второй 192. БХОДЫ, -группу входов 73 записи и группу выходов 46

Узел 25 пуска (фиг. 10) содержит первый 74 и второй 75 элементы ИЛИ, счетчик 76 импульсов, элемент 77 задержки, первый 78 и второй 79 триггеры, первый 80, второй 81 и третий 82 элементы И, коммутационньш элемент 83 (Пуск), вход 42 тактовых импульсов, вход 47, разрешения начальной установки, дополнительный вход 84 установки нуля, вход 85 разрешения промежуточной установки, группу входов 23 установки нуля, выход 67 разрешения сравнения, выход 86 разрешения счета и выход 19 разрешения начала работы.

Второй узел 41 памяти (.фиг. 11) додержит грзшпу триггеров 87, первьй 72, группу входов 88 записи и группу выходов 68. При этом 72 пер- ВЫ.Й вход соединен с входами установки нуля триггеров 87, входы установки единицы которых подключены к группе входов 88, а прямые выходы триггеров 87 подключены к группе выходов 68.

Устройство работает следующим образом.

В исходном состоянии, перед решением задачи на устройстве, светодио- ды второй подгруппы 50,2; первой группы блока 4 индикации соединены между собой в соответствии с топологией графа, а модели 1 ветвей и модели 5 узлов также скоммутированы между собой на наборном поле 6 в соответствии с топологией графа. Наборное поле 6 представляет собой совокупность, например пары гнездо-штеккер. Нажатием коммутационного элемента 24 Сброс в блоке 3 управления производится сброс всех триггеров и счетчиков устройства в исходное нулевое состояние, так как при этом нормально разомкнутые контакты коммутационного элемента 24 замыкаются, и единичные импульсы с выхода гене- ратора 2 поступают на входы 72 пер- вого 40 и второго 41 узлов памяти, на соответствующие входы первого 37 и второго 38 элементов ИЛИ, а так-, же на входы установки нуля второго счетчика 31 и триггера 26 блока 3 управления. С входа 72 единичные импульсы поступают на входы установки нулей триггеров 69 и 87 первого 40 и второго 41 узлов памяти, поэтому

триггеры устанавливаются в нулевое состояние. С вьпсода первого элемента ИЛИ 37 единичные импульсы поступают через вход 19 всех моделей 1 ветвей на (п+1)-й вход элемента ИЛИ 16 и входы установки нулей группы триггеров 12 и счетчика 9, а с выхода элемента ИЛИ 16 единичные импульсы поступают на вход установки нуля триггера 1.1 и выход 23 модели 1 ветви. С выхода 23 через первый элемент ИЛИ 74 единичные импульсы поступают на входы установки нуля счетчика 76 и первого триггера 78 узла 25 пуска, С выхода элемента ИЛИ 38 единичные импульсы поступают через вход 84 узла 25 пуска на вход установки нуля триггера 79.

Триггер 78 находится в нулевом состоянии, поэтому на выходе 67 узла 25 пуска имеется нулевой потенциал, которьш поступает на (п+1)-й вход элемента И 66 схемы 27 сравнения, и на выходе элемента И 66 имеется нулевой потенциал. При этом транзисторный ключ 34 блока 4 индикации-закрыт, поэтому обмотка реле 55 обесточена и контакты 56 разомкнуты, а значитJ светодиоды второй подгруппы 502 первой группы закрыты и индикация отсутствует, Светодиод 52 и вторая группа.51 светодиодов также закрыты, так как триггер 26 блока 3 управления и счетчики 9 модели 1 ветвей находятся в нулевом состоянии. Затем на входы 73 и 88 записи соответственно первого 40 и второго 41 узлов памяти оператором заносятся двоичные коды исходного и конечного состояний исследуемого графа соот- ветстйенно, а на вход установки вто)5

20

разомкнутые контакты замыкаются, и единичные импульсы с выхода генератора 2 импульсов поступают на вход установки единицы триггера 79 и перс вый вход элемента И 82, с выхода которого через элемент ИЛИ 75 единичные импульсы поступают на входы ус- тановки едини цы триггеров 11 всех моделей 1 ветвей и вход элемента 71

JO задержки, представляющий собой диф (ференцирующую резистивно-емкостную . цепочку, первого узла 40 памяти. На прймом выходе триггера 11 устанавливается единичный потенциал, который, поступая на первый вход элемента И 13, разрешает поступление единичны импульсов с-выхода умножителя 39 час тоты через элемент И 13 на счетный вход счетчика 9 импульсов.

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

25 вторые входы элементов И 70, что при водит к появлению единичных импульсов на выходе тех элементов И 70, на первые входы которых поступает единичный сигнал с прямых выходов триггеров 69. При этом время задержки передачи единичного импульса элемен- том 71 задержки должно быть не меньше суммы времени задержки переключения вторых счетчика 31, дешифратора 33 и коммутатора 8.

С выхода первого узла 40 памяти

двоичный код исходного состояния ПОС

тупает на группу входов второго коммутатора 8, с группы выходов которого двоичный код поступает на группу входов 62 той исходной модели 5 уз- лов, адрес которой записан во втором

30

35

40

рого С1 етчика 31 оператором подается последовательный двоичный код адреса исходной модели 5 узла. Номер исходной модели 5 узла индицируется с помощью первой подгруппы 50, светодиодов первой группы блока 4 Индикации, и при появлении единичного потенциала на соответствующем выходе

/,. оt;n импульсы, которые поступают через

45 группы выходов блока 3 управления

соответствующий светодиод подгруппы 50 открывается.

Пусть в момент времени t, происходит запуск устройства нажатием комму- устанавливаются единичные сигналы, тационного элемента 83 Пуск в уз-которые поступают на входы элемента ле 25 пуска. При этом нормально-замк-ИЛИ 15, и на его выходе появляется нутые контакты коммутационного эле-единичный сигнал, который через элемента 83 размыкаются, а нормальномент 17 задержки, представляющий сосчетчике 31 блока 3 управления. На выходах соответствующих элементов 5 ИЛИ 61 пЬявляются единичные импульсы поступающие на аноды соответствующих диодов 60, и на выходых 18 модели 5 узла, связанных с катодами этих диодов 60, также появляются единичные

наборное поле 6 на группу входов 18 соответствующей модели 1 ветви. Поэтому в модели 1 ветви на прямых выходах соответствзпощих три1;геров 12

разомкнутые контакты замыкаются, и единичные импульсы с выхода генератора 2 импульсов поступают на вход установки единицы триггера 79 и первый вход элемента И 82, с выхода которого через элемент ИЛИ 75 единичные импульсы поступают на входы ус- тановки едини цы триггеров 11 всех моделей 1 ветвей и вход элемента 71

задержки, представляющий собой диф (ференцирующую резистивно-емкостную . цепочку, первого узла 40 памяти. На прймом выходе триггера 11 устанавливается единичный потенциал, который, поступая на первый вход элемента И 13, разрешает поступление единичных импульсов с-выхода умножителя 39 частоты через элемент И 13 на счетный вход счетчика 9 импульсов.

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

вторые входы элементов И 70, что при водит к появлению единичных импульсов на выходе тех элементов И 70, на первые входы которых поступает единичный сигнал с прямых выходов триггеров 69. При этом время задержки передачи единичного импульса элемен- том 71 задержки должно быть не меньше суммы времени задержки переключения вторых счетчика 31, дешифратора 33 и коммутатора 8.

С выхода первого узла 40 памяти

двоичный код исходного состояния ПОС

тупает на группу входов второго коммутатора 8, с группы выходов которого двоичный код поступает на группу входов 62 той исходной модели 5 уз- лов, адрес которой записан во втором

счетчике 31 блока 3 управления. На выходах соответствующих элементов ИЛИ 61 пЬявляются единичные импульсы поступающие на аноды соответствующих диодов 60, и на выходых 18 модели 5 узла, связанных с катодами этих диодов 60, также появляются единичные

устанавливаются единичные сигналы, которые поступают на входы элемента ИЛИ 15, и на его выходе появляется единичный сигнал, который через элемент 17 задержки, представляющий сонаборное поле 6 на группу входов 18 соответствующей модели 1 ветви. Поэтому в модели 1 ветви на прямых выходах соответствзпощих три1;геров 12

fO

бой. дифференцирующую резистивно-ем- костную цепочку, поступает на входы группы элементов И 14.При этом единичные импульсы появляются на выходе тех элементов И 14, на входы которых пос- тупает единичный сигнал с прямых выходов триггеров 12, Единичные импульсы с выходов элементов И 14 поступают на входы элемента ИЛИ 16 и через наборное поле 6 на группу входов 20 соответствующей модели 5 узла и т.д. При этом на выходе элемента ИЛИ 16 появляется единичный импульс, который поступает на вход установки нуля триггера 11, и на его прямом выходе устанавливается нулевой потенциал, который блокирует поступление единичных импульсов с выхода умножителя 39 частоты через элемент И 13 на счетный вход счетчика 9. С выхода элемента ИЛИ 16 единичный импульс поступает также на соответствующий вход элемента ИЛИ 74 узла 25 пуска, и на выходе элемента ИЛИ 74 появля15

20

ставляющего собой резистивно-емкост ную цепочку, появляется единичный импульс, который поступает на вход установки единицы триггера 78 узла 25 пуска. На прямом выходе триггера 78 в момент времени t устанавливается единичный потенциал, который поступает на первый вход элемента И 80 и (п+1)-й вход элемента И 66 схемы 27 сравнения. Единичные импул сы с выхода элемента И 81 поступают также на второй вход-элемента И 80, с выхода которого поступают на счет ный вход первого счетчика 30, и в зависимости от количества поступивш импульсов на соответствующем выходе первого дешифратора 32 появляется единичный сигнал. Этот сигнал посту пает на группу входов первого комму татора 7 и определяет адрес модели 1 ветви, группа выходов 22 которой подключена через первьв коммутатор к группе входов 43 схемы. 27 сравнен Таким образом, первый коммутатор 7

ется единичный импульс, который пос последовательно подключает группу тупает на входы установки нулей выходов 22 всех моделей 1 ветвей к

группе входов 43 схемы 27 сравнения I

триггера 78 и счетчика 76 и устанавливает их в нулевое состояние. Затем на счетный вход счетчика 76 поступают импульсы с выхода элемента И 81, первый вход которого подключен к выходу -генератора 2, а на второй вход элемента И 81 поступает единичный потенциал с прямого выхода триггера 79. На выходе счетчика 76 формируется единичньш импульс переполнения только в том случае, если промежуток времени между двумя последовательными единичными импульсами, поступающими на входы 23 элемента.ИЛИ 74, превьшает в 2 раза время f,;- , равное

сумме времен задержки передачи единичного сигнала триггером 12, элементом И .14, первым 15 и вторым 16 элементами ИЛИ и элементом 17 задержки модели 1 ветви и элементом ИЛИ 61 модели 5 узла. При этом единичные импульсы на выходах элементов ИЛИ 16 моделей 1 ветвей последовательно появляются с промежутком времени, равным с, , поэтому появление единичного импульса на выходе счетчика 76. означает, что вычислительный йроцесс, т.е. преобразование двоичного кода в каждой модели 5 узла и передача этого кода каждой моделью 1 ветви сети, завершен, и на вьпсоде элемента 77 задержки, пред

ставляющего собой резистивно-емкост- ную цепочку, появляется единичный импульс, который поступает на вход установки единицы триггера 78 узла 25 пуска. На прямом выходе триггера 78 в момент времени t устанавливается единичный потенциал, который поступает на первый вход элемента И 80 и (п+1)-й вход элемента И 66 схемы 27 сравнения. Единичные импульсы с выхода элемента И 81 поступают также на второй вход-элемента И 80, с выхода которого поступают на счетный вход первого счетчика 30, и в зависимости от количества поступивших импульсов на соответствующем выходе первого дешифратора 32 появляется единичный сигнал. Этот сигнал поступает на группу входов первого коммутатора 7 и определяет адрес модели 1 ветви, группа выходов 22 которой подключена через первьв коммутатор 7 к группе входов 43 схемы. 27 сравнения,. Таким образом, первый коммутатор 7

последовательно подключает группу выходов 22 всех моделей 1 ветвей к

группе входов 43 схемы 27 сравнения. I

Если в момент времени tj появляется единичный сигнал на выходе схемы 27 сравнения, это значит, что двоичный код конечного состояния сети, записанный во втором узле 41 памяти и поступающий на группу входов 68 схемы 27 сравнения, совпадает с двоичным кодом, который поступает на группу входов 43 схемы 27 сравнения, например, с группы выходов 22j i-й модели 1;j ветви. Поэтому на выходах всех элементов РАВНОЗНАЧНОСТЬ 65

устанавливаются единичные сигналы и на выходе элемента И 66 также появляется единичный сигнал, которьй поступает на вход второго элемента 36 задержки, представляющий собой дифференцирующую резистивно-емкостную цепочку. На его выходе появляется единичньш импульс, поступающей на соответствующий вход второго элемента ИЛИ 38, с выхода которого единичный импульс поступает на вход 84 установки нуля триггера 79 узла 25 пуска, и на прямом выходе триггера 79 устанавливается нулевой сигнал, который блокирует элемент И 81. На .его выходе устанавливается нулевой сиг- ,нал, т.е. единичные импульсы на счет- ньй вход первого счетчика 30 не поступают, так как на выходе элемента

И 80 также устанавливается нулевой сигнал, потому что на его второй вход ноступает нулевой сигнал с выхода элемента И 81. При этом период следования импульсов на выходе генератора 2. должен быть больше времени с равного сумме времен задержки передачи единичного сигнала триггера

Если, например, в счетчике 9,- i-й модели 1 ветви записано р импульсо

79, первого 80 и второго 81 элементор

И узла 25 пуска, первого счетчика 30, О (р 1, 2, ,«,, т), то на р-м выходе первого дешифратора 32, второго эле- дешифратора 10; имеется единич- мента 36 задержки, второго элемента ИЛИ 38 блока 3 управ йния, первого (Коммутатора J7. элемента РАВНОЗНАЧНОСТЬ 65 и элемента И 66 схемы 27 сравне- ния. Поэтому в момент времени t в первом счетчике 30 записано i импьт сигнал, который поступает на р-Й анод светодиода i-й подгруппы второй группы светодиодов блока 4 индикадии. При этом светодиод 51« открывается, так как сопротивление фотосопротивления 58 мало из-за топульсоВ;, а значит, выход второго ком- го, что на него попадает световой

мут-атора Л9 блока 4 индикации под- ключ ен к катоду i-ro светодиода второй подгруппы первой групгш светодиодов. Так как на вход 47f транзисторного ключа 54 подается высо- кий положительный потенциал с выхода схемы 27 сравнения, то обмотка реле 55 подключена к источнику 37 напря- жения и контакты 56 замкнуты. Допустим, во второй счетчик 31 записано Ц+1) импульсов, поэтому на Ц+1)-м выходе 45,41 второго дешифратора 33 имеется единичньш сигнал.и группа входов 46 второго коммутатора В подключена, к группе входов 62 ,, (1+1)-й модели 5 узла,, а информа- ционньй вход первого коммутатора 48 блока 4 индикации подключен к (1+1)-му аноду светодиода 30 второй подгруппы первой группы светодиодов. При этом ток от источника 53 тока протекает пoлJ;eпи: выход источника , йнформационньй вход Первого коммутатора 48, анод (i+l)-ro светодиода , последовательная цепочка из светодиодов 50, соединенных между собой в соответствии с топологией исследуемого графа, катод i-ro светодиода 50 , i-й информационный вход второго коммутатора 49, выход второго коммутатора 49, замкнутые контакты 56 и вход источника 53 тока, Светодиоды подгруппы 50,, находящиеся на кратчайшем пути между (1+-1)-и,и i-M светодиодами подгруппы

25

поток излучения светодиода 50{,, и, 20 таким образом, происходит индикация приоритета модели 5; узлов, а фотосопротивления 58, которые не освещены, имеют большое сопротивление. Поз тому величина тока, протекающего в сопротивлении, мала, и светодиоды группы 51, соединенные с этим сопротивлением, закрыты.

При этом содержание счетчика 9 модели 1, ветви определяет приоритет 30 модели узла, и чем больше содер- о жимоё счетчика 9, , тем вьЩге приоритет модели 5; узла. Очевидно, что

приоритет модели 5- узла в рассматриваемом случае на найденном пути

35 самый высокий, а приоритет модели 5,, узла самый низкий, и тогда модель 5,, узла с наименьшим приоритетом соответствует началу найденного пути, а модель 5j узла с наибольшим приори40 тетом - концу найденного пути. При этом чем выше приоритет модели 5 узла, тем меньше расстояние между этой моделью узла и концом пути. Под расстоянием между двумя моделями 5

5 узлов понимается наименьшее количество моделей 1 ветвей, соединяющих чти модели 5 узлов.

После регистрации найденного пути 50 оператор вновь осуществляет запуск устройства для поиска других путей, нажимая коммутационный элемент 83 Пуск в момент времени t. При этом триггер 79 узла 25 пуска устанавлиSOjj , открываютсяJ и излучение с этих55 вается в единичное состояние, и имдиодов попадает на соответствующиепульсы с выхода генератора 2 снова

фотосопротивления 58, а именно: излу-поступают через второй 81 и первый

чение со светодиода 50,; - на фото-80 элементы И на счетньй вход первосопротивление 58j, и так далее,. Та- го счетчика 30, а первый коммутатор

КИМ образом, с помощью светодиодов подгруппы 502 осуществляется индикация моделей 5 узлов, находящихся на найденном пути графа, на котором осуществляется последовательное преобразование исходного состояния в конечное состояние сети,

Если, например, в счетчике 9,- i-й модели 1 ветви записано р импульсов

(р 1, 2, ,«,, т), то на р-м выходе дешифратора 10; имеется единич-

(р 1, 2, ,«,, т), то на р-м выходе дешифратора 10; имеется единич-

пьт сигнал, который поступает на р-Й анод светодиода i-й подгруппы второй группы светодиодов блока 4 индикадии. При этом светодиод 51« открывается, так как сопротивление фотосопротивления 58 мало из-за то

поток излучения светодиода 50{,, и, таким образом, происходит индикация приоритета модели 5; узлов, а фотосопротивления 58, которые не освещены, имеют большое сопротивление. Поз тому величина тока, протекающего в сопротивлении, мала, и светодиоды группы 51, соединенные с этим сопротивлением, закрыты.

При этом содержание счетчика 9 модели 1, ветви определяет приоритет модели узла, и чем больше содер- жимоё счетчика 9, , тем вьЩге приоритет модели 5; узла. Очевидно, что

риоритет модели 5- узла в рассмативаемом случае на найденном пути

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

узлов понимается наименьшее количество моделей 1 ветвей, соединяющих чти модели 5 узлов.

После регистрации найденного пути оператор вновь осуществляет запуск устройства для поиска других путей, нажимая коммутационный элемент 83 Пуск в момент времени t. При этом триггер 79 узла 25 пуска устанавлиto

15

7 продолжает подключать группы выходов 22 моделей 1 ветвей к группе входов 43 схемы 27 сравнения. Если коды на группах входов 43 и 68 схемы 27 сравнения не совпадают, то на ее выходе 47, устанавливается нулевой сигнал, так как на соответствующих выходах элементов РАВНОЗНАЧНОСТЬ 65 присутствуют нулевые сигналы,- -поступающие на входы элемента И 66, поэтому все светодиоды в блоке 4 инди- кации обесточены и индикация не производится ,

Если.первый счетчик 30 накопил k импульсов, то на k-м выходе первого дешифратора 32 устанавливается единичный сигнал, и с приходом (k+U-ro импульса на счетньш вход первого счетчика 30 на k-м выходе 441 первого дешифратора 32 устанавливается ну- 20 левой сигнал. Поэтому на выходе эле- . мента И-НЕ 34 устанавливается еди- ничйьй сигнал, а на выходе первого элемента 35 задержки, представля рщет- го собой дифференцирующую резистивно- емкостную цепь, появляется единичный импульс, который поступает на счетный вход второго счетчика 31, и его содержимое увеличивается на единицу, например становится- равным

пуска, с выхода которого единичньй импульс поступает на входы установки нуля счетчика 76 и триггера 78. Нуле вой сигнал на прямом вьгходе триггера 78 блокирует элемент И 80 и элемент И 66 схемы 27 сравнения, поэтому на их выходах удерживаются нулевые сигналы.

Единичный импульс с выхода первого элемента 35 задержки поступает также на второй вход элемента ИЛИ 75 узла 25 пз ска, а с выхода элемента ИЛИ 75 единичный импульс поступает на входы установки единицы триггеров 11 всех моделей 1 ветвей и вход мента 71 задержки первого узла 40 памяти. Далее вычислительньм процесс протекает как описано смомента времени t до момента tg.

Если в момент времени первый 30 и второй 31 счетчики блока 3 управления накопили по k импульсов, то на вь ходах 44 у, и 45) соответственно первого 32 и второго 33 дешифраторов

25

30

1+2. На (i+2)-M выходе 45i второ го дешифратора 33 устанавливается единичный сигнал, и двоичный код исходного состояния с группы выходов 46 первого узла 40 памяти поступает через второй коммутатор В на группу входов 62 (1+2)-й модели 5 узла. I . При этом, если на выходе схемы

27 сравнения имеется нулевой сигнал, который подается на инверсный вход элемента И 28, то единичный импульс с выхода первого элемента 35 задержки последовательно поступает на вход элемента И 28, ас его выхода - на вход элемента ИЛИ 37, входы установки нуля первого счетчика 30 и триг- геров 12 и (п+1)-й вход элемента ИЛИ 16 всех моделей 1 ветвей. Поэтому первьй счетчик 30 и триггеры 12 устанавливаются в нулевое состояние, а триггер 11 всех моделей 1 ветвей, счетчик 76 и триггер 78 узла 25 пуска также устанавливаются в нулевое

устанавливаются единичные сигналы, С приходом на счетньп вход первого счетчика 30 (k+1)-ro импульса с выхо да генератора 2 на выходе 44 первого дешифратора 32 устанавливается нулевой сигнал и на выходе элемента И-НЕ 34 появляется единичный сигнал, а на выходе первого элемента 35 задержки появляется единичньш импульс, который поступает на первые входы

35 элементов И 28 и 29, счетный вход второго счетчика 31 и второй вход элемента ИЛИ 75 узла 25 пуска. Так. как на второй вход элемента И 29 х поступает едгшичньп сигнал с выхода

40 45|, второго дешифратора 33, то на вы ходе элемента И 29 появляется еди- ничньм импульс, который поступает, на вход установки единицы триггера . 26 и первый вход элемента ИЛИ 38. На

45 .прямом выходе триггера 26 устанавливается единичный сигнал, который поступает на анод светодиода 52 блока 4 индикации и открывает его. TaKiiM о.бразом, осуществляется индикация

50 окончания вычислительного процесса поиска путей на графе. С приходом на счетный вход второго счетчика 31 ()-ro импульс, с выхода первого

элемента 35 задг.ржки на выходе 45-L состояние, так как единичный импульс 55 второго дешифратора 33 устанавлива- с выхода элемента ИЛИ 16 одновременно поступает на вход установки нуля триггера 11 и соответствующий вход .23 первого элемента ИЛИ 74 узла 25

ется нулевой сигнал.

С выхода первого элемента 35 задержки единичньй импульс поступает

5

0

пуска, с выхода которого единичньй импульс поступает на входы установки нуля счетчика 76 и триггера 78. Нулевой сигнал на прямом вьгходе триггера 78 блокирует элемент И 80 и элемент И 66 схемы 27 сравнения, поэтому на их выходах удерживаются нулевые сигналы.

Единичный импульс с выхода первого элемента 35 задержки поступает также на второй вход элемента ИЛИ 75 узла 25 пз ска, а с выхода элемента ИЛИ 75 единичный импульс поступает на входы установки единицы триггеров 11 всех моделей 1 ветвей и вход мента 71 задержки первого узла 40 памяти. Далее вычислительньм процесс протекает как описано смомента времени t до момента tg.

Если в момент времени первый 30 и второй 31 счетчики блока 3 управления накопили по k импульсов, то на вь ходах 44 у, и 45) соответственно первого 32 и второго 33 дешифраторов

устанавливаются единичные сигналы, С приходом на счетньп вход первого счетчика 30 (k+1)-ro импульса с выхода генератора 2 на выходе 44 первого дешифратора 32 устанавливается нулевой сигнал и на выходе элемента И-НЕ 34 появляется единичный сигнал, а на выходе первого элемента 35 задержки появляется единичньш импульс, который поступает на первые входы

элементов И 28 и 29, счетный вход второго счетчика 31 и второй вход элемента ИЛИ 75 узла 25 пуска. Так. как на второй вход элемента И 29 х поступает едгшичньп сигнал с выхода

45|, второго дешифратора 33, то на выходе элемента И 29 появляется еди- ничньм импульс, который поступает, на вход установки единицы триггера . 26 и первый вход элемента ИЛИ 38. На

прямом выходе триггера 26 устанавливается единичный сигнал, который поступает на анод светодиода 52 блока 4 индикации и открывает его. TaKiiM о.бразом, осуществляется индикация

окончания вычислительного процесса поиска путей на графе. С приходом на счетный вход второго счетчика 31 ()-ro импульс, с выхода первого

элемента 35 задг.ржки на выходе 45-L второго дешифратора 33 устанавлива-

ется нулевой сигнал.

С выхода первого элемента 35 задержки единичньй импульс поступает

также на второй вход элемента ИЛИ 75 зла 25 пуска, а с выхода элемента ЛИ 75 единичный импульс поступает а входы установки единицы триггеов 11, устанавливая их в единичное состояние, и вход элемента 71 задержи первого узла 40 памяти, С выхода элемента ИЛИ 38 единичный импульс поступает на вход установки нуля триггера 79, и на его .прямом выходе станавливается нулевой сигнал, который блокирует второй элемент И 81 И с выхода генератора 2 импульсы на выход элемента И 81 не поступают. алее, если на выходе схемы 27 сравнения имеется нулевой сигнал, то элемент И 28 открыт, и единичньй импульс с выхода первого элемента 35 задержки через элемент И 28 и элемент ИЛИ 37 подается на входы установки нуля первого счетчика 30 и триггеров 12 и (п+1)-й вход элемента ИЛИ 1 всех моделей 1 ветвей. Поэтому первый счетчик 30 и триггеры 12 устанавливаются в нулевое состояние, а триггер 11 всех моделей 1 ветвей, счетчик 76 и триггер 78 узла 25 пуска также устанавливаются в нулевое состояние, так как единичный импульс с выхода элемента ИЛИ 16 одновременно Поступает на вход установки нуля триггера 11 и соответствующий вход 23 первого элемента ИЛИ 74 узла 25 пуска, с выхода которого единичный импульс поступает на входы установки нуля счетчика 76 и первого триггера 78, Нулевой сигнал на прямом выходе триггера 78 блокирует первый элемент И 80 и элемент И 66 схемы 27 сравнения, поэтому на их выходах удерживаются нулевые сигналы,

Таким образом, все триггеры и счетчики устройства устанавливаются в нулевое состояние за исключением триггеров первого 40 и второго 41 узлов памяти и триггера 26 блока 3 управления, которые сбрасываются в нулевое состояние нажатием коммутационного элемента 24 Сброс блока 3 управления.

При этом выбор кратчайшего и наиболее длинного путей в исследуемой сети може.т быть осуществлен оператором путем сравнения приоритетов конечных моделей 5 узлов найденных путей. Формула изобретения

1, Устройство для исследования графов, содержащее генератор тактовых импульсов, блок управления, груп- пу моделей узлов, группу моделей ветвей, блок индикации и наборное поле, блок управления содержит первый и

второй элементы задержки, первый и второй элементы И и триггер, каждая из моделей ветвей содержит триггер и элемент И, причем каждый i-й выход (где i 1, 2, ,,,, п) j-й подгруппь: (J 1, 2j .,,,-k) первой

группы информационных выходов наборного поля подключен к i-му информационному входу j-й модели ветви группы, каждый i-й выход j-й подгруппы второй группы информационных вы- ходов наборного поля подключен к i-му входу первой группы информационных входов j-й модели узла группы, i-й информационный выход каждой j-й

модели ветви группы подключен к i-му входу j-й подгруппы первой группы информационных входов наборного поля, каждый i-й информационный выход группы выходов j-й модели узла группы

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

коммутационный элемент, узел пуска, схема сравнения, первый и второй счетчики импульсов, первый и второй дешифраторы, элемент И-НЕ, первьй и второй элементы ИЛИ, умножитель частоты, первый и второй узлы памяти в модель ветви введены счетчик импульсов, дешифратор, группа триггеров, группа элементов И, первый и второй элементы ИЛИ и элемент задержки,причем в каждой модели ветви вход установки в 1 каждого i-ro триггера группы является соответствующим входом группы информационных входов модели ветви, прямой выход каждого i-ro тригге- ра группы подключен к первому входу i-ro элемента И группы к i-му входу первого элемента ИЛИ, входы установки в О всех триггеров группы объе-дииены с входом установки в О счетчи- Ш разрешения индикации блока управлека, с (п+1)-м входом второго элемента РШИ и являются входами установки в О модели ветви, вторые входы элементов И группы модели ветви объединены и подключены к выходу элемен- t5 первого элемента ИЛИ блока управле

та задержки, вход которого подключен к выходу первого элемента ИЛИ модели ветви, выход каждого i-ro элемента И первой группы модели ветви подключе к i-му входу второго элемента ИЛИ модели ветви и является i-м выходом группы информационных выходов модели ветви, выход второго элемента ИЛИ модели подключен к входу установки в О триггера модели ветви, вход установки в 1 которого является входом запуска модели , прямой выход триггера модели ветви подключен к первому входу элемента И .модели ветви, второй вход которого Является тактовым входом модели ветви, выход эдемента И модели ветви подключен к счетному входу счетчика модели ветви, разрядные выходы которого подключены соответственно к входам дешифратора, выходы которого являются группой приоритетных выходо модели ветви и подключены к соответствующим входам группы информационных входов первого коммутатора, прямой выход каждого i-ro триггера группы модели ветви является i-м выходом группы информационных выходов модели ветви, выход второго элемен- иа ИЛИ каждой j-й модели ветви подключен к j-му входу группы входов установки нуля узла пуска блока управления, в блоке управления вход тактовых импульсов узла пуска объединен с входом умножителя частоты и подключен к выходу генератора тактовых импуль

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

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

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

ния. выход первого элемента ИЛИ бло0

0

ка управления является выходом разрешения сброса блока управления, до- полнительньш вход установки нуля узла пуска подключен к выходу второго элемента ИЛИ блока управления, вход разрешения промежуточной установки узла пуска подключен к выходу первого элемента задержки блока управления, группа разрядных выходов перво- - го счетчика блока управления соответственно подключена к группе входов первого дешифратора блока управления, группа выходов которого соответственно подключена к группе управляющих входов первого коммутатора и к . группе входов индикации адреса моде- ли узла конца пути блока индикации, кроме этого, в блоке управления k-й 5 выход дешифратора через элемент И-ИЕ подключен к входу первого элемента задержки, выход которого подютючен к второму входу первого элемента И блока управления, выход которого подключен к первому входу первого элемента ИЛИ блока управления, второй вход первого элемента ИЛИ блока управления объединен с входом установки нуля второго счетчика блока управления, с входом установки нуля триггера блока управления, с первым входом второго элемента EJTli блока управления, с входом установки в О первого узла памяти блока управления, с . входом установки в О второго узла

памяти блока управления и через нормально заьжнутые контак ты коммутационного элемента блока управления подключены к шине нулевого потенциа0

5

0

5

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

ра и группе входов индикации адреса модели узла начала пути блока индикации,, кромеэтого, в блоке управления k-й выход второго дешифратора подключен к второму входу второго элемента И блока управления, группа выходов второго узла памяти блока управления подключена к первой группе информационных входов схемы сравнения, блока управления, группа входов записи второго узла памяти блока управления является группой входов Конечного состояния исследуемого графа устройства, группа входов записи первого узла памяти является группой входов начального состояния исследуе;Мого графа устройства, установочйый вход второго счетчика блока управле ния является установочным входом блокам управления, группа выходов пер- вого коммутатора соответственно подключена к второй группе информационных входов схемы сравнения-блока управления, группа выходов первого узла памяти блока управления соответ- ственно подключена к группе информационных входов второго коммутатора, группа выходов которого соответственно подключена к группе входов моделей узлов,

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

19г 23, 23

Щ 20пЮ,

Фиг. 2

щ

ег.

L.

гй, ,

57

-e

чЛ|

M,

(Й-

,Ш.1

V

ТД /

62,

20n

M

Ф«Ф

Д

ffJ,

so

,

L

%

9 « о

«I w w о .1

5, %г

0W3.5

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

6J,

22;,;; 5,

2Д.г1

3

VZ

2Д.г1

il

Фиг. 6

-

Й,

a

yi

./z

Л

4V

6j

iv

/i . 7

Фи.8

Фиг.З

7,

Фиг. Ю

J92

Фиг.П

Редактор О.Юрковецкая

Составитель Т.Сапунова

Техред В.Кадар Корректор М„Самборская

1454/48

Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектнля, 4