Устройство для решения задач на графах — SU 1837312 (original) (raw)
-(lЯЩ) (ммчЕСВФи,91 ЕКА ПИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИДЕТЕЛЬСТ) 4784401/24 ) 18.01.90 ) 30.08.93. Бюл. М 32 ) В.Я. Певнев, С,А. Ильин, С,В. Листрой, В.В. Ковальчук и В.Н, Мариян ) Авторское свидетельство СССР 485451, кл. О 06 Р 15/20, 1971.Авторское свидетельство СССР 640314, кл. 6 06 0 7/122, 1978.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ (57) Изобретение относится к вычислительной технике и предназначено для использования при решении задач комбинаторной оптимизации на графах. Цель изобретения - повышение быстродействия. Это достигается тем, что устройство для решения задач на графах содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор 3, В процессоров 4 (где В - число вершинф) б 5 я. 1 З.п, ф-лы, 5 и:,1837312игГ Составитель В Певн Техред М.Моргентал едакКорректор М Керецман Заказ 2867 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5город, ул,Гагарина, 101изводственно-издательский комбинат "ПатенИзобретение относится к кибернетике и вычислительной техники и предназначено для использования при решении задач комбинаторной оптимизации на графах.Целью изобретения является повышение быстродействия за счет распараллеливания операции нахождения кратчайших путей и устранения зависимости времени определения кратчайшего пути от величин весов ребер.На фиг, 1 показана структурная схема устройства для определения кратчайших путей; на фиг. 2 - функциональная схема блока управления; на фиг. 3 - функциональная схема коммутатора; на фиг. 4 - функциональная схема процессора; на фиг. 5- функциональная схема блока сравнения.Устройство для определения кратчайших путей (фиг. 1) содержит генератор 1 тактовых импульсов, блок 2 управления, коммутатор 3, процессоры 4.14,В, блок 5 сравнения, выход 6 генератора тактовых импульсов, выход 7 и группу выходов 8 блока 2 управления, выходы 9 коммутатора, выходы 10.11 О,В веса пути, выходы 11,111.В номеров вершин и веса пути, входы 12,1.12,В останова процессоров, выходы 13,1,13,В блока 5 сравнения, вход 14 номера корневой вершины и вход 15 значения числа вершин графа.Генератор 1 тактовых импульсов с выхода 6 подает на вход синхронизаии блока 2 управления последовательность тактовых импульсов, управляющих работой элементов и блоков устройства, Блок 2 управления предназначен для записи номера корневой вершины и выдачи управляющих сигналов на остальные блоки устройства. Для этого выход 7 блока 2 управления соединен с управляющим входом коммутатора 3, а группа выходов 8 подключена к входу кода операции каждого процессора 4 1.4.В,Коммутатор 3 служитдля передачи кратчайшего пути определенного ранга, принятого с одного из процессоров, на все процессоры 4, Для этого его выходы 9 подключены к первым информационным входам каждого процессора 4,14.В. Процессоры обеспечивают формирование путей различных рангов, выявление среди двух путей пути с меньшим весом, передачу путей (перечень вершин и вес) в коммутатор 3, а весов путей - в блок 5 сравнения и запись кратчайшего пути к данной вершине, Выходы 10.1,10.В веса пути соответственно процессоров 4.1.4,В подключены к информационным входам блока 5 сравнения, а выходы 11.1.11.В номеров вершин и веса пути этих же процессоров 4,14.В подключены к информационным входам коммутатора 3. Блок 5 сравнения служит для выявления среди поступивших на его входы чисел (весов путей) меньшего и передачи управляющего сигнала на один из процес соров 4,1.4.В, Для этого выходы 13 блока 5 ,. сравнения распределены и подключены квходам 12.1,12.В останова процессоров 4.1,4.В.В исходном состоянии в лроцессорах 10 4.14.В записаны номера "своих" вершин исвязи этих вершин с остальными вершинами графа.Устройство для определения кратчайших путей работает следующим образом.15 Номер корневой вершины со входа 15 устройства поступает на вторые информационные входы всех процессоров 4.14,В.Процессор, номер которого совпал с номером корневой вершины, из дальнейшей ра боты исключается путем закрытия егопервого информационного входа. В процессорах, вершины которых имеют связь с корневой вершиной, по управляющим сигналам, поступающим на их входы кода 25 операции с блока 2 управления, сформируются и запомнятся пути первого ранга, а их веса с выходов 10 передадутся в блок 5 сравнения. В процессорах, вершины которых не имеют связи с корневой вершиной, 30 формирования путей первого ранга не произойдет и с их выходов 10 на блок 5 сравнения будут переданы максимально большие числа (т,е. во всех разрядах выхода 10 будут переданы "1").35 В блоке 5 сравнения произойдет выделение минимального. числа из всех поступивших от процессоров 4 и выдача управляющего сигнала об этом на соответствующий процессор, В этом процессоре 40 кратчайший путь запомнится и передастся свыхода 11 перечня вершин и веса пути в коммутатор 3 и, кроме того, закроется первый информационный вход этого процессо-.ра, исключая его из дальнейшей работы 45 (кратчайший путь к данной вершине определился - им стал путь первого ранга),Кратчайший путь первого ранга из коммутатора 3 по сигналу с выхода 7 блока 2 управления передастся на все процессоры 50 4.14.В (в исключенные из работы процессоры этот путь не пройдет). В процессорах, вершины которых имеют связь с последней вершиной полученного кратчайшего пути первого ранга, сформируются пути второго 55 ранга: в процессорах, где не было путейпервого ранга, путь второго ранга запомнится, а его вес передается в блок 5 сравнения; в процессорах, где уже сформированы пути первого ранга. произойдет сравнение весов путей первого и второго рангов им ньший из путей (по весу) запомнится, а ег вес передастся в блок 5 сравнения. В и цессорах, вершины которых не имеют св зи с последней вершиной полученного кр тчайшего пути первого ранга, формирова ия путей второго ранга не произойдет, а н блок 5 сравнения с этих процессоров бу ут переданы максимально большие числа также максимально большое число будет передано с процессора, в котором записалкратчайший путь первого ранга. В блоке равнения опять произойдет выделение нимального числа; с соответствующего оцессора кратчайший путь (это может ть путь или первого, или второго ранга) 15 едастся в коммутатор 3, а сам процессор лючится иэ дальнейшей работы; в просорах снова сформируются новые пути, ди них определится кратчайший и т,д, до пор, пока ко всем вершинам не сформи тся кратчайшие пути, Это произойдет за 1) циклов работы блока 2 управления.Блок 2 управления (фиг. 2) содержит л сравнения 16, счетчик 17, распредели- и 18, 19 и 20 импульсов, триггер 21, 25 Вход 6 синхронизации блока 2 управлея соединен с входом синхронизации раседелителя 18 импульсов. Распределитель имеет пять выходов, которые подключеследующим образом: первый - к входу 30 тчика 17 и входу распределителя 19 имьсов, второй - соответствует выходу 8.3, тий - к входу синхронизации распредееля 20 импульсов, четвертый - к входу ановки в единицу триггера 21, пятый - к 35 ду установки в ноль триггера 21 и, кроме о, образует выход 7 блока 2 управления, ход переноса счетчика 17 соединен со рым информационным входом узла 16 внения, с первым информационным вхо ср те РУ итр д которого соединен вход режима 14, а в одузла 16 сравнения подключен к входу п знака запуска/останова распределител 8 импульсов. (В) выход распределител 19 импульсов соответствует выходу 8,1. (В ) выход распределителя 20 импульсов со тветствует выходу 8.2. Выход триггера 21 соответствует выходу 8,4. Выходы 8.1, 8.,8.3, 8.4, образуют группу выходов 8 блока 2 управления.В исходном состоянии триггер 21 и оста ьные элементы памяти - в нулевом сост янии.Блок 2 управления работает следующим об азам. Последовательность тактовых импу ьсов, поступающая на вход 6, вызывает по вление импульсов на выходах распредели еля 18, Импульс с первого выхода з с вает "1" в счетчик 17 и поступает на си хронизации распределителя 19, на апивход пер цессоров 4.14 ИЛИ 24, тригге вом выходе которого появляется импульс, поступающий на выход 8,1, Импульс со второго выхода распределителя 18 поступает на выход 8,3. Импульс с третьего выхода распределителя 18 поступает на вход синхронизации распределителя 20, на первом выходе которого появляется импульс, поступающий на выход 8.2. Импульс счетвертого выхода распределителя 18 поступает на вход установки в единицу триггера 21, переводит его в единичное состояние и высокий потенциал с выхода триггера поступает на выход 8,4,Импульс с пятого выхода распределителя 18 поступает на выход 7 блока 2 управления и, кроме того, на вход установки в ноль триггера 21 и переводит его в нулевое состояние - высокий потенциал с выхода 8,4 снимается, На этом заканчивается первый цикл работы блока 2 управления. При последующих циклах в счетчик 17 записываются "единицы", импульсы появляются на последующих выходах распределителей 19 и 20, а также на выходах 7, 8.3, 8.4. Число полных циклов работы блока 2 управления равно (В), На В-ом цикле импульс появляется только на первом выходе распределителя 18 - в счетчик 17 записывается В-ая "единица", в узле 16 сравнения число "В" с входа режима 14 совпадает с числом "В" из счетчика 17 и импульс с выхода узла 16 сравнения прекратит работу распределителя 18 импульсов,Коммутатор 3 (фг, 3) содержит сборки элементов ИЛИ 22.122,В и сборки элементов И 23,123.В.Управляющий вход 7 подключен к разрешающим входам сборок элементов И 23,1.23.В. Информационные входы 11,1.11. В подключены к входам сборок элементов ИЛИ 22,122,В; вход 11,1 подключен к первым входам сборок элементов ИЛИ 22.1,22,В, вход 11,2 - к вторым входам и т,д. Выходы сборок элементов ИЛИ 22.1,22,В соединены с информационными входами соответствующих сборок элементов И 23,1,23.В, выходы которых образуют выход 9 коммутатора 3.Комм татар 3 работает следующим образом. Информация о кратчайшем пути какого-то ранга (перечень номеров вершин и вес пути) с одного из входов 11.111.В,через сборки элементов ИЛИ 22.122.В поступает на информационные входы сборок элементов И 23.1.23.В и когда на их разрешающие входы поступает сигнал с входа 7, информация о кратчайшем пути поступает на выход 9.Каждый из про . В (фиг. 4) содержит элемент р 25, сбор 1837312ки элементов И 26.126.8, элементы И 27 и 28, регистр 29, схему 30 совпадения, триггер З 1., сборки элементов И 32 и 33, линию 34 задержки, сборки элементов И 35,135.(В), сборки элементов ИЛИ 36 Л.36.(8-1), регистры 37.137,8 сумматор 38, сборки элементов И 39 Л 39.(8-1), сборку элементов ИЛИ 40, сборку 41 регистров, включающую регистры 42.142.(8-1) и 43.143.(8-1), схемы 44.144,(8-1) совпадения, сборки элементов И 45,1.45.(8-1), сборку элементов ИЛИ 46, элемент ИЛИ 47, триггер 48, сборки элементов И 49.149,(8+1), регистры 50,150,(В+1), сборки элементов И 51 и 52, схему 53 сравнения, регистр 54, сборку элементов И 55, сборки элементов И 56 и 57.157,8,Первый информационный вход 9 подключен к информационным входам сборок элементов И 26.126.8. Второй информационный вход подключен к информационному входу сборки элементов И 32 и первому входу схемы 30 совпадения. Вход останова 12,1 (вхады 12.2.12.8 в процессорах 4.2,4.8) подключен к первому входу элемента ИЛИ. 24 и разрешающим входам сборок элементов И 57 Л,57.8. Вход 58 соответствует выходу 8,4 блока 2 управления и подключен к разрешающему входу элементов И 27 и 28; вход 59 соответствует выходу 8.3 блока 2 и подключен к второму входу триггера 48; вход 60 соотвтстует выходу 8.2 блока 2 и подключен к разрешающим входам сборок элементов И 39.1,39,(8-1); вход 61 соответствует выходу 8.1 блока 2 и подключен к разрешающим входам сборок элементов И 35 ЛЗ 5.(8-1). Подключение элементов внутри каждого процессора одинаковы, поэтому рассмотрим их на примере процессора 4.1. Выход регистра 29, в котором хранится номер "своей" вершины, подключен к информационному входу сборки элементов И 33 и второму входу схемы 30 совпадения, выход которой подключен к входу триггера 31, Единичный выход триггера 31 соединен с разрешающими входами сборок элементов И 32 и 33, а нулевой выход - с входом линии 34 задержки, выход которой подключен к устанавливающему входу регистра 37 Л и второму входу элемента ИЛИ 24, выход которого соединен с входом триггера 25, единичный выход которого подключен к разрешающим входам сборок элементов И 26.126,8 и информационному входу элемента И 27, выход которого соединен с разрешающим входом сборки элементов И 56, а нулевой выход триггера 25 подключен к информационному входу элемента И 28, выход которого соединен с разрешающим входом сборки элементов И 55.Выходы сборок элементов И 26,126,Вподключены к первым входам соответству ющих сборок элементов ИЛИ 36.136(В)и сумматора 38, Выход сборки элементов И 32 подключен к информационному входу регистра 37.1. Выход сборки элементов И 33 подключен к информационным входам сбо рок элементов И 35 Л 35.(8-1), выходы которых подключены к вторым входам соответствующих сборок элементов ИЛИ 36.136.(8-1), выходы которых соединены с входами регистров 37.237.8,15 Регистр 37.1 служитдля хранения номера корневой вершины, регистры 37.237.В - для хранения номеров вершин, образующих пути рангов от первого до (В)-го к "своей" вершине, сумматор 38-для получе ния веса пути соответствующего ранга, Выходы регистров 37 Л 37.(8-1) подключены к информационным входам соответствующих сборок элементов И 39.139.(8-1) и 49,149,(8-1), выход регистра 37,8 подклю чен к информационному входу сборки элементов И 49.8.В ыходы сборок элементов И39.139.(8-1) соединены со входами сборки элементов ИЛИ 40, выход которой подклю чен к первым входам схем совпадения44.144.(8-1). В сборке регистров 41 хранятся связи "своей" вершины с остальными вершинами графа, причем в регистрах 42 Л 42.(8-1) хранятся номера вершин, а в 35 регистрах 43 Л 43.(8-1) - веса ребер, соединяющих эти вершины со "своей" (при отсу 1- ствии связи в соответствующих регистрах 43 Л 43.(8-1) записаны "нули"), Выходы регистров 4 ЗЛ 43,(8-1) подключены к инфор 40 мационным входам соответствующихсборок элементов И 45,145.(8-1). Выходы регистров 42.142,(8-1) подключены к вторым входам соответствующих схем совпадения 44.144.(8-1, выходы которых 45 подключены к разрешающим входам соответствующих сборок элементов И 45.145.(8-1), выходы которых соединены со входами сборки элементов ИЛИ 46, вы. ход которой подключен к второму входу сум матора 38 и входу элемента ИЛИ 47.Выход сумматора 38 подключен к информационным входам сборок элементов И 49.(В+1) и 51. Выходэлемента ИЛИ 47 соединен с первым входом триггера 48, выход которого 55 подключен к разрешающим входам сборок элементов И 51 и 52, Выходы сборок элементовы И 49,149.(8+1) подключены к входам соответствующих регистров 50,150.(В+1),.в которых хранится информация о кратчайшем пути (номера вершин и вес пути).Выходы регистров 50.2.50.(В+1) подлючены к информационным входам саотетствующих сборок элементов И 7.1.57.В и, кроме того, выход регистра 0.(В+1) подключен к информационным вхоам сборок элементов И 52 и 56, Выходы борок элементов И 51 и 52 соединены со ходами схемы 53 сравнения, выход котоой подключен к разрешающим входам сбоок элементов И 49.149.(В+1). Регистр 54 лужит для записи максимально большого исла, его выход подключен к информационому входу сборки элементов И 55, Выходы сборок элементов И 55 и 56 соединены межу собой и образуют выход 10,1, а выходы борок элементов И 57.1.57.В образуют ыход 11,1 процессора 4.1. Аналогично обазуются выходы 10.210.В и 11,211,В роцессоров 4,24. В,В исходном состоянии в регистре 29 аписан номер "своей" вершины, регистры 7,137,В и сумматор 38 обнулены, в регистрах 42.142.(В) записаны номера вершин графа (кроме "своей"), в регистрах 3.143.(В) - веса ребер, связывающих оответствующие вершины со "своей" (при тсутствии ребра в регистре - "0"), регистрь 1 0,150,В обнулены, в регистрах 50,(В+1) и 4 записано максимально большое число (т.е; во всех разрядах - "1"), триггеры 25 и 31в единичном состоянии, триггер 48 - в нулевом,Процессор 4,1 работает следующим образом. На второй информационный вход 15 поступает номер корневой вершины, который через открытую сборку элементов И 32 запишется в регистр 37.1, а также поступит на первый вход схемы 30 совпадения. Если номер корневой вершины совпадает с номером "своей" вершины, то сработает схема 30 совпадения и перевернет триггер 31 в нулевое состояние: низкий потенциал с его единичного выхода закроет сборки элементов И 32 и 33 (запрещается пропуск номера корневой вершины в регистр 37,1 и номера "своей" вершины на сборки элементов И 35.135.(В, высокий потенциал с нулевого выхода через линию 34 задержки приведет в исходное состояние ("очистит") регистр 37.1, а также через элемент ИЛИ 24 поступит на, вход триггера 25 и переведет его в нулевое состояние, тем самым закроются сборки элементов И 26.126.В, т,е. в процессор не будет поступать информация из коммутатора 3 - таким образом, процессор из дальнейшей работы устройства исключается; кроме того, низкий потенциал с единичного выхода триггера 25 закроет элемент И 27, а высокий потенциал с его нулевого выхода откроет элемент И 28. Если 5 10 15 20 25 30 35 40 45 50 55 номер корневой вершины не совпал с номером "своей", то триггер 31 остается в единичном состоянии: в регистре 37.1 останется записанным номер корневой вершины, который с выхода регистра поступит на входы сборок элементов И 39.1 и 49.1, комер "своей" вершины поступит на информационные входы сборок элементов И 35.135,(В), сборки элементов И 26,1,26,В останутся открытыми, При поступлении первого импульса на вход 61 откроется сборка элементов И 35.1 и номер "своей" вершины через сборки элементов И 35.1 и ИЛИ 36.1 запишется в регистр 37,2, а с его выхода поступит на входы сборок элементов И 39,2 и 49,2. При поступлении первого импульса на вход 60 откроется сборка элементов И 39.1 и номер корневой вершины через сборки элементов И 39.1 и ИЛИ 40 поступит на первые входы всех схем совпадения 44,1.44,(В).На выходе одной из схем 44,1 совпадения (схемы, на второй вход которой подается номер корневой вершины из регистра 42,1, где 1=1 Впоявится высокий потенциал, который откроет соответствующую сборку элементов И 45. и через нее, а также через сборку элементов ИЛИ 46, вес ребра, соединяющего корневую и "сваю вершины, запишется в сумматор 38 и поступит на вход элемента ИЛИ 47. При этом триггер 48 переворачивается в единичное состояние и высоким поенциалом со своего выхода открывает сборки элементов И 51 и 52, На информационный вход сборки элементов И 51 из сумматора 33 поступает вес ребра, соединяющего корневую и "свою" вершины, а на информационный вход сборки элементов И 52 - максимально большое число из регистра 50.В+1).Вес ребра и большое число сравниваются в схеме 53 сравнения схема 53 сравнения работает таким образом, что сигнал на ее выходе появляется в случае, если число, поступающее на первый вход, меньше числа, поступающего на второй правый) вход) и на ее выходе появится потенциал, который откроет сборки элементов И 49.149.(В+1). Путь первого ранга запишется в регистры 50,", корневая вершина),50,2"своя" вершина) и 50,(В+1) (вес пути). Импульс со входа 59 перевернет триггер 48 в исходное состояние, "Своя" вершина и вес пути из регистров 50,2 и 50.(В+1) поступают на информационные входы сборок элементов И 57.1 и 57.В, кроме того, вес пути поступает на информационный вход сборки элементов И 56. (Если связи между корневой и "сваей вершиной нет, тс с соответствующего регистра 43.1 Б сумматор 38 ничего не запишется, триггер10 1520 25 30 35 50 55 48 останется в исходном положении, схема 53 сравнения не сработает, в регистры 50,1.50. В ничего не запишется, максимально большое число из регистра 50.(В+1) поступит на информационный вход сборки элементов И 56). Импульс со входа 58 через открытый элемент И 27 поступит на разрешающий вход сборки элементов И 56, пропуская число с ее входа на выход 10.1.Если вес пути, сформированного в процессоре 4.1, является минимальным среди весов путем первого ранга, то на входе останова 12,1 появляется импульс, который откроет сборки элементов И 57,157.В, пропуская этот минимальный путь первого ранга ("свою" вершину и вес пути) на вход 11.1 и через элемент ИЛИ 24 перевернет триггер 25 в нулевое состояние, открывая элемент И 28 и закрывая элемент И 27 и сборки элементов И 26.126.В, тем самым исключая процессор 4,1 из дальнейшей работы, т.е, сформированный в процессоре путь является кратчайшим к данной вершине, Если вес пути, сформированного в процессоре 4.1 не является минимальным, то импульс на вход 12.1 не поступит, В конце цикла работы устройства со входа 58 снимается высокий потенциал.Таким образом, после первого цикла работы устройства (цикла выдачи импульсов с первого по пятый распределителем 18 импульсов блока 2 управления) в ряде процессоров сформируются пути первого ранга и среди них выберется кратчайший, который передается на все процессоры, кроме того, где этот путь выявлен, При втором цикле работы устройства с первого информационного входа 9 через сборки элементов И 26.1, 26.В и ИЛИ 36.1 в регистр 37.2 запишется номер второй вершины кратчайшего пути первого ранга, а в сумматор 38 - вес этого пути, При поступлении второго импульса на вход 61 номер "своей" вершины через открывшуюся сборку элементов И 35.2 и.сборку элементов ИЛИ 36.2 запишется в регистр 37,3, При поступлении второго импульса на вход 60 номер второй вершины кратчайшего пути первого ранга из регистра 37,2 через открывшуюся сборку элементов И 39.2 и сборку элементов ИЛИ 40 поступит на первые входы всех схем совпадения 44.1.44.(В), Далее как и в первом цикле возможно либо формирование пути второго ранга, либо нет, Если связи между второй вершиной кратчайшего пути первого ранга и "своей" вершиной нет(путь второго ранга отсутствует), то со второго входа в сумматор 38 ничего не прибавится, триггер 48 останется в исходном состоянии, схема 53 сравнения не сработает и в регистрах 50,1,50.(В+1) останется информация, записанная в них при первом цикле (т,е. либопуть первого ранга, либо максимально боль-шое число), эта информация поступит на информационные входы сборок элементов И 56 и 57.157,В, а на выходы 10,1 и 11.1 она будет выдаваться как и в первом цикле, Если путь второго ранга существует, то вес ребра, соединяющего вторую вершину кратчайшего пути первого ранга со "своей" вершиной, из регистра 43. через открытую сборку элементов И 45 Л и сборку элементов ИЛИ 46 прибавится в сумматоре 38 к весу кратчайшего пути первого ранга и поступит на вход элемента ИЛИ 47. Триггер 48 перевернется в единичное состояние и высокий потенциал с его выхода откроет сборки элементов И 51 и 52.В схеме 53 сравнения будут сравниваться: вес пути второго ранга (первый вход) и число, записанное в регистре 50.(В+1) при первом цикле (это либо вес пути первого ранга к "своей" вершине, либо максимально большое число). Если вес пути второго ранга больше или равен весу пути первого ранга,то схема 53 не сработает и в регистрах 50,150.(В+1) информация не изменится. Если вес пути второго ранга меньше веса пути первого ранга (естественно меньше максимально большого числа), то схема 53 сработает и высокий потенциал с ее.выхода откроет сборки элементов И 49,149(В+1) -в регистры 50,1,50.(В+1) запишется путь второго ранга (в регистр 50,1 - корневая вершина, в регистр 50.2 - вторая вершина, в регистр 50.3 - третья "своя" вершина, в регистр 50,(В+1) - вес пути) и информация о нем поступит на входы сборок элементов И 56 и 57,157.В, а на выходы 10,1 и 11.1 она будет выдаваться как и в первом цикле. Из процессора, в котором сформировался кратчайший путь первого ранга, с выхода 10 веса пути в блок 5 сравнения передается максимально большое число (триггер 25 в нулевом состоянии, элемент И 27 закрыт, элемент И 28 открыт, а значит при поступлении импульса со входа 58 откроется сборка элементов И 55 и пропустит максимально большое число из регистра 54 на выход 10), это необходимо для исключения ошибочного срабатывания и зацикливания блока 5 сравнения (отсутствие веса пути с выхода закрытой сборки элементов И 56 будет восприниматься блоком 5 сравнения как наличие минимального числа).Таким образом, в процессорах, где ранее был записан путь первого ранга, а при втором цикле сформирован путь второго ранга, из этих двух путей выявится кратчайший, После второго цикла работы устройст 1837312а в некоторых процессорах останутся пути ервого ранга, в других - сформируются пувторого ранга (кроме того, могут быть роцессоры, где формирования путей еще е произойдет, это зависит от структуры г афа), среди них опять выберется кратчайий, который передастся на все процессоы, кроме того, где этот путь выявлен, При оследующих циклах процессоры работают аналогично описанному выше, 5 сравнения (фиг, 5) содержитсхем сравнения 62, каждая из которых предназначена для сравнения пары чисел, и элементы И 63,1,63.В, Схемы с авнения 62 сгруппированы в линейки. В схемах сравнения первой линейки 6.1.162.1(В) происходит сравнение первого числа (веса пути или максимально б лысого числа, поступающих на вход 10.1) с остальными числами, поступающими на в оды 10,210,В. В схемах сравнения втор й линейки 62.2.1.62,2(В) происходит с авнение второго числа со всеми остальн ми числами, кроме первого, и т,д, Вход 1,1 подключен к первым входам схем сравн ния 62,1.162.1 (В) первой линейки. В од 10,2 подключен к первым входам схем с авнения 62,2.162,2.(В) второй линейки и второму входу схемы сравнения 62.1,1. В од 10.3 подключен к первым входам схем с авнения 62.3.162.3(В-З) третьей линейк и второму входу схем сравнения 62.1.2. и 6,2.1 и т,д. Первые выходы схем сравнения 6,1.162.1.(В) первой линейки подключен к входам элемента И 63.1. Первые выходсхем сравнения 62,2.162,2,(В) второй л нейки и второй выход схемы сравнения 6 .1.1 подключены к входам элемента И 6 .2, Первые выходы схем сравнения. 6 .3.162.3.(В-З) третьей линейки и вторые в ходы схем сравнения 62,1.2 и 62.2,1 подк ючены к входам элемента И 63.3 и т.д, В ходы элементов И 63,163,В образуют в ход 13 блока 5 сравнения.Блок 5 сравнения работает следующим о разом. Числа, поступающие на входы 1,1,10.В, представляют собой либо веса и ей, либо максимально большие числа. В к дом цикле работы в схемах сравнения 62 и оисходит одновременное сравнение всех и ступивших чисел. При этом в каждой схем сравнения высокий потенциал появляетс на первом (левом) выходе, если число, п ступившее на ее первый (левый) вход, и ныне или равно числу, поступившему на вт рой (правый) вход, если число, поступивш е на первый вход, больше числа, поступ вшего на второй вход, то высокий и тенциал появляется на втором (правом) выходе схемы сравнения, Таким образом, врезультате сравнения на одном из выходовкаждой схемы сравнения 62 появляется высокий потенциал, Следовательно, на входы5 элементов И 63.16 З,В будут поступатькомбинации высоких и низких потенциалов.При этом комбинация, состоящая из однихвысоких потенциалов, соответствует минимальному числу. Эта комбинация вызывает10 срабатывание соответствующего элементаИ 63 и на его выходе появится импульс,который поступит на выход 13 блока 5 сравнения,Формула изобретения15 1. Устройство для решения задач на графах, содержащее блок управления и генератор тактовых импульсов, причем входзапуска устройства подключен к входу запуска-останова генератора тактовых импуль 20 сов, отличающееся тем,что,сцельюповышения быстродействия, оно содержиткоммутатор, блок сравнения и В процессоров, где В - число вершин графа, причемвыход генератора тактовых импульсов под 25 ключен к входу синхронизации блока управления, выходы группы которого подключенысоответственно к входам кода операциипроцессоров с первого по В-й, выходы весапути на графе а-го процессора (где а=1 Р30 подключены соответственно к информационным входам а-й группы блока сравнения,выходы с первого по В-й которого подкючены соответственно ко входам остановапроцессоров с первого по В-й, выходы но 35 меров вершин пути на графе а-го процессора подключены соответственно кинформационным входам а-й группы коммутатора, выходы которого подключены к первым информационным входам процессоров40 с первого по В-й, выход блока управленияподключен к управляющему входу коммутатора; вход номера корневой вершины графаустройства подключен к входу режима блока управления, вход значения числа вершин45 графа устройства подключен к вторым информационным входам процессоров с первого по В-й,2, Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок управления содержит узел50 сравнения, счетчик, триггер и три распределителя импульсов, причем вход режима ивход синхронизации блока подключены соответственно к первому информационномувходу узла сравнения и к входу синхрониэа 55 ции первого распределителя импульсов,, первый выход которого подключен к входусинхронизации второго распределителя импульсов и к счетному входу счетчика, выходпереноса которого подключен к второму информационному входу узла сравнения, вы 1837312 16ход которого подключен к входу признака запуска-останова первого распределителя импульсов, второй и третий выходы которого подключены соответственно к входу синхронизации третьего распределителя импульсов и к входу установки в "1" триггера, четвертый выход первого распределителя импульсов подключен к входу установки в "О" триггера и к выходу блока, выход триггера, выходы второго и третьего распределителей импульсов и пятый выход 5 первого распределителя импульсов подключены соответственно к выходам группы блока.