Устройство для моделирования графов Советский патент 1988 года по МПК G06F15/173 

К)

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

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

На фиг.1 изображена функциональная схема предложенного устройства; на фиг.2 - то же, блока управления; на фиг.З - пример моделирования графов .

Устройство для моделирования графов содержит регистр 1 сдвига, сумма тор 2, блок 3 управления, триггер А, группу триггеров 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,

Здесь и далее цифрами в скобках, следующими за номером позиции без скобок, обозначены порядковые номера совершенно одинаковых по своему техническому исполнению и назначению блоков, узлов и элементов. Цифрами в скобках, cтoящIiми у контура соответствующего блока, узла или элемента показаны порядковые номера входов и выходов этого блока, узла или элемента.

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

Генератор 26 импульсов (фиг.2) вьфа батывает последовательность тактовых HNmynbcOB частоты f ,из которых распределитель 27 импульсов формирует п последовательностей импульсов частоты f/n, где п - количество разрядов

,

ю

15

20 25 30

е 0

5

представления весов моделей ветвей, сдвинутых друг относительно друга на время 1/f. Из последовательности импульсов п-го разряда распределителя 27 импульсов распределитель 28 импульсов формирует m последовательностей импульсов длительностью n/f, действующий с частотой f/m-n и сдвинутых друг относительно друга на время n/f.

В режиме ввода весов моделей ветвей в регистр 1 сдвига переключателем 32 блока 3 управления подключают выход генератора 29 одиночных импульсов к входу установки в 1 триггера 34. С помощью коммутаторов 30 и 31 блока 3 управления задают дополнительный двоичный код веса модели ветви и номер модели ветви соответственно. Коммутатор 30 подключает в единичных .разрядах дополнительного двоичного кода веса модели ветви соответствующие выходь: распределителя 27 импульсов к входам элемента ИЛИ 37, на выходе которого, формируется йосле- довательный дополнительньй код веса модели ветви. Например, если вес модели ветви равен пяти (дополнительный двоичный код 11 ... 1011), то выходы всех разрядов, кроме третьего разряда, распределителя 27 импульсов подключаются коммутатором 30, к входам элемента ИЛИ 37. С помощью коммутатора 31 задают номер модели ветви. Например, если выполняется ввод веса в седьмую модель ветви, то выход седьмого разряда распределителя 28 им-. пульсов подключают к входу элемента ИЛИ 38, на выходе которого формируется импульсньш сигн ал длительностью n/f, совпадающий по фазе с временем сдвига с выхода регистра 1 сдвига, под действием тактовых импульсов генератора 26 импульсов п-разрядного двоичного кода веса для седьмой модели ветви. Ввод последовательного дополнительного кода веса модели ветви в регистр 1 сдвига осуществляется после подачи единичного сигнала с выхода элемента НЕ 39 через переклюг чатель 33 на управляющий вход генератора 29 единичных импульсов, который вьщеляет из последовательности импульсов с выхода элемента И 35, действующих с частотой f/m-n, одиночный импульс, устанавливающий через переключатель 32 триггер 34 в единичное состояние на время т-n/f. Триггер 34

устанавливается в нулевое состояние следующим импульсом последовательности с выхода элемента И 35. Триггер 34 в единичном состоянии открывает сигналом с прямого выхода элемент И 36, через который на управляющий вхо регистра 1 сдвига поступает одиночный импульсный сигнал с выхода элемента 38 ИЛИ, задающий номер модели ветви. Под действием тактовых импульсов генератора 26 импульсов блока 3 управления последовательный дополнительный двоичный код веса модели ветви записывается с выхода элемента ИЛИ 37, начиная с младших разрядов, в регистр 1 сдвига во время действия на выходе элемента ИЛИ 38 импульса, задающего номер модели ветви.

Одиночный импульс генератора 29 одиночных импульсов через переключатель 32 и элемент ИЛИ 23 устанавливает триггеры 4и5(1)-5(т) в нулевое состояние.

Аналогичным образом в регистр 1 сдвига записывают дополнительные двоичные коды весов всех моделей ветвей с первой по т-ю.

Изображенное на фиг.1 устройство моделирует m моделей ветвей, входя- щих в модель узла, т.е. один модуль моделирующей структуры. С целью моделирования сложных графов множество модулей коммутируют между собой в соответствии с топологией решаемой задачи, формируя сложные структуры, содержащие узлы, соединенные между собой ветвями. Например, выход 18 модели узла одного модуля подключают к информационным входам 17 моделей ветвей других модулей, индикационные выходы 20 моделей ветвей которых подключаются к индикационным входам 19 данного модуля.

Пример моделирующей структуры, содержащий три модуля, каждый из которых содержит модель узла и м моделей ветвей, изображен на фиг.З («- моделируемый граф, б- моделирующая структура, содержащая три модуля). Блок 3 управления для всех модулей является общим. Неиспользованные при коммутации модулей входы 17 и 19 соединяются с шиной О.

В режиме моделирования переключа- телем 32 блока 3 управления (фиг.2) подключают выход генератора 26 одиночных импульсов к входу ключа 16, с помощью которого задают начальную

модель узла. Пуск устройства осуществляют переключателем 33, с помощью которого на управляющий вход генератора 29 одиночных импульсов подают единичный сигнал выхода элемента НЕ 39. Одиночный импульс генератора 29 одиночных импульсов блока 3 управления поступает через ключ 16 и элемент ИЛИ 12 на вход установки в т триггера 4 модели начального узла и устанавливает его в единичное состояние. Единичньй сигнал с прямого выхода триггера 4 поступает по шине 18 на информационные входы 17 моделей ветвей других модулей моделирующей структуры.

В режиме моделирования кратчайших путей переключатель 25 подключает выход элемента И 8 к одному из вхо- дов элемента ШТР 12.

Предположим, что в режиме моделирования кратчайших путей на первьш информационньй вход 17 первой модели ветви поступил единичный сигнал с. прямого выхода триггера 4 предыд тце- го модуля, В этом случае через первый элемент И 9 данного модуля проходит последовательность импульсов первого разряда распределителя 28 i-iM- пульсов. Последовательность импульсов с выхода первого элемента И 9,: поступает на выход элемента ИПИ 14, выходной сигнал которого открывает элемент И 7 во время фазы сдвига с выхода регистра 1 сдвига (под действием тактовых импульсов генератора 26) дополнительного двоичного кода веса первой модели ветви. Последовательность импульсов первого разряда - распределителя 27 импульсов блока 3 управления поступает через элемент И 7 на вход сумматора 2, на другой вход которого сдвигается с выхода регистра 1 сдвига дополнительный дво- ичньш код веса первой модели ветви. Сумматор 2 выполняет последовательно во времени, начиная с младших разрядов, суммирование дополнительного двоичного кода веса первой модели ветви с последовательностью единиц младшего разряда с выхода элемента И 7. За время т-п тактов дополнительный двоичный код веса первой модели ветви увеличивается на единицу младшего разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 26 импульсов и регистр 1

сдвига. Спустя время тактов, где Р - вес первой модели ветви, на выходе переноса сумматора 2 сформируется сигнал переноса из п-го разряда текущего двоичного кода первой модел ветви, ко торьм через элемент И 8, тактируемый последовательностью -импульсов п-го разряда распределителя 27 импульсов, поступает через пере- ключатель 25 и элемент ИЛИ 12 на единичный вход триггера 4 и черея элемент ИЛИ 22 и элемент И 11(1), открытый сигналом первого разряда распределителя 28 импульсов, - на вход ус- тановки в 1 триггера 5(1). Триггер 4 модели узла и триггер 5(1) первой модели ветви устанавливаются в единичное состояние. В единичном состоянии триггер 4 блокирует сигналом с .инверсного выхода элемент И 7, и процесс .суммирования в сумматоре 2 прекращается.

В том случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные . сигналы, с выходов 18 моделей узлов других модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступают последовательности импульсов с выхода всех разрядов распределителя 28 импульсов, которые открывают элемент И 7. Последовательность импульсов первого разряда распределителя 27 импульсов поступает через элемент И 7, на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые Ш п тактов дополнительные коды весов m моделей ветвей последовательно во времени, начиная с младших разрядов, увеличивается на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время тактов, где Р - наименьший вес из всех моделей ветвей, принадлежащий, например, k-й модели ветви, на выходе переноса сумматора 2 из текущего дополнительного двоичного код веса К-й модели ветви сформируется сигнал переноса из п-го разряда, который через элемент И 8, переключатель 25, элемент ИЛИ 12 и элементы И 8 и ИЛИ 22, k-й элемент И 11 (k) поступает соответственно на входы установки в 1 триггера 4 и k-ro триггера 5(К), устанавливая их в еди

Q г 0

5 п

0

5

ничное состояние. Триггер 5(К) запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае k-й модели ветви) . Триггер 4 в единичном состоянии возбуждает по выходу 18 модули узла вычислительный процесс в моделях ветвей следующих модулей моделирующей структуры и, кроме того, блокирует сигналом с инверсного выхода элемент И 7. Процесс вычислений.в рассматриваемом модуле моделирующей структуры прекращается.

В этом случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы, с выходов 18 моделей узлов других модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступают последовательности импульсов с выходом всех разрядов распределителя 28 импульсов, которые открывают элемент И 7. Последовательность импульсов первого разряда распределителя 27 импульсов поступает через элемент И 7 на вход сумматора- 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые ш п тактов дополнительные коды весов m моделей ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время тактов, где. Р - наименьший вес из всех моделей ветвей, принадлежащий, например, k-й модели ветви, на выходе переноса сумматора 2 из текущего дополнительного двоичного кода веса k-й модели весов сформируется сигнал переноса из п-го разряда, который через элемент И 8, переключатель 25, элемент tfflH 12 и элементы И 8, ИЛИ 22, k-й элемент И 11 (k) поступает соответственно на входы установки в 1 триггера 4 и k-ro триггера 5(k), устанавливая их в единичное состояние. Триггер 5(k) запоминает номер модели ветви, принадлежащий дереву кратчайших путей (в рассматриваемом случае k-й модели ветви), Триггер 4 в единичном состоянии возбуждает по выходу 18 модели узла вычислительный процесс в моделях ветвей следующих модулей моделирующей структуры и, кроме того, блокирует сигналом с ин71

версного выхода.элемент И 7. Процесс вычислений в рассматриваемом модуле моделирующей -структуры прекращается.

Вычислительный процесс распростра няется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели конечного узла,

. В режиме индикации кратчайшего пу ти, выделяемого из дерева кратчайших путей, в модели конечного узла с помощью ключа 16 подключают прямой выход триггера 4 модели конечного узла к одному из входов элемента ИЛИ 13, Единичный сигнал с прямого выхода триггера А проходит через элементы ИЛИ 1.3, И 6 на первые входы элементо И 10(1) - .10(т), вторые входы которых управляются триггерами 5(1) - 5(т) моделей ветвей. Из всей группы элементов И 10(1) - 10(т) откроется элемент И 10(k) той модели ветви, для которой триггер 5(k) находится в

-

5

0

данного модуля одновременно поступают единичные сигналы с выходов 18 моделей узлов других модулей моделирующей структуры, В этом случае последовательности импульсов с выходов всех разрядов распределителя 28 импульсов, последовательно во времени поступают через элементы И 9(1) - 9(т) и ИЛИ 14 на вход элемента И 7, Последовательность импульсов первого разряда распределителя 27 поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 дополнительных кодов весов всех моделей ветвей. Каждые Ш П тактов полнительные коды весов m моделей ветвей последовательно во времени, начиная с младшего разряда, увеличиваются на единицу младшего разряда и с выхода сумматора 2 вновь записыва- ются в регистр 1- сдвига под действием тактовых импульсов, вырабатываемых генератором 26, Если в процессе сум

Изобретение относится к вычислительной технике и может быть использовано для моделирования задач о длиннейшем и кратчайшем пути дискретных вариационных задач, задач оптимального управления и т.д. Устройство моделирует М моделей ветвей, входя- Щах в модель узла, т.е. один модуль моде- .лирукщей структуры. С целью моделирования сложных графов множество моду,лей коммутируют между собой в соответствии с топологией решаемой задачи, формируя сложные структуры, содержащие узлы, соединенные между собой ветвями. В режиме моделирования соответствующими переключателя ми задают начальную и конечную модели узлов. После пуска устройство определяет кратчайший (длиннейший) путь в данный узел из всех подключенных к данному узлу моделей предыдущих узлов и вьщает вес этого пути на информационный выход устройства. Вычислительный процесс распространяется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели конечного узла. В режиме индикации кратчайшего (длиннейшего) пути на индикационный вход устройства модели конечного узла графа подают единичный сигнал, который последовательно распространяется от модели конечного узла графа к модели начального узла, индицируя кратчайший (длиннейший) путь. 3 ил. (Л со vi 00 о:

единичном состоянии, Единичньй сигнал 25 мирования на выходе переноса сумматос выхода триггера 5(k) модели ветви, принадлежащей кратчайшему пути, проходит через соответствующий-элемент И 10(k) на индикационный выход 20(k) k-й модели -ветви и далее поступает на индикационные входы 19 других модулей моделирующей структуры, возбуждая процесс распространения единичного сигнала индикации от модели конечного узла к модели начального узла вдоль кратчайшего пути,

В режиме моделирования длиннейших путей переключателем 25 подключают выход -элемента 24 задержки к одному из входов элемента РШИ 12, Ключом 16 задают начальную модель узла. Пуск устройства осуществляют переключателем 33 блока 3 управления, который запускает генератор 29 одиночных импульсов. Одиночный импульс генератора Д5 как к моменту установки в единичное 29 поступает через ключи 32, 16- и состояние триггера 5(k), соответствуэлемент ИЛИ 12„на вход установки в 1 триггера 4 модели начального узла и устанавливает его в единичное состояние, Единичньй сигнал с прямого выхода триггера 4 поступает на информационный выход 18 данного модуля и далее согласно топологии решаемой задачи на информационные входы 17(1) - 17(т) других модулей моделирующей структуры.

Предположим, что в режиме моделирования длиннейших путем на все информационные входы 17(1) - 17(т)

0

5

0

ра 2 сформируется сигнал переноса из .п-го разряда дополнителного кода веса, например, 1-й модели ветви, то импульс п-го разряда распределителя 27 импульсов блока 3 управления через элементы И 8, WM 22, И 11(1) и устанавливает триггер 5(1) в единичное состояние,

В дальнейшем устройство работает аналогичным образом до тех пор, пока на выходе переноса сзгмматора 2 не сформируется сигнал переноса из п-го разряда дополнительного кода веса длиннейшей, например k-й ветви, В этом случае импульс п-го разряда распределителя 27 импульсов блока 3 управления проходит через элементы И 8, ИЛИ 22, И 11 (1) и устанавливает триггер 5(k) в единичное состояние. Так

0

5

ющего длиннейшей ветви графа, все остальные триггеры 5(1),.,.,5(га) находятся в единичном состоянии в результате предшествующей работы устройства, то на выходе элемента И 21 сформируется единичньш сигнал, который задерживается элементом 24 задержки на -длительность тактового импульса, вырабатываемого генератором 26. Единичный сигнал с выхода элемента 24 задержки поступает через элементы ИЛИ 22, И 11 (k), открытые импульсом k-ro разряда распределителя 28, на

рых управляются триггерами 5(1),..., 5(т) моделей ветвей. Из всей группы элементов И 10(1),...,10(т) откроется элемент И 10(k) той модели ветви, для которой триггер 5(k) находится в единичном состоянии. Единичньй сигнал триггера 5(k) модели ветви, принадлежащей длиннейшему пути, проходит

9 137786710

вход установки в 1 триггера 5(k). Одновременно единичный сигнал с выхода элемента 24 задержки, поступает через элемент ИЛИ 23 на входы установки в О всех триггеров 5(1),..., 5(т). В результате все триггеры 5(1), ,..,5(т) устанавливаются в нулевое состояние, кроме триггера 5(k), на входе установки в единичное состояниеJQ через соответствующий элемент И 10(k) которого действует единичный сигнал на индикационный выход 20(k) модели с выхода элемента И 11(k). Триггер k-й ветви и далее поступает на инди- 5(k), соответствующий длиннейшей вет- кационные входы 19(1)-19(т) других ви, сохраняет единичное состояние, а модулей моделирующей структуры, воз- все остальные триггеры 5(1),...,5(т) ts уждая процесс распространения еди- устанавливаются в нулевое состояние ничного сигнала индикации от модели и блокируют элемент И 21.

Единичный сигнал с выхода элемента 24 задержки поступает через переключатель 25 и элемент ИЛИ 12 на вход 20 установки в 1 триггера 4, который переходит в единичное состояние. На прямом выходе триггера 4 формируется единичный сигнал, которьш поступает на информационньш выход 18 устройст- 25 расширения функциональных возможное на. Нулевой.сигнал с инверсного выхо- тей устройства за счет определения да триггера 4 блокирует элемент И 7, максимального пути в графе, в него что прекращает процесс суммирования введены элемент задержки, четвертьш в сумматоре 2, элемент И, четвертый и пятый элеменЕдиничный сигнал с прямого выхода JQ ты ИЛИ и переключатель, причем пря- триггера 4, поступая с информационно- мой выход k-ro триггера третьей груп- го выхода 18 данного модуля на информационные входы 17(l)-17(m) других

конечного узла к модели начального узла вдоль дли:ннейшего пути.

Формула изобретения

Устройство для моделирования графов по авт.св. № 1246110, о т л и - чающееся тем, что, с целью

пы (,...,m, где m - количество ветвей в графе),подключен к k-му входу четвертого элемента И, вьпсод которого подключен к первому входу переключателя, к первому входу четвертого элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первым входам всех

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

пы (,...,m, где m - количество ветвей в графе),подключен к k-му в ду четвертого элемента И, вьпсод ко торого подключен к первому входу переключателя, к первому входу чет вертого элемента ИЛИ и к первому в ду пятого элемента ИЛИ, выход кото рого подключен к первым входам все

до тех пор, пока не достигнет модели Q элементов И третьей группы, выход

третьего элемента И подключен к в рому входу пятого элемента ИЛИ и к второму входу переключателя,,выход которого подключен к первому входу

конечного узла.

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

ход триггера 4 модели конечного узла 45 элемента ИЛИ, первый выход к одному из входов элемента ИЛИ 13. первого переключателя блока управле- Единичный сигнал с прямого выхода ния подключен к второму входу четвер- триггера.4 проходит через элементы того элемента ИЛИ, выход которого ИЛИ 13, И 6 на первые входы элементов .подключен к входам установки в О И 10(1),...,10(т), вторые входы кото- Q всех триггеров группы.

рых управляются триггерами 5(1),..., 5(т) моделей ветвей. Из всей группы элементов И 10(1),...,10(т) откроется элемент И 10(k) той модели ветви, для которой триггер 5(k) находится в единичном состоянии. Единичньй сигнал триггера 5(k) модели ветви, принадлежащей длиннейшему пути, проходит

через соответствующий элемент И 10(k) на индикационный выход 20(k) модели k-й ветви и далее поступает на инди- кационные входы 19(1)-19(т) других модулей моделирующей структуры, воз- уждая процесс распространения еди- ничного сигнала индикации от модели

через соответствующий элемент И 10(k) на индикационный выход 20(k) модели k-й ветви и далее поступает на инди- кационные входы 19(1)-19(т) других модулей моделирующей структуры, воз- уждая процесс распространения еди- ничного сигнала индикации от модели

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

Формула изобретения

Устройство для моделирования графов по авт.св. № 1246110, о т л и - чающееся тем, что, с целью

ты ИЛИ и переключатель, причем пря- мой выход k-ro триггера третьей груп-

пы (,...,m, где m - количество ветвей в графе),подключен к k-му входу четвертого элемента И, вьпсод которого подключен к первому входу переключателя, к первому входу четвертого элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первым входам всех

элементов И третьей группы, выход

третьего элемента И подключен к второму входу пятого элемента ИЛИ и к второму входу переключателя,,выход которого подключен к первому входу

20ц}

19(т}