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

 

Изобретение относится к области вычислительной техникии может быть использовано для определения величины кратчайшего пути в графе, С этой целью устройство содержит пять блоков/ памяти и два блока вывода, с помощью которых задается топология исследуемого графа и отмечается движение по его ветвям (исполнение) верошн.Веса ветвей, исходящих из достигнутой вершины графа, моделируются одновременно при помощи многоканального таймера . Это позволяет определить величину кратчайшего пути в графе за время, пропорциональное весу пути. 4 ил. |

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

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

РЕСПУБЛИК (19) (11) 74 A t (so 4 G 06 F 15/20

ar, . й(, Г,-1.-;.,, Г Ц йбр „=,::-, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

M A ВТОРСНОМУ СВИДЕТЕПЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 4098834/24-24 (22) 25.07.86 . (46.) 15,1 1..88. Бюл. У 42 (71) Институт проблем моделирования в энергетике АН УССР (72) А.Г. Додонов, А.A. Котляренко, С.П, Пелехов, В.П. Приймачук и A.Ì. Щетннин (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 470811, кл. G 06 F 15/20, 1973.

Авторское свидетельство СССР

У 1161951, кл. G 06 F 15/20, !984. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТР0В ГРАФА (57) Изобретение относится к области вычислительной техники.и может быть использовано для определения величины кратчайшего пути в графе. С этой целью устройство содержит пять блоков памяти и два блока вывода, с помощью которых задается топология исследуемого графа и отмечается движение по его ветвям .(исполнение) вершин. Веса ветвей, исходящих из достигнутой вершины графа, моделируются одновременно при помощи многоканального таймера. Это позволяет определить величину кратчайшего пути в графе эа время, пропорциональное весу пути. 4 ил.

Р 1 с0

1437874

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

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

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

Устройство содержит с первого по пятый блоки 1-5 памяти„- таймер 6, первый и второй блоки 7 и 8 вывода информации, с первого по третий блоки

9-11 синхронизации, с первого по чет- 20 вертый регистры 12-15, блоки 16 сравнения, счетчик 17, первый и второй триггеры 18 и 19, с первого па третий блоки 20-22 элементов И, с первого по третий элементы ИЛИ 22-25, эле- 25 мент И 26 и элемент НЕ 27.

Кроме того, на фиг. 1 цифровые обозначения имеют вход 28 начальной установки устройства, вход 29 пуска устройства, вход 30 задания номера 30 начального узла пути устройства, вход

31 задания номера конечного узла пути устройства, выход 32 признака окончания работы устройства, выход

33 веса кратчайшего пути в графе уст- 3 ройства, тактовый вход 34 устройства, с первого по пятый выходы 35-39 первого блока 9 синхронизации, с первого по пятый выходы 40-44 второго блока 10 синхронизации и с первого !0 по четвертый выходы 45-48 третьего блока 1! синхронизации, Устройство работает следующим образом.

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

4, 2, 4, 2, 1, 2, I и 4 (задают длительность соответствующих адресам ветвей графа); в блок 4 памяти по адресам 1,2,3,4,5,6,7 и 8 заносят соответственно числа 4,5,4,2,! 3,5 и 4 (задают номера узлов, в которые входят соответствующие адресам ветви графа). В блок 7 вывода информации по адресам 1,2,3,4 и 5 заносят соответственна списки (5), (2), (6), (3,1, 8) и (4,7)(задают списки ветвей, входящих в соответствующие адресам списков узлы графа). В блок 8 вывода информации па адресам I 2,3,4 и 5 заносят соответственно списки чисел (6), (1,7), (2,3,4}, (5) и (8)(задают списки ветвей, выходящих из соответствующих адресам списков узлов графа}.

На вход 30 подают число 3 (номер начального узла пути). На вход 31 подают числа 1 (намер начального узла пути).

На вход 28 начальной установки устройства подают импульсный сигнал единичного уровня. При этом снимаются все прерывания и абнуляются все каналы таймера, устанавливается в ноль триггер 18, обнуляется счетчик 17, устанавливается в единичное состояние триггер 19, в регистр 12 наносится число 3, в регистр 15 числа l. .На вход пуска устройства подают импульсный сигнал единичного уровня. При этом блок 7 вывода информации выдает число 6, на свой информационный выход (намер ветви первой в списке входящих в начальный узел пути) и импульсный сигнал единичного уровня на выход признака выдачи слова. При этом блок 9 синхронизации начинает формировать последовательность сигналов в соответствии с временной диаграммой работы (фиг. 2) На выходе 35 появляется импульс единичного уровня. При этом код числа Ь заносится в регистр

l3. Через время Т, достаточное для записи информации в регистр 13, на выходе 36 блока 7 синхронизации появляется сигнал единичного уровня.

При этом в блок l памяти па адресу

6 заносится l (начальный узел пути считается достигнутым, а все входящие я него ветви свершенными), Н3 блока 5 памяти по. адресу 6 считывается нулевое информационное слово.

Через время Т, достаточное для чтения информации из блока 5 памяти, на выходе 37 блока 9 синхронизации появляется сигнал единцчнага уровня.

При этом устанавливается в ноль нулевой канал таймер 6 (холостая

4 нале таймера 6, на выходе 43 блока

10 синхронизации появляется импульсный сигнал единичного уровня. Прн этом устанавливается в ноль регистр

14. После этого на выходе 44 блока

10 синхронизации появляется импульсный сигнал единичного уровня. При этом на информационном выходе блока

8 вывода информации появляется число 3 (номер очередной ветви, выходящей из начального узла пути), на выходе признака выдачи слова блока 8 появляется импульсный сигнал единичного уровня. Далее устройство работает аналогично и на втором и третьем тактах работы блока 10 в блок 5 памяти по адресам 3 и 4 записаны числа

2 и 3 соответственно (номера каналов таймера, занятых исполнением моделированием ветвей 3 и 4, в блок 3 памяти по адресам 2 и 3 будут записаны числа 3 и 4 соответственно (номера ветвей, которые моделирует второй и третий каналы таймера 6), во второй и третий каналы таймера 6 записаны числа 4 и 3 соответственно (веса ветвей 3 и 4). При подаче на вход

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

При этом устанавливается в единицу триггер 18, таймер 6 и счетчик 17 начинают счет тактовых импульсов. Через 2 тактовых импульса на выходе прерывания таймера 6 появляется сигнал единичного уровня. При этом устанавливается в ноль .триггер 18, таймер

6 и счетчик 17 прекращает счет тактовых импульсов, блок 11 синхронизации начинает формировать последовательность сигналов в соответствии с временной программой (фиг. 3), на выходе номера загружаемого канала таймера 6 появляется код числа ) (номер канала таймера с высшим приоритетом, первым выставивший прерывание). Сигнал единичного уровня появляется на выходе 45 блока ll. При этом из блока

3 памяти по. адресу 1 считывается число 2 (номер ветви, исполненной данным каналом). Через время Т4, доста" точное для окончания чтения из блока 3 памяти, на выходе 46 блока 11 появляется сигнал единичного уровня, при этом из блока 4 памяти по адресу 2 считывается число 2 (номер узла, в который входит исполненная з 1437874 операция, так как таймер 6 еще не был занят моделированием ветви). Через время Т, достаточное для установки в ноль канала таймера на выЭ

5 ходе 38 блока 9 синхронизации появляется импульс единичного уровня.При этом устанавливается в ноль регистр

13. После этого на выходе 39 блока

9 синхронизации появляется импульс 10 единичного уровня. При этом блок 7 вывода информации формирует импульс единичного уровня на своем выходе признака конца списка (список ветвей, входящих в третий начальный узел, ис- l5 черпан). При этом блок 8 вывода информации выдает на информационный выход число 2 (номер ветви первой в списке ветвей, выходящих из начального третьего узла), и импульс еди- 2р ничного уровня появляется на выходе признака выдачи слова. При этом блок

l0 синхронизации начинает формировать последовательность сигналов в соответствии со своей временной диа- 25 граммой. На выходе 40 блока 10 появляется импульсный сигнал единичного уровня. При этом число 2 заносится в регистр 14. Через время Т, достаточное для записи информации в регистр 30

14, на выходе 41 блока 10 появляется сигнал единичного уровня. При этом из блока 1 памяти считывается ноль (признак того, что ветвь 2 еще не исполнялась). На выходе элемента 27 HE появляется сигнал единичного уровня, при этом таймер 6 выдает .на свой выход номера загружаемого канала номер свободного канала, например номер l,и, кроме того, на выходе блока 2 памяти 4р появляется число 2 (вес ветви 2). Через время Т, достаточное для чтения информации из блоков 1 и 2 памяти и выдачи номера свободного канала таймером 6, на выходе 42 блока 10 синхронизации появляется сигнал единичного уровня. При этом по адресу 2 в блок 5 памяти производится запись числа 1 (по адресу ветви 2 запоминается номер канала таймера 6 занятый О ее моделированием ), по адресу 1 в блок 3 памяти производится запись числа 2 (по адресу номера канала занятого моделированием ветви запоминается ее номер) В первый канал таймера 6 загружается число 2 (вес ветви 2). Через время Т5, достаточное для окончания процессов записи в блоках 5 и 3 памяти и в первом ка5 143 ветвь 2). Через время Т, достаточное для окончания операции чтения из блока 4 памяти, на выходе 47 блока

11 появляется импульсный сигнал единичного уровня, При этом в регистр

12 заносится число 2 (номер достигнутого узла). На выходе 48 блока 11 появляется сигнал единичногд уровня.

При этом блок 7 вывода информации выдает на свой информационный выход число I (номер ветви, стоящей первой в списке исходящих из первого узла графа)

Далее работа устройства проходит аналогично. Под управлением первого блока синхронизации производится запись в блок 1 памяти меток сверя.ения по адресам (номерам) всех ветвей, входящих в достигнутый узел, при этом обнуляются каналы, занятые моделированием этих ветвей и снимаются прерывания от этих каналов, если они были. Далее под управлением блока 1 О синхронизации свободные и освободившиеся каналы таймера 6 загружаются весами ветвей, исходящих из достигнутого узла и устанавливается в единицу триггер 18. Если в таймере 6 не осталось необработанных прерываний, процесс исполнения ветвей (счет импульсов в таймере 6 и в счетчике 17) продолжается. В противном случае сигнал прерывания устанавливает триггер 18 в нулевое состояние и запускает блок II синхронизации. Работа устройства прекращается, когда будет исполнена первая из ветвей, входящая в конеч » ный узел пути. После того как номер конечного узла пути (в данном случае он равен единице) записан в регистр 12, блок 16 сравнения выработает сигнал единичного уровня, который остановит блок 11 синхронизации. Работа устройства прекратится. При этом счетчик 17 хранит количество импульсов, численно равное весу кратчайшего пути из начальной в конечную вершину графа.

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

Устройство для анализа параметров графа, содержащее четыре регистра, блок сравнения, два бдока вывода информации, три блока элементов ИЛИ, четыре блока памяти, два триггера, таймер, счетчик и три

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

5 --второго блока вывода информации,ин30

ЗБ

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

7 14 суммирующему входу счетчика, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения величины кратчайшего пути в графе, в него введены пятый блок памяти, три элемента ИЛИ, элемент И и элемент НЕ, причем вход задания номера начального узла пути устройства подключен к второму входу второго блока элементов ИЛИ, выход которого подключен к информационному входу первого регистра, вход начальной установки устройства подключен к входу начальной установки таймера, к входу признака записи четвертого регистра, к первым входам первого и второго элементов ИЛИ, к входу установки в "0" счетчика и к входу установки в "1" второго триггера, выход которого подключен к информационному входу первого блока памяти, выход которого подключен к входу элемента

НЕ, выход которого подключен к входу признака чтения второго блока памяти и к входу опроса номера свободного канала таймера, выход прерывания которого подключен к первому входу элемента И, выход которого подключен к второму входу первого элемента ИЛИ, выход которого подключен к входу пуска третьего блока синхронизации и к входу установки в "0" первого триггера, выход которого подключен к второму входу элемента И, вход пуска устройства подключен к первому входу третьего элемента ИЛИ, выход которого подключен к входу пуска первого блока вывода информации, выход второго регистра подключен к первому входу третьего блока элементов ИЛИ, выход третьего регистра подключен к второму входу третьего блока эле37874 8 ментов ИЛИ, выход которого подключен к адресному входу пятого блока памяти, выход которого подключен к

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

25 третьего регистра, к входу признака чтения первого блока памяти, к входу. установки в 0" третьего регистра и к тактовому входу второго блока вывода информации соответстщ венно, третий выход второго блока синхронизации подключен к входу признака записи пятого блока памяти, к входу признака загрузки канала таймера и к входу признака записи третьего блока памяти, с первого по четвертый выходы третьего блока синхронизации подключены к входу признака чтения третьего блока памяти, к входу признака чтения четвертого

4р блока памяти, второму входу второго элемента ИЛИ и к второму входу третьго элемента ИЛИ соответственно, вы ход второго элемента ИЛИ подключен к входу признака записи первого ре45 гистра °!

437874

1437874

Я(40) 36(1

Я7(42) 38(43

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

Техред Л.Сердюкова

Корректор N. Демчик

Редактор М. Недолуженко

Заказ 5895/49

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

ЩСЮ ва пуиа

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

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

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