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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

„„SU„„1377867 A 2 (51) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИИ И ОТКРЫТИЙ (61) 1246110 (21) 4050009/24-24 (22) 07.04.86 (46) 29.02,88. Бюл. Ф 8 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев и В.Л.Баранов (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Ф 1246110, кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть исполь.зовано для моделирования задач о длиннейшем и кратчайшем пути дискретных вариационных задач, задач оптимального управления и т.д, Устройство моделирует М моделей ветвей, входящих в модель узла, т.е. один модуль моде.лирующей структуры. С целью моделирования сложных графов множество моду,лей коммутируют между собой в соот ветствии с топологией решаемой задачи, формируя сложные структуры, содержащие узлы, соединенные между со- бой ветвями. В режиме моделирования соответствующими переключателями задают начальную и конечную модели узлов. После пуска устройство определяет кратчайший (длиннейший) путь в данный узел иэ всех подключенных к данному узлу моделей предыдущих узлов и выдает вес этого пути на информационный выход устройства. Вычислительный процесс распространяется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели конечного узла. В режиме индикации кратчайшего (длиннейшего) пути на индикационный вход устройст» ва модели конечного узла графа подают единичный сигнал, который последовательно распространяется от модели конечного узла графа к модели началь- . ного узла, индицируя кратчайший (длиннейший) путь. 3 ил.

1377867

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

У и является дополнительным к авт.св.

В 12461.10.

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

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

Устройство для моделирования графов содержит регистр 1 сдвига, сумматор 2, блок 3 управления, триггер 4, группу триггеров 5(1) — 5(ш), элементы И 6 вЂ,8, три группы элементов

И: 9(1) — 9(ш), 10(1) — 10(ш) и

11(1) — 11(m), элементы ИЛИ 12 — 14, ключи 15 и 16, информационные входы

17(1) - 17(m) моделей ветвей, выход

18 модели узла, индикационные входы

9(1) - 19(m) моделей ветвей, индикационные выходы 20(1) — 20(m) моделей ветвей, элемент И 21, элементы ИЛИ

22 и 23, элемент 24 задержки и переключатель 25.

Блок 3 управления (фиг.2) содержит генератор 26 импульсов, распределители 27 и 28 импульсов, генератор 29 одиночных импульсов, кнопочные коммутаторы 30 и 31, переключатели 32.и

33, триггер 34, элементы И 35 и 36, элементы ИЛИ 37 и 38, элемент НЕ 39.

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

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

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

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

В режиме ввода весов моделей ветвей в регистр 1 сдвига переключателем

32 блока 3 управления подключают вы15 ход генератора 29 одиночных импульсов к входу установки в "1" триггера

34, С помощью коммутаторов 30 и 31 блока 3 управления задают дополнительный двоичный код веса модели вет20 ви и номер модели ветви соответственно. Коммутатор 30 подключает в единичных разрядах дополнительного двоичного кода веса модели ветви соответствующие выходы распределителя 27

25 импульсов к входам элемента ИЛИ 37, на выходе которого формируется йоследовательный дополнительный код веса модели ветви. Например, если вес модели ветви равен пяти (дополнительный

30 ДВОичный кОД 11 ° ° ° 1011)у то ВыхОДы всех разрядов, кроме третьего разряда, распределителя 27 импульсов подключаются коммутатором 30, к входам элемента ИЛИ 37. С помощью коммутатора 31 задают номер модели ветви, Например, если выполняется ввод веса в седьмую модель ветви, то выход седьмого разряда распределителя 28 им-. пульсов подключают к входу элемента

40 ИЛИ 38, на выходе которого формируется импульсный сигнал длительностью

n/f, совпадающий по фазе с временем сдвига с выхода регистра 1 сдвига, под действием тактовых импульсов ге нератора 26 импульсов п-разрядного двоичного кода веса для седьмой модели ветви. Ввод последовательного дополнительного кода веса модели ветви в регистр 1 сдвига осуществляется после подачи единичного сигнала с выхода элемента НЕ 39 через переклю-, чатель 33 на управляющий вход генератора 29 единичных импульсов, который выделяет из последовательности импульсов с выхода элемента И 35, действующих с частотой f/m n, одиночный импульс, устанавливающий через переключатель 32 триггер 34 в единичное состояние на время m n/f. Триггер 34

1377867 устанавливается в нулевое состояние следующим импульсом последовательности с выхода элемента И 35. Триггер

34 в единичном состоянии открывает сигналом с прямого выхода элемент И

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

ИЛИ 37, начиная с младших разрядов, в регистр 1 сдвига во время действия на выходе элемента ИЛИ 38 импульса, .задающего номер модели ветви.

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

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

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

19 данного модуля.

Пример моделирующей структуры, 45 содержащий три модуля, каждый из которых содержит модель узла и м моделей ветвей, изображен на фиг.3 (a— моделируемый граф, б- моделирующая структура содержащая ТрН модуля) ° 50

Блок 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. За время m n тактов дополнительный двоичный код веса первой модели ветви увеличивается на единицу младшего разряда и результат с выхода суммы сумматора 2 вновь сдвигается под действием тактовых импульсов генератора 26 импульсов и регистр 1

5 137786 сдвига. Спустя время Р,m п тактов, где Р„ — вес первой модели ветви, на выходе переноса сумматора 2 сформируется сигнал переноса из п-го разряда текущего двоичного кода первой модели

5 ветви, который через элемент И 8, тактируемый последовательностью импуль сов и- го разряда распредеЛителя

27 импульсов, поступает через переключатель 25 и элемент ИЛИ 12 на единичный вход триггера 4 и через элемент ИЛИ 22 и элемент И 11(1), открытый сигналом первого разряда распределителя 28 импульсов, — на вход ус- q5 тановки в "1" триггера 5(1). Триггер

4 модели узла и триггер 5(1) первой модели ветви устанавливаются в единичное состояние. В единичном состоянии триггер 4 блокирует сигналом с 2р ,инверсного выхода элемент И 7, и процесс,суммирования в сумматоре 2 прекращается.

В том случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы, с выходов 18 моделей узлов других модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступают последовательности импульсов с выхода всех разрядов распределителя 28 импульсов, которые открывают элемент

И 7. Последовательность импульсов первого разряда распределителя 27 импульсов поступает через элемент И 7, на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые m п тактов дополнитель40 ные коды весов m моделей ветвей последовательно во времени, начиная с младших разрядов, увеличивается на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время

P„m-и тактов, где P — наименьший вес из всех моделей ветвей, принадлежащий, например, k-й модели ветви, на выходе переноса сумматора 2 из текущего дополнительного двоичного кода веса k-й модели ветви сформируется сигнал переноса из п-ro разряда, который через элемент И 8, переключатель 25, элемент ИЛИ 12 и элементы

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

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

В этом случае, когда на все информационные входы 17 моделей ветвей одновременно поступают единичные сигналы, с выходов 18 моделей узлов других модулей моделирующей структуры через элементы И 9 и ИЛИ 14 последовательно во времени поступают последовательности импульсов с выходом всех разрядов распределителя 28 импульсов, которые открывают элемент

И 7. Последовательность импульсов первого разряда распределителя 27 импульсов поступает через элемент И 7 на вход сумматора 2 во время сдвига с выхода регистра 1 сдвига дополнительных кодов весов всех моделей ветвей. Каждые m n тактов дополнительные коды весов m моделей ветвей последовательно во времени, начиная с младших разрядов, увеличиваются на единицу младшего разряда и с выхода суммы сумматора 2 вновь записываются в регистр 1 сдвига. Спустя время P m u тактов, где. P — наименьший вес из всех моделей ветвей, принадлежащий, например, k-й модели ветви, на выходе переноса сумматора 2 из текущего дополнительного двоичного кода веса

k-й модели весов сформируется сигнал переноса из и-го разряда, который через элемент И 8, переключатель 25, элемент ИЛИ 12 и элементы И 8, ИЛИ

22, k-й элемент И 11 (k) поступает соответственно на входы установки в

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

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

Единичный сигнал с прямого выхода триггера 4 проходит через элементы

ИЛИ 13, И 6 на первые входы элементов

И 10(1) — .10(m), вторые входы которых управляются триггерами 5(1) — 20

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

И 10(k) на индикационный выход 20(1с)

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

В режиме моделирования длиннейших путей переключателем 25 подключают выход:элемента 24 задержки к одному из входов элемента ИЛИ 12, Ключом 16 . 4O задают начальную модель узла. Пуск устройства осуществляют переключателем 33 блока 3 управления, который запускает генератор 29 одиночных импульсов. Одиночный импульс генератора 45

29 поступает через ключи 32, 16 и элемент ИЛИ 12.на вход установки в

"1" триггера 4 модели начального узла.и устанавливает его в единичное состояние. Единичныи сигнал с прямого выхода триггера 4 поступает на" информационный выход 18 данного модуля и далее согласно топологии решаемой задачи на информационные входы 17(1)

17(m) других модулей моделирующей структуры.

Предположим, что в режиме моделирования длиннейших путем на все информационные входы 17(1) — 17(ш) данного модуля одновременно поступают единичные сигналы с выходов 18 моделей узлов других модулей моделирующей структуры. В этом случае последовательности импульсов с выходов всех разрядов распределителя 28 импульсов, последовательно во времени поступают через элементы И 9(1)

9(ш) и ИЛИ 14 на вход элемента И ?, Последовательность импульсов первого разряда распределителя 27 поступает через элемент И 7 на вход сумматора

2 во время сдвига с выхода регистра

1 дополнительных кодов весов всех моделей ветвей. Каждые ш и тактов до» полнительные коды весов ш моделей ветвей последовательно во времени, начиная с младшего разряда, увеличиваются на единицу младшего разряда и с выхода сумматора 2 вновь записываются в регистр 1 сдвига под действием тактовых импульсов, вырабатываемых генератором 26, Если в процессе суммирования на выходе переноса сумматора 2 сформируется сигнал переноса из

n-ro разряда дополнителного кода веса, например, 1-й модели ветви, то импульс и-го разряда распределителя

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

ИЛИ 22, И 11(1с), открытые импульсом

k-го разряда распределителя 28, на

1377867

10 вход установки в "1" триггера 5(k).

Одновременно единичный сигнал с выхода элемента 24 задержки, поступает через элемент ИЛИ 23 на входы установки в "0" всех триггеров 5(1),..., 5(ш), В результате все триггеры 5(1), ...,5(m) устанавливаются в нулевое состояние, кроме триггера 5(), на входе установки в единичное состояние 1р которого действует единичный сигнал с выхода элемента И « (k), Триггер

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

24 задержки поступает через переключатель 25 и элемент ИЛИ 12 на вход установки в "1" триггера 4, который переходит в единичное состояние. На прямом выходе триггера 4 формируется единичный сигнал, который поступает на информационный выход 18 устройства. Нулевой сигнал с инверсного выхода триггера 4 блокирует элемент И 7, что прекращает процесс суммирования в сумматоре 2 °

Единичный сигнал с прямого выхода триггера 4, поступая с информационного выхода 18 данного модуля на информационные входы 17(1)-17(m) других модулей, возбуждает в них вычислительный процесс, который осуществля- . ется аналогично описанному процессу в данном модуле. Вычислительный процесс распространяется от одного модуля моделирующей структуры к другому до тех пор, пока не достигнет модели,10 конечного узла.

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

Единичный сигнал с прямого выхода триггера.4 проходит через элементы

ИЛИ 13, И 6 на первые входы элементов

И 10(1),...,10(m) вторые входы кото- gp

I рых управляются триггерами 5(1) .

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

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

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

Устройство для моделирования графов. по авт,св. N - 1246110, о т л и— ч а ю щ е е с я тем, что, с целью расширения функциональных возможнос- тей устройства за счет определения максимального пути в графе, в него введены элемент задержки, четвертый элемент И, четвертый и пятый элементы ИЛИ и переключатель, причем прямой выход k-ro триггера третьей группы (k=1,...,m, где m — количество ветвей в графе),подключен к k-му входу четвертого элемента И, выход которого подключен к первому входу переключателя, к первому входу четвертого элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первым входам всех элементов И третьей группы, выход третьего элемента И подключен к второму входу пятого элемента ИЛИ и к второму входу переключателя, выход которого подключен к первому. входу первого элемента ИЛИ, первый выход первого переключателя блока управления подключен к второму входу четвертого элемента ИЛИ, выход которого подключен к входам установки в "0" всех триггеров группы.

1377867

19 rj

) 1377867

2)

m)

Составитель А,Мишин

Редактор М.Келемеш Техред М.Ходанич корректор М.Пожо

Заказ 875/46 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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