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

И 9) (И) РЕСПУБЛИ И 4 С 06 ГОСУДАРСТБЕКНЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ НИ(5 А) УСТРОЙСТ МАЛЪНОГО ПУТИ ДЛЯ ОПГРАФЕ НИЯ ИИНИк вычи ыть ис носится,Колесни и может анизаци льство СССР 15/20, 198. ство СССР 15/20, 1983,ычислирах уп- слитель пользова при орроцесса ногома пе ельного и авляющих м ых систем. нных выч с виде т С 06 состо зобрете(57) Изобретени лительной техни 3072 А1403072 в сокращении аппаратурных затрат, Устройство содержит генераторимпульсов, блок 2 формирователей минимального пути, группу элементов И 3, распределитель импульсов 4, группу блоков 5 элементов И, группу сумматоров 6, группу элементов ИЛИ 7,блок 8 выбора максимального кода, группу регистров 9, надциагональную матрицу ,10 регистров 11, группу элементов задержки 12. Блок 2 содержит группу триггеров, три группы элементов И,Изобретение относится к областивычислительной техники и может быть;использовано при органиэации вычислительного процесса в диспетчерахуправляющих многомашинных вычисли1тельных систем.Цель изобретения состоит в сокращении аппаратурных затрат,На фиг.1, 2 изображены функциональные схемы устройства и блока формирователей минимального пути; нафиг,З - граф, на примере которогорассматривается работа устройства.Устройство (фиг.1) содержит гене 15ратор 1 импульсов блок 2 формиро 9вателей минимального пути, группуэлементов 3 И, распределитель 4 импульсов, группу блоков элементов 5 И,группу 6 сумматоров, группу элементов 7 ИЛИ, блок 8 выбора максимального кода, группу регистров 9, наддиагональную матрицу 10, элементамикоторой являются регистры 11, группуэлементов задержки 12. Блок 2 содержит (фиг.2) группу триггеров 13,13, ,, 13 первую группу элементов 14 , 14 14 ь,И, вторую группу элементов 15, ,1515, И, третью группу элементов16 1616 ь ,И, первую групЗОпу элементов 171717 ИЛИ,вторую группу элементов 18 , 18,.,18 ИЛИ, регистр 19, первую группу20 входов разрешения записи, вторуюгруппу 21 входов разрешения записи, 35вход 22 разрешения считывания,Устройство работает следующим образом,После подачи пускового сигнала генератор 1 начинает выдачу импульсов,две группы элементов ИЛИ, регистр,первую группу входов разрешения записи, вторую группу входов разрешения записи, вход разрешения считывания, Сокращение аппаратурных затратдостигнуто за счет исключения из прототипа группы элементов И-НЕ, группыэлементов И, триггеров, счетчика, дешифратора при дополнительном включении лишь группы элементов задержки,группы блоков элементов И и распределителя импульсов. 3 ил,первый из которых поступает на первый вход блока 5 и на вход разрешения считывания регистра 9, с выхода которого вес дуги (1,2) поступает на второй вход сумматора 6 . Пусковой импульс также поступает на вход распределителя 4, который вьщает по первому выходу потенциал "1" на вход элемента задержки 12и входы считывания регистров 11 11 з, Записанный в одном из них обратный код дуги (1,3) через элемент 7 ИЛИ поступает на первый вход блока 8, а записанный в регистре 11вес дуги ( 2,3) через элемент 7 ИЛИ поступает на вход первого слагаемого сумматора 6, Последний складывает веса дуг (1,2) и (2,3) и с инверсного выхода выдает обратный код суммы через блок 5 на второй вход блока 8, на остальных входах которого нули. Блок 8 выбирает максимальный из входных кодов и выдает его в обратном коде через выход максимального кода, на информационные входы регистров 9 начиная с регистра 9 . С выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9, который запоминает число, которым выражается длина минимального пути из первой в третью вершину графа,Для графа-примера (фиг,З) на пер- вый вход блока 8 поступает обратный код 1001 веса дуги (1,3),на входы сумматора 6 в . коды 0010 и 0011 весов дуг (1,2) и (3,2), которые после сложения в обратном коде поступают на второй вход блока 8, который выбирает максимальный из входных кодов (1010).и выдает его в обратном кодена запись в регистр 9 как величину минимального пути из первой в третью вершину графа, Блок 8 выдает также потенциал "1", который через вход 20 г блока 2 поступает на вторые входы элементов 14 г, 14 г 4, 14 И, Одновременно с первого выхода распределителя 4 единичный сигнал поступает через вход 21 э на первые вхоцы 10 элементов 14, 14 гз И. На выходе элемента 14 И появляется потенциал "1", перебрасываюший в единичное состояние триггер 13 г.Второй импульс генератора 1 вновь 15 проходит на вход разрешения считывания регистра 9 , и вес дуги (1,2) вновь подается на вход второго слагаемого сумматора бг. Второй импульс поступает также на первый вход блока 20 5 , а поскольку элемент 3 И открыт по второму входу единичным потенциалом с первого выхода распределителя 4, то этот импульс проходит на вход считывания регистра 9, который 25 вьщает записанный в нем код числа на вход второго слагаемого сумматора 6 Указанный импульс генератора 1 поступает также на вход распределителя 4, который, продолжая выдавать потенци ал "1" по первому выходу, вьщает этот же потенциал и по второму выходу, Так как входы разрешения записи регистров 9 и входы разрешения считывания регистров 11 импульсные, то сохранение единичного потенциала на первом выходе распределителя 4 на них никакого влияния не оказывает, а потенциал "1" с второго выхода поступает на вход элемента задержки 12 40 и на входы разрешения считывания регистров 11, , 11 г, 11 з, которые выдают соответственно 0 (дуги 14 в графе нет), 4,2. Сумматор 6 находит сумму чисел 2+4=6 и в обратном коде 45 1001 вьщает ее через открытый блок 5 г на второй вход блока 8, а сумматор 6 находит сумму чисел 5+2=7 и в обратном коде через блок 5, открытый по первому входу импульсом с вы хода элемента Зэ И, вьщает на третий вход блока 8. Блок 8 определяет,что максимальным является поданный на второй вход код 1001, а потому выдает его обратный код на информационные 55 входы регистров 9, Когда с выхода элемента задержки 12 сигнал поступает на вход разрешения записи регистра 9, он запоминает число 6 как длину минимального пути из первой в четвертую вершину, Блок 8 вьщает такжепризнак максимального кода (потенциал "1"), который через вход 20 г проходит на вторые входы элементов 14 г,14 г, 14 г И. Единичный сигнал с второго выхода распределителя 4 поступает через вход 21 на первые входыэлементов 14, 14 14, И. Единичный сигнал появляется на выходе элемента 14 г И и перебрасывает в единичное состояние триггер 1 Зг.Третий импульс генератора 1 вновьпроходит на вход разрешения считывания регистра 9 г и на первый вход бло-,ка 5 . Поступив на вход распределителя 4, третий импульс обусловливает задачу потенциала "1" и по третьему выходу распределителя 4. Этот потенциал поступает на вход элемента задержки 12 и на входы считываниярегистров 11 11 г, 11 з ., 11 . Записанное в регистре 11, число 0 (такой дуги в графе нет) через элемент 71 ИЛИ выставляется на первый вход блока 8, а на его второй, третий и четвертый входы подаются соответственно коды 0110, 0010, 0100, из которых максимальный код 0110 подан навторой вход. Его обратный код 1001выставляется на информационные входырегистров 9. При поступлении сигналас выхода элемента задержки 12 эточисло (9) записывается в регистр 9как величина минимального (искомого)пути из первой в пятую вершину графа.Одновременно блок 8 выдает потенциал "1" через вход 20 г на вторые входы элементов 14 гз, 14 г 4, 14 г И, Единичный сигнал с третьего выхода распределителя 4 через вход 21 - поступает на первые входы элементов 14, 14 г, 14,14 И,На выходе элемента 14 г И появляется потенциал "1", перебрасываюший в единичное состояние триггер 13 г 5Четвертый импульс генератора 1 про.ходит на вход разрешения считывания регистра 9 г, через элемент Зэ И - на вход разрешения считывания регистра 9, через элемент 3И - на вход разрешения считывания регистра 9, а также на первые входы блоков 5 г, 5 э, 5. Появление на входе распределителя 4 четвертого импульса генератора 1 приводит к выдаче потенциала "1" по четвертому выходу распределителя 4 на вход 22 разрешения считывания1403072 б делитель импульсов, причем вход за и далее на вторые входы элементов15, и 16 И. Сигнал с входа 22 проходит через открытые элементы 16 Идо тех ггор, пока не будет найден первый в последнем столбце находящийсяв состоянии 1 триггер 13; в данномпримере это триггер 13 . Поэтомуединичный сигнал считывания проходитчерез элементы 16 и 15 .И и 18 ИЛИна последний, пятый, информационныйвход регистра 19 (информационный вход пуска генератора импульсов являетсявходом пуска устройства, выход генератора импульсов соединен с входомраспределителя импульсов, входомразрешения считывания первого регистра группы, первым входом первогоблока элементов И группы и первымивходами элементов И группы, выходыМ-х элементов И группы (1=1,п) подключены к входам разрешения считывания (1+1)-х регистров группы и первым входам (1+1)-х блоков элементов 5 10 его пятого разряда), в котором запишется 1. Во-первых, указанный импульс И группы, р-й выход распределителя через элемент 17 ИЛИ поступит на втоарой вход элемента 16 И, открытый единичным потенциалом с выхода триггера 13 , и далее на информационный вход его первого разряда, Единичимпульсов (р=1, и) соединен с р-мвходом разрешения записи второй группы блока формирователей минимального пути графа, входом разрешения считышины графа, через который проходитискомый минимальный путь, длина (9)которого записана в регистре 9. В и входом р-го элемента задержки1группы, выход которого соединен свходом разрешения записи (р+1) -го ре 25гистра группы, выход которого соединен с входом второго слагаемого(р+1)-го сумматора группы, инверсный выход которого подключен к -второму входу (р+1)-го блока элементов И группы, выход которого соединенс (р+2)-м входом блока выбора макси-,мального кода, выход максимальногокода которого подключен к информационным входам 1-х регистров группы35 (1 с=2, п), (п)-й выход распределителя импульсов соединен с входомразрешения чтения блока формирователей минимального пути графа, входом османова генератора импульсов иявляется выходом признака окончанияработы устройства, вйходы регистров1-й строки наддиагональной матрицырегистров (1=1, и) объединены иподключены к входам 1-го элемента45 ИЛИ группы, выход регистра (и)-йстроки подключен к входу первого слагаемого (и)-го сумматора группы,(и)-й выход распределителя импульсов соединен с (и)-м входом разре 50 шения записи второй группы блока формирователей минимального пути графа,входом разрешения считывания (и)-гостолбца матрицы регистров и входом(и)-го элемента задержки группы,55 выход которого подключен к входу разрешения записи (п 1)-го регистра группы,остальных регистрах 9 записаны длины минимальных путей от первой до соответствующих вершин графаЕдиничныйсигнал с четвертого выхода распределителя ч проходит также на вход останова генератора 1 и на выход признака окончания работы устройства. Формула изобретенияУстройство для определения минимального пути в графе, содержащее генератор импульсов, группу элементов И, группу сумматоров, группу элементов ИЛИ, блок выбора максимального кода, группу регистров, блок формирователей минимального пути графа и наддиагональную матрицу регистров размерности (и) (п), где и - число вершин графа, причем выход первого элемента ИЛИ группы соединен с первым входом блока выбора максимального кода, выходы Е-х элементов ИЛИ группы (1=2,п) подключены к входам первого слагаемого Ь)-х сумматоров группы, а выходы признаков максимального кода блока выбора максимального кода соединены с соответствующими входами разрешения записи первой группы блока формирователей минимального пути графа, о т л и - ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит группу блоков элементов И, группу элементов задержек, распреные состояния первого, второго и пя вания р-го столбца матрицы регистров, того разрядов регистра 19 укажут вер- вторым входом р-го элемента И группы1403072 РРГЗ Составитель И.ЕршТехред И.Дидык Заказ 28 б 2/41 Тираж 70 писное ВН ИИПИ Государственного по делам изобретений и 113035, Москва, Ж, Раушс зводственно-полиграФическое предпри г Ужгород Проектна Редактор О.Спесивых омитета СССРоткрытийан наб., д. ч/ ректор И,Иаксимишинец