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

ОП ИСАНИ Е ИЗОБРЕТЕН ИЯ Союз СоветскихСоциалистическихРеспублик(23) Приори Опубликован Дата опубли Пв деЛаи кзебретенкй н открыткй) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ИИНИИАЛЬНЫ ПУТЕЙ В ГРАФАХИзобретение относится:1 к вычислительной технике и может быть использовано при исследовании параметров се тевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определенияминимальных путей в графах.Известно устройство для определения минимальных путей в графах, содержащее блок управления, генератор импульсов 10 по числу строк и столбцов матричной модели, цепочки из последовательное соединенных счетчика, триггера и дифференцирующей цепочки, по числу столбцов матричной модели, элементы ИЛИ, первый и второй триггеры, .первый, второй, третий и четвертый эле" менты И, элемент НЕ, два регистцирующих счетчика и схему сравнения 1.м20Недостатком известного устроиства, является его низкое быстродействие и чрезмерная сложность при моделирова нии графов, вершинам которого соуков и А,Л. Гайдуков ответствуют "веса" работ, а дугам- информационные связи между работами.Наиболее близким техническим решением к предлагаемому является устройство для определения минимальных пу" тей в графах, содержащее генератор импульсов, первый элемент И, элемент И-НЕ, по числу строк и столбцов мат.- ричной модели формирователи дуг, по . числу строк матричной модели, мрвые элементы ИЛИ, по числу столбцовматричной модели, управляющие триггеры, первые и вторые группы элементов И, элементы НЕ, счетчики "весов" вервины, регистрирующие счетчики, входы каждого из которых подсоединены к выходу второго элемента Ипервый вход которого подсоединен к выходу йевого элемента И, второй вход - к выходу элемента НЕ, входы каждого первого элемента ИЛИ подсоединены к первым выходам формирователей дуг одноименной строки матричной модели,91203 а выход - к Входу управляющего триггера одноименного столбца матричноймодели, первый вход каждого элемента И первой группы подсоединенквыходу первого-элемента И, второй 5вход - к выходу управляющего триггера, а выход - к входу счетчика "веса" вершины, выход которого подсоединен к первым входам формирователейдуг одноименного столбца матричной фмодели, входу элемента НЕ и одноименному входу элемента И-НЕ, выход которого подсоединен к первому входупервого элемента И,второй вход которого подсоединен к выходу генератора импульсов 21. Недостаток известного устройства - невозможность определения вершин, образующих минимальный путь в графе и недостаточное быстродействие. Необходимость в определении вершин, образующих минимальный путь в графе, возникает, например, при решении задачпланирования, выполнения некоторого множества работ, представленных сетевым графиком, вершинам которого со. ,ответствуют "веса" работ, а дугам -связи между ними. В этом случае возникает необходимость определения вершин графа, образующих минимальный путь, а также величин минимальных путей для всех вершин графа.Цель изобретения - повышение быстродействия.Поставленная цель достигается тем, что в устройство для определения минимальных путей в графах, содержащее формирователи дуг по числу строк и столбцов матричной модели графа,Щ каждый из которых содержит первыи триггер, выход которого соединен со входом дифференцирующей цепочки, первую группу элементов ИЛИ по числу строк матричной модели графа, входы которых подключены к выходам диффе"45 ренцирующих цепочек одноименных строк матричной модели графа, группу триггеров по числу столбцов матричной модели графа, первую и вторую группу элементов И по числу столбцов матрич ной модели графа, счетчики по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, группу регистрирующих счетчиков по числу 55 столбцов матричной модели графа, первый элемент И, элемент И-НЕ и генератор тактовых импульсов, причем 0 фвыходы дифференцирующих цепочек формирователей дуг одноименной строкиподключены ко входам элемента ИЛИпервой группы одноименной строки, выход каждого элемента ИЛИ группы соединен со входом триггера группыодноименного столбца, выход которогоподключен к первому входу элементаИ первой группы одноименного столбца, выход которого соединен со входом счетчика группы одноименногостолбца, выход генератора тактовыхимпульсов соединен с первым входомпервого элемента И, выход которогоподключен к вторым входам элементов И первой группы и первым входам элементов И второй группы, выход счетчика группы одноименногостолбца соединен со входом элемента,НЕ группы одноименного столбца, совходами первых триггеров формировате.лей дуг одноименного столбца и соответствующим входом элемента И-НЕ,выход которого подключен ко второмувходу первого элемента И, выход эле.мента НЕ группы одноименного столбцасоединен со вторым входом элемента Ивторой группы одноименного столбца выход которого подключен ко входурегистрирующего счетчика группыодноименного столбца, дополнительновведены элемент НЕ, второй элемент Исчетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группарегистрирующих триггеров по числустолбцов матричной модели графа, вторая группа элементов ИЛИ по числустолбцов матричной модели графа,блок выбора кодов максимального числа, а также в каждый формировательдуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом.формирователе дуг выход дифференцирующей цепочкиподключен ко входу второго триггера,выход которого соединен с первымвходом элемента И, выходы элементовИ формирователей дуг одноименногостолбца соединены соответственно совходами элемента ИЛИ второй группыодноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименногостолбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца,второй вход которого соединен с выходом регистрирующего счетчика груп0 6элемент И 21, элемент НЕ 22, второй элемент И 23, счетчик 24, дешифратор 25, пусковой вход 26 и выход 27,Блок 18 (Фиг.2) содержит поразрядные узлы 28 - 28 т переноса, где в - максимальное число разрядов в счетчиках 14, группы элементов И и ИЛИ 2,- 29 , состоящие из элементов ИЛИ 30 и элементов.И 31, элементы ИЛИ-НЕ 32, входные шины 33321,1, выходные шины 34 34.Устройство работает следующим образом.Первоначально в модель 1 заносится информация о топологии моделируе" мого графа (сети) . При этом триггеры 3, , (,3 = 11 п), где и - число, вершин в моделируемом графе, соответствующих формирователей 2 устанав(ливается в единичное состояние, если есть информационная связь из 1-ой вершины в -ую вершину, Соответствующий формирователь 2" определяется пересечением строки с номером (1-ая вершина) и столбца с номером 1(-ая вершина). В счетчики 10 соответствующих вершин графа заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков, а счетчики 14 и 24 находятся в сброшенномсостоянии. Внулевое состояние устанавливаются все триггеры 5, а также триггеры 9, кроме триггера 9 , соответствующего последней1вершине графа, и триггеры 16, кроме триггера 1 , соответствующего первой вершине графа, эти триггеры устанавливаются в единичное состояние. После занесения исходной информации все триггеры 3 в строке, соответст-вующей конечной вершине матричной модели, находятся в нулевом состоянии. Такое занесение исходной информации о графе позволяет использовать для расчета минимального пути процедуру. динамического программирования.1 С появлением пускового сигнала на входе 26 элемента И 21 импульсы с выхода генератора 20 через элемент И 21 начинают поступать на входы элементов И 10 и 13 групп. Однако пер воначально счетные импульсы проходят через элементы И 13 на все регистрирующие счетчики 14 и только через те элементы И 10, на первом входе которых имеется высокий потенциал с единичного выхода триггера 9. В на чальный момент такой потенциал посту 5 94203пы одноименного столбца, выходы элементов И третьей группы подключенык соответствующим входам блока вы бора кодов максимального числа, выходы которого соединены со входами; 5регистрирующих триггеров группы, выход регистрирующего триггера группыодноименного столбца подключен к первому входу элемента И четвертойгруппы одноименного столбца, выход ко.10торого соединен со вторыми входамиэлементов И формирователей дуг одноименной строки, выход генератора тактовых импульсов подключен к первомувходу второго элемента И, выход которого через счетчик соединен со входом дешифратора, выходы которого соединены соответственно со вторымивходами элемента И четвертой группы,выход элемента И-НЕ соединен со входом 20элемента НЕ, выход которого подключен ко второму входу второго элемента И.На фиг, 1 показана структурнаясхема устройства для определения 25минимальных путей в графах; на фиг.2 структурная схема блока выбора кодов максимального числа,Устройство содержит матричнуюмодель 1 которая представляет со обой матрицу формирователей 2 дуг всоставе первого триггера 3, дифференцирующей цепочки 4, второго триггера 5 и элемента И 6, по числу строкматричной модели графа первую группуэлементов ИЛИ 7 по числустрок матричной модели графа, вторую груйпу элементов ИЛИ 8 по числу столбцов матричной модели графа, группу триггеров9 по числу столбцов матричной моделиграфа, первую группу элементов И 10по числу столбцов матричной моделиграфа, группу счетчиков 11 по числустолбцов матричной модели графа, группу элементов НЕ 12 по числу столбцов матричной модели графа, вторуюгруппу элементов И 13 по числу столбцов матричной модели графа, группурегистрирующих счетчиков 14 по числу столбцов матричной модели графа,третью группу элементов И 15 по числу столбцов матричной модели графа,группу регистрирующих триггеров 16 почислу столбцов матричной модели граФа, четвертую группу элементов И 1755по числу столбцов матричноймоделиграфа, блок 18 выбора кодовмаксимального числа, элемент И-НЕ 19, генератор 20 тактовых импульсов, первый9420пает только на элемент И 10, соответствующий конечной вершине.Отсчитав число импульсов, пропорциональное "весу" моделируемой модели графа, соответствующий счетчик 511 переполняется, а сигнал переполнения с выхода счетчика 11 устанавливает в нулевое состояние все триггеры3 в одноименном столбце матрицы, Одновременно высокий потенциал с выхо- фда переполненного счетчика 11 подается на одноименный вход элемента И-НЕ19 и элемент НЕ 12. Появление низкого потенциала на выходе элемента НЕ12 ( на первом входе элемента И 13)вызывает прекращение подачи счетныхимпульсов через элементы И 13 навход регистрирующего счетчика 14.Переброс триггеров 3 в одноименномстолбце в нулевое состояние вызывает появление импульса через дифференцирующие цепочки 4 на входе триг.герон 5, в результате чего они запоминают предыдущее состояние тригге.ров 3 одноименного Формирователя 2 25дуги, а также появление импульсачерез элементы ИЛИ 7 на входе триггера 9 очередного столбца. Этот импульс переводит триггер 9 в единичное состояние, вследствие чего на зо первом входе элемента И 10 оДЬоименного столбца появляется высокий потенциал. Появление разрешающего потенциала на первом входе элемента И1 О обеспечивает возможность прохожде- зния счетных импульсов через элемент И 10 на вход счетчика 11 ( "веса"вершины) очередного столбца матрицы. При этом формируется разрешение поступления импульсов на входы счетчи- щ) ков 11, из соответствующих вершинкоторых исходят дуги, приводящие в сформированную. ранее вершину.Подсчет импульсов продолжается до тех пор,. пока на выходах всех счет 4 чиков 1,1 не будут присутствовать вы- сокие потенциалы, появляющиеся из-за переполнения этих счетчиков, Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких потенциалов на выходах счетчиков 11 обеспечивает через элемент И-НЕ 19 прекращение подачи счетных импульсов с выхода генера-, тора 20 через элемент И 21 на входыэлементов И 10 и 13. Суммарное число импульсов, поступившее с выхода генератора 20 через элемент И 21 на входы счетчиков 14, соответствует 30 8кодам минимальнымкритическим) величинам путей графа из данной (в том числе и начальной ) вершины до конечной вершины моделируемого графа сети.Наличие низкого потенциала на выходе элемента И-НЕ 19 через элемент НЕ 22 обеспечивает подачу счетных импульсов с выхода генератора 20 на счетчик 24, с выхода которого информация поступает на вход дешифратора 25. На выходе дешифратора 25 возбуждаются поочередно все шины, начиная с первой и кончая и-ой. При возбуждении первой выходной шины на выходе дешифратора 25 высокий потенциал поступает на первый вход элемента И 17 в результате чего высокий потенциал поступает на первые входы элементов И 6 первой строки матричной модели сети. Высокий потенциал появляется только на тех выходах элементов И 6, соответствующие триггеры 5 которых находятся в единичном состоянии, поэтому только в этих столбцах на элементах ИЛИ 8 будут высокие потенциалы, которые поступают на первые входы соответствующих элементов И группы 15, в результате чего на входы блока 18 поступают коды с выходов соответствующих счетчиков 14. Блок 18 обеспечивает выбор из поступивших на ее входы кодов максимального числа ( входы элементов И 15 группы подсоединены к обратным выходам триггеров счетчиков 14) и переброс соответствующего триггера 16 (или триггеров, если таких кодов несколько) в единичное состояние.Далее к содержимому счетчика 24 добавляется очередной импульс, на выходе дешифратора 25 возбуждается очередная шина, и процесс идентификации вершин, образующих минимальный путь, продолжается до тех пор, пока на выходе 27 триггера 16 и, соответствующего последней вершине моделируемого графа, не появится высокий потенциал. аБлок 18 работает следующим образом,На входные шины 33 блока 18 поступают и чисел, каждое из которых представлено щ разрядами, с обратных выходов триггеров счетчиков 14 через элементы И 15, В первый момент анализируются старшие разряды. Если хотя бы один из старших разрядов2030 1 Отов И 1 О и И 13, а далее на входывсех регистрирующих счетчиков 14,так как отсутствие сигнала переполнения на счетчиках "весов" вершин 11 5 обеспечивает наличие высокого потенциала с выходов элементов НЕ 12первых входов элементов И 13) и прохождение счетных импульсов на счетчики 14. Кроме того, счетные импуль сы проходят через элемент И 16 навход счетчика 119. Через й = 2, т.ес приходом второго импульса, который заполняет до полной емкости)счетчик 110, на первом входе элемен та И 13 появляется низкий потенциал,прекращается подача счетных импулЬСовна вход счетчика 14 . Одновременносигнал переполнения счетчика 110 переводит триггеры 3 9 и 39 в нулевое щ состояние, в результате чего с их выходов поступают импульсы напряжениячерез дифференцирующие цепочки 4 натри Ггеры 79 и В 9, а также черезэлементы ИЛИ 7 т и 7 на входы триг геров 9) и 9 В Переброс триггеров 9 ти 9 д обеспечивает подачу счетных 9 94 чисел равен 1, то на выходеэлемента ИЛИ-НЕ 32 ( в старшем разряде) фдрмируется О, который вырабатывает сигнал запрета для каждого из чисел. При этом, если старший разряд -го числа равен О, то все числа не проходят через элементы И 31 1-ой группы первого узла 28 переноса Если старший разряд -го числа равен "1", то 1-ое число проходит через элементы И 31 1-ой группы первого узла 281 переноса.Если старшие разряды всех чисел равны "0", то на выходе. элемента КЛИНЕ 32 формируется "1", которая дает разрешение на прохождение всех и чисел через элементы И 31 узла 28 . Вторым элементом ИЛИ-НЕ 32 совместно с элементами ИЛИ 30 узла 28 анализируются вторые по старшинству разряды и чисел таким же образом, как и старших разрядов, и т.д.Таким образом, позиционный код номера экстремального числа получается путем совпадения всех в сигналов запрета, сформированных в каждом 1-ом узле 28 переноса. импульсов через элементы И 1 О иРабота устройства при определе"нии минимального пути в графе поясняется следующим примером: пусть задан граф, описываемый матрицей смежности А и вектором Т-"весов" дуг, причем 30 011000000 000110100 000011000 000000110 000000010 000000110 000000001 000000001 000000000 35 После занесения исходной информации на первом входе триггера 9 бу 9 дет высокий потенциал, поэтому после подачи пускового сигнала йа вход.26 устройства счетные импульсы с выхода генератора 20 через элемент И 21 будут поступать на входы элемент =1; 2; 3; 4; 3; 2; ; 4; 2,45 где элементы О, если нет дуги из1-ой вершины в 1-ую; а = 1, если есть дуга из 1-дй вершины в -ую; "вес" 1-ой вершины50моделируемого графа,100 на счетчики "весов" вершины 11 т и 11. С приходом шестого импульса переполняется счетчик 11 В, после чего прекращается подача счетных импульсов на счетчик 14 у и перебра;сываются в нулевое состояние триггеРы 3, ЗВ и 3 В 6. Импульсы напряжения выхо ов эт)их т иг е ов ес д р г р чер з дифференцирующие цепочки 4 поступают на соответствующие триггеры 5 и элементы ИЛИ 7, 75., 76, перебрасывают триггеры 9 9 и 96 в единичное состояние, тем самым обеспечивается поступление счетных импульсов через элементы И 104, 105 и 10 на счетчики 114, 11 и 11 и т.д. Процесс подсчета имйульсов заканчивается с приходом одиннадцатого импуль са, после чего все счетчики 11 бу-.дут переполнены, и с выхода элемен-. та И-НЕ 19 будет поступать низкий потенциал, поэтому прекращается подача счетных импульсов с выхода генератора 20 через элемент И 21. ПОказания счетчиков 14 соответствуют минимальным величинам путей для каждой вершины графы до его конечной вершины, при этом каждому номеру вершины сопоставлен свой счетчик. В дан- . ном примере эти показания (начиная с первого) следующие: 10; 9; 11 1 О; 9; 8,7; 6; 2.11 9 ч 20Наличие низкого потенциала на выходе элемента И-НЕ 19 обеспечивает подачу счетных импульсов с выхода генератора 20 на вход счетчика 21. С приходом первого импульса возбужда-ется первая выходная шина дешифратора 25, и высокий потенциал поступает на первый вход элемента И 17 и далее на первые входы элементов И 6 первой строки матричной модели. Высо 1 О кий потенциал появляется только на выходах элементов 6, и 6, поэтому на входы блока 18 поступают только коды со счетчиков 11 и 11 через элементы И 15 и 154 Минималь ный из этих кодов - 9, поэтому в ,единичное состояние будет переброшен триггер 16, и т.д. В результате минимальный путь составят вершины:71 9.20Таким образом предлагаемое устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в уЗ том, что значительно расширяются функциональные возможности; кроме величины минимального пути в графе, определяется также и конфигурация критического минимального пути при высоком щ быстродействии по сравнению д другими аналогичными устройствами.Формула изобретенияУстройство для определения минимальных путей в графах, содержащееформирователи дуг по числу строк истолбцов матричной модели графа,н, 3 Щкаждый из которых содержит первыитриггер, выход которого соединен свходом дифференцирующей цепочки, пер.вую группу элементов ИЛИ по числустрок матричной модели графа, входыкоторых подключены к выходам диффе"45ренцирующих цепочек одноименных строкматричной модели графа, группу триггеров по числу столбцов матричноймодели графа, первую и вторую группы элементов И по числу столбцовматричной модели графа, счетчики почислу столбцов матричной модели графа, группу элементов НЕ по числустолбцов матричной модели графа,группу регистрирующих счетчиков по Ячислу столбцов матричной модели графа, первый элемент И, элемент И-НЕи генератор тактовых импульсов,30 12при чем выходы дифференцирующи х цепочек формирователей дуг одноименной строки подключены к входам элемента ИЛИ первой группы одноименной строки, выход каждого элемента ИЛИ группы соединен с входом триггера группы одноименного столбца, выход которого подключен к первому входу элемвнта И первой группы одноименного столбца, выход каторого соединен с входом счетчика группы одноименного столбца, выход генератора тактовых импульсов соединен с первым входом первого элемента И, выход которого подключен к вторым входам элементов И первой группы: и первым входам элементов И второй группы, выход счетчика группы одноименного столбца соединен с входом элемента НЕ группы одноименного столбца, с входом первых триггеров формирователей дуг одноименного столбца и соответствующим входом элемента И-НЕ, выход ко. торого подключен к второму входу первого элемента И, выход элемента НЕ группы одноименного столбца соединен с вторым входом элемента И второй группы одноименного столбца, выход которого подключен к входу регистрирующего счетчика группы одноименного столбца, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в него дополнительно введены элемент НЕ, второй элемент И, счетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной моде ли графа, вторая группа элементов ИЛИ по числу столбцов матричной модели графа, блок выбора кодов мак. симального числа, а также в каждый формирователь дуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом формирователе дуг выход дифференцирующей цепочки подключен к входу второго триггера, выход которого соединен с первым входом элемента И, выходы элементов И формирователей дуг одноименного столбца соединены соответственно с входами элемента ИЛИ второй группы одноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столб13 9420 ца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кодов максимального числа, выходы которого соединены с входами регистрирующих триггеров группы, выход регистрирующего триггера группы одноименного столбца подключен к 1 о первому входу элемента И четвертой группы одноименного столбца, выход которого соединен с вторыми входами элементов И формирователей дуг одноименной строки, выход генерато- И ра тактовых импульсов подключен к первому входу второго элемента И,30 14выход которого через счетчик соединен с входом дешифратора, выходы которого соединены соответственно с вторыми входами элемента И четвертой группы, выход элемента И-НЕ соединен с входом 1 элемента НЕ, выход которого подключен к второму входу второго элемента И.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРпо заявке У 2830339/18-24,кл. 6 06 С 7/122, 1979.2. Авторское свидетельство СССРпо заявке М 2880614/18-24,кл, 6 06 6 7/122, 1980 (прототип).942030 Составитель И. Дубининаовальчук Техред Т, Маточка Корре кто Редак Подписн лиал ППП "Патент, г.ужгород, ул. Проектная, 4 Тираж 731осударственного комлам изобретений и оква, Ж, Раушская аз 4842/40 ВНИИПИ Г по де 113035, Мос