Устройство для моделирования графов

(5 Р 15/2 ПИСАНИЕ ИЗОБРЕТЕНИ АВТОРСКОМ ВИДЕТЕЛЬСТ 12461104050009/24-2407.04,8629.02,88. БюлИнститут пробргетике АН УСВ.В.Васильев681.333 (088.Авторское свид6110, кл. С 0(54) У ГРАФОВ (57) И тельно зовано длинне ретение относится кехнике и может бытья моделирования задачи кратчайшем пути ди вычисли испольем ре ных вариационных задачмального управления имоделирует М моделей вщих вмодель узла,т.е.о.лирущцей структуры. Свания сложных графов м ,лей коммутируют между задач оптит.д. Устройство етвей, входя- дин модуль моде- целью моделироножество моду- собой в соотОСУДАРСТВЕНКЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИИ И ОТКРЫТ ветствии с топологией решаемой задачи, формируя сложные структуры, содержащие узлы, соединенные между со- бой ветвями, В режиме моделирования соответствующими переключателями задают начальную и конечную модели узлов. После пуска устройство определяет кратчайший (длиннейший) путь в данный узел иэ всех подключенных к данному узлу моделей предыдущих узлов и выдает вес этого пути на информационный выход устройства. Вычислительный процесс распространяется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели конечного узла. В режиме аф индикации кратчайшего (длиннейшего) пути на индикационный вход устройст ва модели конечного узла графа подают единичный сигнал, который последовательно распространяется от модели конечного узла графа к модели началь- . ного узла, индицируя кратчайший вам (длиннейший) путь. 3 ил. МИзобретение относится к вычислительной технике, может быть использовано для моделирования задач о длиннейшем и кратчайшем пути дискретных вариационных задач, задач оптимального управления и дифференциальных игрУ и является дополнительным к авт,св. В 12461.10.Цель изобретения - расширение функциональных возможностей устройства за счет определения максималь" ных путей в графе,На фиг.1 изображена функциональная схема предложенного устройства; на фиг,2 - то же, блока управления; на фиг.3 - пример моделирования граФов.Устройство для моделирования графов содержит регистр 1 сдвига, сумматор 2, блок 3 управления, триггер 4, группу триггеров 5(1) - 5(ш), элементы И 6 в ,8, три группы элементов И: 9(1) - 9(ш), 10(1) - 10(ш) и 11(1) - 11(ш), элементы ИЛИ 12 - 14, ключи 15 и 16, информационные входы 17(1) - 17(ш) моделей ветвей, выход 18 модели узла, индикационные входы 9(1) - 19(ш) моделей ветвей, индикационные выходы 20(1) - 20(ш) моделей ветвей, элемент И 21, элементы ИЛИ 22 и 23, элемент 24 задержки и переключатель 25.Блок 3 управления (фиг.2) содержитгенератор 26 импульсов, распределители 27 и 28 импульсов, генератор 29одиночных импульсов, кнопочные коммутаторы 30 и 31, переключатели 32 и33, триггер 34, элементы И 35 и 36, элементы ИЛИ 37 и 38, элемент НЕ 39.Здесь и далее цифрами в скобках, следующими за номером позиции беэ скобок, обозначены порядковые номера совершенно одинаковых по своему техническому исполнению и назначению блоков, узлов и элементов. Цифрами в скобках, стоящими у контура соответствующего блока, узла или элемента показаны порядковые номера входов и выходов этого блока, узла или элемента.Устройство работает следующим образом.Генератор 26 импульсов (фиг.2) вырабатывает последовательность тактовых импульсов частоты Г, из которых распределитель 27 импульсов формирует и последовательностей импульсов частоты Е/и, где и - количество разрядов представления весов моделей ветвей,сдвинутых друг относительно другана время 1/Г.Из последовательности 5импульсов п-го разряда распределителя 27 импульсов распределитель 28импульсов Формирует ш последователь"ностей импульсов длительностью и/Й,действующий с частотой Г/ш и и сдвинутых друг относительно друга навремя пИ.В режиме ввода весов моделей вет"вей в регистр 1 сдвига переключателем32 блока 3 управления подключают вы ход генератора 29 одиночных импульсов к входу установки в "1" триггера34, С помощью коммутаторов 30 и 31блока 3 управления задают дополнительный двоичный код веса модели вет ви и номер модели ветви соответственно, Коммутатор 30 подключает в единичных разрядах дополнительного двоичного кода веса модели ветви соответствующие выходы распределителя 27 25 импульсов к входам элемента ИЛИ 37,на выходе которого формируется йоследовательный дополнительный код весамодели ветви, Например, если вес модели ветви равен пяти (дополнительный 30 двоичный код 111011), то выходывсех разрядов, кроме третьего разряда, распределителя 27 импульсов подключаются коммутатором 30, к входамэлемента ИЛИ 37. С помощью коммутатора 31 задают номер модели ветви, Например, если выполняется ввод веса вседьмую модель ветви, то выход седьмого разряда распределителя 28 им-.пульсов подключают к входу элемента 4 О ИЛИ 38, на выходе которого формируется импульсный сигнал длительностьюи/Е, совпадающий по фазе с временемсдвига с выхода регистра 1 сдвига,под действием тактовых импульсов ге нератора 26 импульсов п-разрядногодвоичного кода веса для седьмой модели ветви. Ввод последовательного дополнительного кода веса модели ветвив регистр 1 сдвига осуществляетсяпосле подачи единичного сигнала свыхода элемента НЕ 39 через переклю-,чатель 33 на управляющий вход генератора 29 единичных импульсов, которыйвыделяет из последовательности импульсов с выхода элемента И 35, действующих с частотой Г/ш и, одиночныйимпульс, устанавливающий через пере"ключатель 32 триггер 34 в единичноесостояние на время ш и/Г. Триггер 34устанавливается в нулевое состояниеследующим импульсом последовательности с выхода элемента И 35. Триггер34 в единичном состоянии открываетсигналом с прямого выхода элемент И36, через который на управляющий входрегистра 1 сдвига поступает одиночный импульсный сигнал с выхода элемента 38 ИЛИ, задающий номер модели 10ветви, Под действием тактовых импульсов генератора 26 импульсов блока 3управления последовательный дополнительный двоичный код веса модели ветви записывается с выхода элемента 15ИЛИ 37, начиная с младших разрядов,в регистр 1 сдвига во время действияна выходе элемента ИЛИ 38 импульса,задающего номер модели ветви,Одиночный импульс генератора 29 20одиночных импульсов через переключатель 32 и элемент ИЛИ 23 устанавливает триггеры 4 и 5(1) - 5(ш) в нулевое состояние,Аналогичным образом в регистр 1 25сдвига записывают дополнительные двоичные коды весов всех моделей ветвейс первой по ш-ю.Изображенное на фиг.1 устройствомоделирует ш моделей ветвей, входящих в модель узла, т.еодин модульмоделирующей структуры. С целью моделирования сложных графов множествомодулей коммутируют между собой всоответствии с топологией решаемойзадачи, формируя сложные структуры,содержащие узлы, соединенные междусобой ветвями. Например, выход 18модели узла одного модуля подключаютк информационным входам 17 моделей 40ветвей других модулей, индикационныевыходы 20 моделей ветвей которыхподключаются к индикационным входам19 данного модуля,Пример моделирующей структуры, 45содержащий три модуля, каждый из которых содержит модель узла и м моделей ветвей, изображен на Фиг.З ( а -моделируемый граф, б- моделирующаяструктура, содержащая три модуля).Блок 3 управления для всех модулейявляется общим, Неиспользованные прикоммутации модулей входы 17 и 19 соеДиняются с шиной ОВ режиме моделирования переключателем 32 блока 3 управления (фиг,2)подключают выход генератора 26 одиночных импульсов к входу ключа 16,с помощью которого задают начальную модель узла. Пуск устройства осуществляют переключателем 33, с помощьюкоторого на управляющий вход генератора 29 одиночных импульссв подаютединичный сигнал выхода элемента НЕ39. Одиночный импульс генератора 29одиночных импульсов блока 3 управления поступает через ключ 16 и элемент ИЛИ 12 на вход установки в "1"триггера 4 модели начального узла иустанавливает его в единичное состояние, Единичный сигнал с прямого выхода триггера 4 поступает по шине 18на информационные входы 17 моделейветвей других модулей моделирующейструктуры.В режиме моделировачия кратчайшихпутей переключатель 25 подключаетвыход элемента И 8 к одному из вхо-.дов элемента ИЛИ 12,Предположим, что в режиме моделирования кратчайших путей на первыйинформационный вход 17 первой моделиветви поступил единичный сигнал спрямого выхода триггера 4 предыдущего модуля, В этом случае через первый элемент И 9 данного модуля проходит последовательность импульсов первого разряда распределителя 28 импульсов. Последовательность импульсов с выхода первого элемента И 9,поступает на выход элемента ИЛИ 14,выходной сигнал которого открываетэлемент И 7 во время фазы сдвига свыхода регистра 1 сдвига (под деиствием тактовых импульсов генератора26) дополнительного двоичного кодавеса первой модели ветви, Последовательность импульсов первого разряда .распределителя 27 импульсов блока 3управления поступает через элементИ 7 на вход сумматора 2, на другойвход которого сдвигается с выхода регистра 1 сдвига дополнительный двоичный код веса первой модели ветви.Сумматор 2 выполняет последовательново времени, начиная с младших разрядов, суммирование дополнительногодвоичного кода веса первой моделиветви с последовательностью единицмладшего разряда с выхода элементаИ 7. За время ш и тактов дополнительный двоичный код веса первой моделиветви увеличивается на единицу младшего разряда и результат с выходасуммы сумматора 2 вновь сдвигаетсяпод действием тактовых импульсов генератора 26 импульсов и регистр 15 137786сдвига. Спустя время Р,ш и тактов,где Р - вес первой модели ветви, навыходе переноса сумматора 2 сформируется сигнал переноса из п-го разрядатекущего двоичного кода первой модели5ветви, который через элемент И 8,тактируемый последовательностью импульсов и-го разряда распредеЛителя27 импульсов, поступает через переключатель 25 и элемент ИЛИ 12 на единичный вход триггера 4 и через элемент ИЛИ 22 и элемент И 11(1), открытый сигналом первого разряда распределителя 28 импульсов, - на вход установки в " 1" триггера 5(1), Триггер4 модели узла и триггер 5(1) первоймодели ветви устанавливаются в единичное состояние, В единичном состоянии триггер 4 блокирует сигналом с 2 О,инверсного выхода элемент И 7, и процесс,суммирования в сумматоре 2 прекращается,В том случае, когда на все информационные входы 17 моделей ветвейодновременно поступают единичныесигналы, с выходов 18 моделей узловдругих модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступаютпоследовательности импульсов с выходавсех разрядов распределителя 28 импульсов, которые открывают элементИ 7. Последовательность импульсовпервого разряда распределителя 27 импульсов поступает через элемент И 7,на вход сумматора 2 во время сдвигас выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые ш п тактов дополнитель 40ные коды весов ш моделей ветвей последовательно во времени, начиная смладших разрядов, увеличивается наединицу младшего разряда и с выходасуммы сумматора 2 вновь записываютсяв регистр 1 сдвига. Спустя время45Рш-и тактов, где Р - наименьшийвес из всех моделей ветвей, принадлежащий, например, Е-й модели ветви,на выходе переноса сумматора 2 из текущего дополнительного двоичного кодавеса Е-й .модели ветви сформируетсясигнал переноса из п-го разряда, который через элемент И 8, переключатель 25, элемент ИЛИ 12 и элементыИ 8 и ИЛИ 22, 1 с-й элемент И 11 Ос)поступает соответственно на входыустановки в " 1" триггера 4 и Ы-готриггера 5 Й), устанавливая их в еди 7 6ничное состояние. Триггер 5(К) запоминает номер модели ветви, принадлежащий дереву кратчачших путей (в рассматриваемом случае к-й модели ветви). Триггер 4 в единичном состоянии возбуждает по выходу 18 модули узла вычислительный процесс в моделях ветвей следующих модулей моделирующей структуры и, кроме того, блокирует сигналом с инверсного выхода элемент И 7. Процесс вычислений в рассматриваемом модуле моделирующей структуры прекращается.В этом случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы, с выходов 18 моделей узлов других модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступают последовательности импульсов с выходом всех разрядов распределителя 28 импульсов, которые открывают элемент И 7, Последовательность импульсов первого разряда распределителя 27 импульсов поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые ш и тактов дополнительные коды весов ш моделей ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время Рш и тактов, где, Р - наименьший вес из всех моделей ветвей, принадлежащий, например, 1 с-й модели ветви, на выходе переноса сумматора 2 из текущего дополнительного двоичного кода веса к-й модели весов сформируется сигнал переноса из и-го разряда, который через элемент И 8, переключатель 25, элемент ИЛИ 12 и элементы И 8, ИЛИ 22, 1-й элемент И 11 Ь) поступает соответственно на входы установки в "1" триггера 4 и 1-го триггера 5 Ь), устанавливая их в единичное состояние. Триггер 5(к) запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае 1-й модели ветви), Триггер 4 в единичном состоянии возбуждает по выходу 18 модели узла вычислительный процесс в моделях ветвей следующих модулей моделирующей структуры и, кроме того, блокирует сигналом с ин 1377867версного выхода, элемент И 7. Процесс вычислений в рассматриваемом модуле моделирующей структуры прекращается.Вычислительный процесс распростра 5 няется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели конечного узла.. В режиме индикации кратчайшего пу ти, выделяемого из дерева кратчайших путей, в модели конечного узла с помощью ключа 16 подключают прямой выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13.Единичный сигнал с прямого выхода триггера 4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10(1) - .10(ш), вторые входы которых управляются триггерами 5(1) - 20 5(ш) моделей ветвей. Из всей группы элементов И 10(1) - 10(ш) откроется элемент И 10 Ь) той модели ветви, для которой триггер 5(Е) находится в единичном состоянии, Единичный сигнал 25 с выхода триггера 5 Й) модели ветви, принадлежащей кратчайшему пути, проходит через соответствующий элемент И 10%) на индикационный выход 20(1 с) 1-й модели ветви и далее поступает ЗО на индикационные входы 19 других модулей моделирующей структуры, возбуж" дая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути.35В режиме моделирования длиннейших путей переключателем 25 подключают выход элемента 24 задержки к одному из входов элемента ИЛИ 12, Ключом 16 . 4 О задают начальную модель узла, Пуск устройства осуществляют переключателем 33 блока 3 управления, который запускает генератор 29 одиночных импульсов. Одиночный импульс генератора 45 29 поступает через ключи 32, 16 и элемент ИЛИ 12.на вход установки в "1" триггера 4 модели начального узла и устанавливает его в единичное состояние. Единичныи сигнал с прямого выхода триггера 4 поступает на" информационный выход 18 данного модуля и далее согласно топологии решаемой задачи на информационные входы 17(1) 17(ш) других модулей моделирующей структуры.Предположим, что в режиме моделирования длиннейших путем на все информационные входы 17(1) - 17(ш) данного модуля одновременно поступают единичные сигналы с выходов 18моделей узлов других модулей моделирующей структуры. В этом случае последовательности импульсов с выходоввсех разрядов распределителя 28 импульсов, последовательно во временипоступают через элементы И 9(1)9(ш) и ИЛИ 14 на вход элемента И 7,Последовательность импульсов первогоразряда распределителя 27 поступаетчерез элемент И 7 на вход сумматора2 во время сдвига с выхода регистра1 дополнительных кодов весов всех моделей ветвей. Каждые ш и тактов дополнительные коды весов ш моделейветвей последовательно во времени,начиная с младшего разряда, увеличиваются на единицу младшего разряда ис выхода сумматора 2 вновь записываются в регистр 1 сдвига под действиемтактовых импульсов, вырабатываемыхгенератором 26, Если в процессе суммирования на выходе переноса сумматора 2 сформируется сигнал переноса изи-го разряда дополнителного кода веса, например, 1-й модели ветви, тоимпульс и-го разряда распределителя27 импульсов блока 3 управления через элементы И 8, ИЛИ 22, И 11(1) иустанавливает триггер 5(1) в единичное состояние,В дальнейшем устройство работаетаналогичным образом,до тех пор, покана выходе переноса сумматора 2 несформируется сигнал переноса из и-горазряда дополнительного кода весадлиннейшей, например 1-й ветви, Вэтом случае импульси-го разряда распределителя 27 импульсов блока 3 управления проходит через элементы И 8,ИЛИ 22, И 11(М) и устанавливает триггер 5) в единичное состояние, Таккак к моменту установки в единичноесостояние триггера 5(К), соответствующего длиннейшей ветви графа, все остальные триггеры 5(1)5(ш) находятся в единичном состоянии в результате предшествующей работы устройства, то на выходе элемента И 21 сформируется единичный сигнал, которыйзадерживается элементом 24 задержкина длительность тактового импульса,вырабатываемого генератором 26. Единичный сигнал с выхода элемента 24задержки поступает через элементыИЛИ 22, И 11(1 с), открытые импульсомЕ-го разряда распределителя 28, навход установки в "1" триггера 5(Е), Одновременно единичный сигнал с выхода элемента 24 задержки, поступает через элемент ИЛИ 23 на входы установки в "0" всех триггеров 5(1) 5(ш), В результате все триггеры 5(1), ,5(ш) устанавливаются в нулевое состояние, кроме триггера 5 Ь), на входе установки в единичное состояние 10 которого действует единичный сигнал с выхода элемента И 11(К), Триггер 5(К), соответствующий длиннейшей ветви, сохраняет единичное состояние, а все остальные триггеры 5(1)5(ш) 15 устанавливаются в нулевое состояние и блокируют элемент И 21.Единичный сигнал с выхода элемента 24 задержки поступает через переключатель 25 и элемент ИЛИ 12 на вход установки в "1" триггера 4, который переходит в единичное состояние. На прямом выходе триггера 4 формируется единичный сигнал, который поступает на информационный выход 18 устройст ва. Нулевой сигнал с инверсного выхода триггера 4 блокирует элемент И 7, что прекращает процесс суммирования в сумматоре 2Единичный сигнал с прямого выхода триггера 4, поступая с информационного выхода 18 данного модуля на информационные входы 17(1)-17(ш) других модулей, возбуждает в них вычислительный процесс, который осуществля- . ется аналогично описанному процессу в данном модуле. Вычислительный процесс распространяется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели,10 конечного узла.В режиме индикации длиннейшего пути в модели конечного узла с по мощью ключа 15 подключают прямой выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13. Единичный сигнал с прямого выхода триггера.4 проходит через элементы ИЛИ 13, И 6 на первые входы элементов И 10(1)10(ш), вторые входы которых управляются триггерами 5(1).5(ш) моделей ветвей. Из всей группыэлементов И 10(1) .,10(ш) откроетсяэлемент И 10%) той модели ветви,для которой триггер 5(к) находится вединичном состоянии. Единичный сигнал триггера 5 Ь) модели ветви, принадлежащей длиннейшему пути, проходитчерез соответствующий элемент И 10(1)на индикационный выход 20 Ь) модели1-й ветви и далее поступает на индикационные входы 19(1)-19(ш) другихмодулей моделирующей структуры, возбуждая процесс распространения единичного сигнала индикации от моделиконечного узла к моделиначальногоузла вдоль длиннейшего пути,формула из обре,тенияУстройство для моделирования графов.по авт,св. Р 1246110, о т л и - ч а ю щ е е с я тем, что, с целью расширения функциональных возможнос- тей устройства за счет определения максимального пути в графе, в него введены элемент задержки, четвертый элемент И, четвертый и пятый элементы ИЛИ и переключатель, причем прямой выход К-го триггера третьей группы (1;=1. ш, где ш - количество ветвей в граФе), подключен к 1-му входу четвертого элемента И, выход которого подключен к первому входу переключателя, к первому входу четвертого элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первым входам всех элементов И третьей группы, выход третьего элемента И подключен к второму входу пятого элемента ИЛИ и к второму входу переключателя, выход которого подключен к первому входу первого элемента ИЛИ, первый выход первого переключателя блока управления подключен к второму входу четвертого элемента ИЛИ, выход которого подключен к входам установки в "0"всех триггеров группы.1Тираж 704И Государственногоделам изобретений иМосква, Ж, Раушс Подписноомитета СССРоткрытийая наб., д, 4/5 2) т)