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

 

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

(11 4 G 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4139450/24-24 (22) 28.10.86 (46) 15.06.88. Бюл. И 22 (72) Г.С.Колесник и N.Ã.Êoëåñíèê (53) 681.333(088.8) (56) Авторское свидетельство СССР

И - 1013965, кл. С 06 Е 15/20, 1981.

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

N - !151979, кл. G 06 F 15/20, 1983.

„„SU„, 1403072 А1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ИИНИМАЛЪНОГО ПУТИ В ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процесса в диспетчерах управляющих многомашинных вычислительных систем. Цель изобретения состоит

1403072 в сокращении аппаратурных затрат.

Устройство содержит генератор I импульсов, блок 2 формирователей минимального пути, группу элементов И 3, распределитель импульсов 4, группу блоков 5 элементов И, группу сумматоров 6, группу элементов ИЛИ 7,блок 8 выбора максимального кода, группу регистров 9, надциагональную матрицу ,10 регистров ll, группу элементов задержки 12. Блок 2 содержит группу .триггеров, три группы элементов И, Изобретение относится к области вычислительной техники и может быть

;использовано при органиэации вычис лительного процесса в диспетчерах управляющих многомашинных вычисли- 5

:тельных систем.

Цель изобретения состоит в сокра-! щении аппаратурных затрат, (На фиг.l, 2 изображены функциональные схемы устройства и блока фор- 10 мирователей минимального пути; на фиг.3 — граф, на примере которого .рассматривается работа устройства.

Устройство (фиг.l) содержит гене15 ратор 1 импульсов блок 2 формироЭ вателей минимального пути, группу элементов 3 И, распределитель 4 импульсов, группу блоков элементов 5 И, !

rpynny 6 сумматоров, группу элементов 7 ИЛИ, блок 8 выбора максимального кода, группу регистров 9, наддиагональную матрицу 10, элементами которой являются регистры 11, группу элементов задержки 12. Блок 2 содержит (фиг.2) группу триггеров 13, 13,,.. °, 13 „, первую группу элементов 14„» 14«,..., 14 „, „И, вторую группу элементов 15,,15„, ° .., 15 и 1,„ И, третью группу элементов

16,, 16,,...,16„, „ И, первую групЗО пу элементов 17,,17,...,17 „ ИЛИ, вторую группу элементов 18» . 18,..., 18„ ИЛИ, регистр 19, первую группу

20 входов разрешения записи, вторую группу 21 входов разрешения записи, 35 вход 22 разрешения считывания.

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

После подачи пускового сигнала генератор 1 начинает выдачу импульсов, две группы элементов ИЛИ, регистр, первую группу входов разрешения записи, вторую группу входов разрешения записи, вход разрешения считыва ния, Сокращение аппаратурных затрат достигнуто за счет исключения из прототипа группы элементов И-НЕ, группы элементов И, триггеров, счетчика, дешифратора при дополнительном включении лишь группы элементов задержки, группы блоков элементов И и распределителя импульсов. 3 ил. первый из которых поступает на первый вход блока 5 и на вход разрешения считывания регистра 9z, с выхода которого вес дуги (1,2) поступает на второй вход сумматора 6 . Пусковой импульс также поступает на вход распределителя 4, который вьщает по первому выходу потенциал "1" на вход элемента задержки 12 и входы считывания регистров 11,, 11 з . Записанный в одном из них обратный код дуги (1,3) через элемент 7е ИЛИ поступает на первый вход блока 8, а записанный в регистре 11 вес дуги (2,3) через элемент 7 ИЛИ поступает на вход первого слагаемого сумматора 6 . Последний складывает веса дуг (1,2) и (2,3) и с инверсного выхода выдает обратный код суммы через блок 5z на второй вход блока 8, на остальных входах которого нули. Блок 8 выбирает максимальный из входных кодов и выдает его в обратном коде через выход максимального кода, на информационные входы регистров 9 начиная с регистра 9 .

С выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9>, который запоминает число, которым выражается длина минимального пути из первой в третью вершину графа.

Для графа-примера (фиг.3) на пер- вый вход блока 8 поступает обратный код 1001 веса дуги (1,3),на входы сумматора 6 †. коды 0010 и 0011 весов дуг (1,2) и (3,2), которые после сложения в обратном коде поступают на второй вход блока 8, который выбирает максимальный из входных кодов (1010).и выдает его в обратном коде

1403072 на запись в регистр 9> как величину минимального пути из первой в третью вершину графа, Блок 8 выдает также потенциал "1", который через вход

20 блока 2 поступает на вторые входы элементов 14 z>, 14 4, 14 И. Одновременно с первого выхода распределителя 4 единичный сигнал поступает через вход 21 на первые вхоцы элементов 14„> 14 > И. На выходе элемента 14 И появляется потенциал

"1", перебрасываюший в единичное состояние триггер 13 .

Второй импульс генератора 1 вновь 15 проходит на вход разрешения считывания регистра 9, и вес дуги (1,2) вновь подается на вход второго слагаемого сумматора 6 . Второй импульс поступает также на первый вход блока 20

5, а поскольку элемент 3 И открыт по второму входу единичным потенциалом с первого выхода распределителя 4, то этот импульс проходит на вход считывания регистра 9, который 25 вьщает записанный в нем код числа на вход второго слагаемого сумматора 6

Указанный импульс генератора 1 поступает также на вход распределителя 4, который, продолжая выдавать потенци- 30 ал "1" по первому выходу, вьщает этот же потенциал и по второму выходу. Taft как входы разрешения записи регистров 9 и входы разрешения считывания регистров 11 импульсные, то сохранение единичного потенциала на первом выходе распределителя 4 на них никакого влияния не оказывает, а потенциал "1" с второго выхода поступает на вход элемента задержки 12 40 и на входы разрешения считывания регистров 11,, 11, 11з, которые выдают соответственно 0 (дуги 14 в графе нет), 4,2. Сумматор 6> находит сумму чисел 2+4=6 и в обратном коде 4Б

1001 вьщает ее через открытый блок

5 на второй вход блока 8, а сумматор 6 находит сумму чисел 5+2=7 и в обратном коде через блок 5>, открытый IIQ первому входу импульсом с вы- Б0 хода элемента 3> И, вьщает на третий вход блока 8. Блок 8 определяет,что максимальным является поданный на второй вход код 1001, а потому выдает его обратный код на информационные входы регистров 9. Когда с выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9, он запоминает число 6 как длину минимального пути из первой в четвертую вершину. Блок 8 вьщает также признак максимального кода (потенциал "1"), который через вход 20 проходит на вторые входы элементов 14, 14, 14 И. Единичный сигнал с второго выхода распределителя 4 поступает через вход 2!д на первые входы элементов 14, 14, 14, И. Единичный сигнал появляется на выходе элемента 14 И и перебрасывает в единичное состояние триггер 13 .

Третий импульс генератора 1 вновь проходит на вход разрешения считывания регистра 9 и на первый вход бло-, ка 5 . Поступив на вход распределителя 4, третий импульс обусловливает задачу потенциала "1" и по третьему выходу распределителя 4. Этот потенциал поступает на вход элемента задержки 12 и на входы считывания

РегистРов 11,, 11, 11sr 11es Записанное в регистре 11, число 0 (такой дуги в графе нет) через элемент

7 ИЛИ выставляется на первый вход блока 8, а на его второй, третий и четвертый входы подаются соответст венно коды 0110, 0010, 0100, из которых максимальный код 0110 подан на второй вход. Его обратный код 1001 выставляется на информационные входы регистров 9. При поступлении сигнала с выхода элемента задержки 12 это число (9) записывается в регистр 9 как величина минимального (искомого) пути из первой в пятую вершину графа.

Одновременно блок 8 выдает потенциал

"1" через вход 20 на вторые входы элементов 14, 14 4, 14 И. Единичный сигнал с третьего выхода распределителя 4 через вход 21 - поступает на первые входы элементов 14ig, 14<р

14,14 И.На выходе элемента 14гд И появляется потенциал "1", перебрасываюший в единичное состояние триггер 13 .

Четвертый импульс генератора 1 проходит на вход разрешения считывания регистра 9, через элемент 3 И вЂ” на вход разрешения считывания регистра

9, через элемент 3 < И вЂ” на вход разрешения считывания регистра 9д, а также на первые входы блоков 5, 5з, 5 . Появление на входе распределителя 4 четвертого импульса генератора

1 приводит к выдаче потенциала "1" по четвертому выходу распределителя

4 на вход 22 разрешения считывания

1ч03072 б делитель импульсов, причем вход заи далее на вторые входы элементов

15, и 16 И. Сигнал с входа 22 проходит через открытые элементы 16 И до тех пор, пока не будет найден первый в последнем столбце находящийся в состоянии 1 триггер 13; в данном примере это триггер 13 . Поэтому единичный сигнал считывания проходит через элементы 16„ и 15 И и 18 ИЛИ на последний, пятый, информационный вход регистра 19 (информационный вход пуска генератора импульсов является входом пуска устройства, выход генератора импульсов соединен с входом распределителя импульсов, входом разрешения считывания первого регистра группы, первым входом первого блока элементов И группы и первыми входами элементов И группы, выходы

k-x элементов И группы (k=1 n-3) подключены к входам разрешения считывания (k+1)-х регистров группы и первым входам (k+1)-х блоков элементов

10

его пятого разряда), в котором запишется 1. Во-первых, указанный импульс И группы, р-й выход распределителя через элемент 17 ИЛИ поступит на вто7. рой вход элемента 16„И, открытый единичным потенциалом с выхода триггера 13„, и далее на информационимпульсов (р= l, и-3) соединен с р-м входом разрешения записи второй группы блока формирователей минимального пути графа, входом разрешения считыный вход его первого разряда, Единичшины графа, через который проходит искомый минимальный путь, длина (9) которого записана в регистре 9 . В и входом р-ro элемента задержки

1 группы, выход которого соединен с входом разрешения записи (р+1) -го ре25 гистра группы, выход которого соединен с входом второго слагаемого (р+1)-го сумматора группы, инверсный выход которого подключен к— второму входу (р+1)-ro блока элементов И группы, выход которого соединен с (р+2)-м входом блока выбора макси-. мального кода, выход максимального кода которого подключен к информационным входам k-x регистров группы

35 (k=2, п-l), (n-1)-й выход распределителя импульсов соединен с входом разрешения чтения блока формирователей минимального пути графа, входом ос анова генератора импульсов и

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

k-й строки наддиагональной матрицы регистров (k=1, и-2) объединены и подключены к входам k-го элемента

45 ИЛИ группы, выход регистра (n-1) -й строки подключен к входу первого слагаемого (n-2)-ro сумматора группы, (n-2)-й выход распределителя импульсов соединен с (и-2)-м входом разре50 шения записи второй группы блока формирователей минимального пути графа, входом разрешения считывания (n-2)-го столбца матрицы регистров и входом (и-2)-го элемента задержки группы, 55 выход которого подключен к входу разрешения записи (п 1)-го регистра группы, остальных регистрах 9 записаны длины минимальных путей от первой до соответствующих вершин графа ° Единичный сигнал с четвертого выхода распределителя ч проходит также на вход останова генератора 1 и на выход признака окончания работы устройства.

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

Устройство для определения минимального пути в графе, содержащее генератор импульсов, группу элементов И, группу сумматоров, группу элементов ИЛИ, блок выбора максимального кода, группу регистров, блок формирователей минимального пути графа и наддиагональную матрицу регистров размерности (n-1) (п-2), где n — число вершин графа, причем выход первого элемента ИЛИ группы соединен с первым входом блока выбора максимального кода, выходы k-x элементов ИЛИ группы (k=2,п-2) подключены к входам первого слагаемого (k-1)-х сумматоров группы, а выходы признаков максимального кода блока выбора максимального кода соединены с соответствующими входами разрешения записи первой группы блока формирователей минимального пути графа, о т л и— ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит группу блоков элементов И, группу элементов задержек, распреные состояния первого, второго и пя- 20 вания р-ro столбца матрицы регистров, того разрядов регистра 19 укажут вер- вторым входом р-го элемента И группы

1403072

1403072

Составитель И.Ершов

Техред М.Дидык

Редактор О.Спесивых

Корректор М.Максимишинец

Заказ 2862/41

Тираж 704

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

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

Подписное

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