Устройство для определения минимальных путей в графах Советский патент 1982 года по МПК G06F15/173 

(Б ) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНЫХ ПУТЕЙ В ГРАФАХ

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров се тевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определения минимальных путей в графах. Известно устройство для определения минимальных путей в графах, содержаще блок управления, генератор импульсов, по числу строк и столбцов матричной модели, цепочки из последовательного соединенных счетчика, триггера и дифференцирующей цепочки, по числу столбцов матричной модели, элементы ИЛИ, первый и второй триггеры,- первый, второй, третий и четвертый элементы И, элемент НЕ, два регистрирующих счетчика и схему сравнения 1 Недостатком известного уетройства. является его низкое быстродействие и чрезмерная сложность при моделирова НИИ графов, вершинам которого соответствуют веса работ, а дугам информационные связи между работ;ами. Наиболее близким техническим решением к предлагаемому является устройство для определения минимальных путей в графах, содержащее генератор импульсов, первый элемент И, элемент И-НЕ, по числу строк и столбцов мажричной модели формирователи дуг, по числу строк матричной модели,г ервые элементы ИШ, по числу столбцовматричной модели, управляющие триггеры, первые и вторые группыэлементов И, элементы HE,i счетчики весов вершины, регистрирующие счетчики, входы каждого из которых подсоединены к выходу второго Jэлемента И,, первый вход которого подсоединён-к выходу первого элемента И, вТорой ход - к выходу элемента НЕ, входы каждого первого элемента ИЛИ подсоеудинен л к первым выходам формирователей дуг одноименной строки матричной модели, а выход - к входу управляющего триггера одноименного столбца матричной модели, первый вход каждого элемента И первой группы подсоединенк выходу первого-элемента И, второй вход - к выходу управляющего триггера, а выход - к входу счетчика веса вершины, выход которого подсоединен к первым входам формирователе дуг одноименного столбца матричной модели, входу элемента НЕ и одноимен ному входу элемента И-НЕ, выход кото рого подсоединен к первому входу первого элемента И,второй вход которого подсоединен к выходу генератора импульсов 2. Недостаток известного усТройства невозможность определения вершин, об разующих минимальный путь в графе и недостаточное быстродействие. Необхо димость в определении вершин, образу щих минимальный путь в графе, возникает, например, при решении задач планирования, выполнения некоторого множества работ, представленных сетевым Графиком, вершинам которого с .ответствуют веса работ, а дугам связи между ними. В этом случае возникает необходимость определения вершин графа, образующих мини,мальный путь, а также величин минимальных пу тей для всех вершин графа. Цель изобретения - повышение быст родействия . Поставленная цель достигается тем, что в устройство для определени минимальных путей в графах, содержащее формирователи дуг по числу строк и столбцов матричной модели графа, каждый из которых содержит первый триггер, выход которого соединен со входом дифференцирующей цепочки, пер вую группу элементов ИЛИ по числу строк матричной модели графа, входы которых подключены к выходам дифференцирующих цепочек одноименных стро матричной модели графа, группу триггеров по числу столбцов матричной модели графа, первую и вторую группу элементов И по числу столбцов матрич ной модели графа, счетчики по числу столбцов матричной модели графа, груп пу элементов НЕ по числу столбцов матричной модели графа, группу регистрирующих счетчиков по числу столбцов матричной модели графа, первый элемент И, элемент И-НЕ и генератор тактовых импульсов, причем ВЫХОДЫ дифференцирующих цепочек формирователей дуг одноименной строки подключены ко входам элемента ИЛИ первой группы одноименной строки, выход каждого элемента ИЛИ группы соединен со входом триггера группы одноименного столбца, выход которого подключен к первому входу элемента И лервой группы одноименного столбца, выход которого соединен со входом счетчика группы одноименного столбца,выход генератора тактовых импульсов соединен с первым входом первого элемента И, выход которого подключен к вторым входам элементов И первой группы и первым входам элементов И второй группы, выход счетчика группы одноименного столбца соединен со входом элемента .НЕ группы одноименного столбца, со входами первых триггеров формирователей дуг одноименного столбца и соответствующим входом элемента И-НЕ, выход которого подключен ко второму ВХОДУ первого элемента И, выход элемента НЕ группы одноименного столбца соединен со вторым входом элемента И второй группы одноименного столбца выход которого подключен ко входу регистрирующего счетчика группы одноименного столбца, дополнительно введены элемент НЕ, второй элемент И, счетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа, вторая группа элементов ИЛИ по числу столбцов матричной модели графа, блок выбора кодов максимального чис ла, а также в каждый формирователь дуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом.формирователе дуг выход дифференцирующей цепочки подключен ко входу второго триггера, выход которого соединен с первым входом элемента И, выходы элементов И формирователей дуг одноименного столбца соединены соответственно со входами элемента ИЛИ второй группы одноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца,выходы элементов И третьей группы подключены к соответствующим входам блока выбора кодов максимального числа, выходы которого соединены со входами ; регистрирующих триггеров группы, выход регистрирующего триггера группы одноименного столбца подключен к первому входу элемента И четвертой группы одноименного столбца, выход ко торого соединен со вторыми входами элементов И формирователей дуг одноименной строки, выход генератора тактовых импульсов подключен к первому входу второго элемента И, выход которого через счетчик соединен со входом дешифратора, выходы KOTQporo соединены соответственно со вторыми входами элемента И четвертой группы. выход элемента И-НЕ соединен со входок элемента НЕ, выход которого подключен ко второму входу второго элемента И. На фиг. 1 показана структурная схема устройства для определения минимальных путей в графах; на фиг.2 структурная схема блока выбора кодов максимального числа. Устройство содержит матричную модель 1j которая представляет собой матрицу формирователей 2 дуг в составе первого триггера 3, дифференцирующей цепочки Ц, второго триг гера 5 и элемента И Ь, по числу стро матричной модели графа первую группу элементов ИЛИ 7 по числустрок матрич ной модели графа, вторую группу элементов ИЛИ 8 по числу столбцов матричной модели графа, группу триггеро 9 по числу I столбцов матричной модели графа, первую группу элементов И 10 по числу столбцов матричной модели графа, группу счетчиков 11 по числу столбцов матричной модели графа, гру пу элементов НЕ 12 по числу столбцов матричной модели графа, вторую группу элементов И 13 по числу столб цов матричной модели графа, группу регистрирующих счетчиков Tt по числу столбцов матричной модели графа, третью группу элементов И 15 по числу столбцов матричной модели графа, группу регистрирующих триггеров 1б п числу столбцов матричной модели графа, четвертую группу элементов И 17 по числу столбцов матричной модели графа, блок 18 выбора кодов максимального числа, элемент И-НЕ 19, генер тор 20 тактовых импульсов, первый элемент И 21, элемент НЕ 22, второй элемент И 23, счетчик 2t, дешифратор 25, пусковой вход 26 и выход 27. Блок 18 (фиг.2 содержит поразрядные узлы 28,у, переноса, где m - максимальное число разрядов в счетчиках И, группы элементов И и ИЛИ , состоящие из элементов ИЛИ 30 и элементов И 31, элементы ИЛИ-НЕ 32, входные шины 33и ,.,, 32у1№,, выходные шины . Устройство работает следующим образом. Первоначально в модель 1 заносится информация о топологии моделируемого графа (сетиК При этом триггеры 3.; , (i,j 1,п), где п - число . вершин в моделируемом графе, соответствующих формирователей 2 устанаввпивается в единичное состояние, если есть информационная связь из i-ой вершины в j-ую вершину. Соответствующий формирователь 2/- определяется пересечением строки с номером (-ая вершина) и столбца с номером j(-aa вершина). В счетчики 10 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков, а счетчики Ш и 2Ц находятся в сброшенном состоянии. Внулевое состояние устанавливаются все триггеры 5, а также триггеры 9, кроме триггера 9j, соответствующего последней вершине графа, и триггеры 16, кроме триггера 1 , соответствующего первой вершине графа, эти триггеры устанавливаются в единичное состояние. После занесения исходной информации все триггеры 3 в строке, соответствующей конечной вершине матричной модели, находятся в нулевом состоянии. Такое занесение исходной информации о графе позволяет использовать для расчета минимального пути процедуру динамического программирования. I С появлением пускового сигнала на входе 26 элемента И 21 импульсы с выхода генератора 20 через элемент И 21 начинают поступать на входы элементов И 10 и 13 групп. Однако первоначально счетные ммпульсы проходят через элементы И 13 на все регистрирующие счетчики 1 и только через те элементы И 10, на первом входе крторых имеется высокий потенциал с единичного выхода триггера 9. В наг чальный момент такой потенциал поступает только на элемент И 10, соответ ствующий конечной вершине. Отсчитав число импульсов, пропорциональное весу моделируемой модели графа, соответствующий счетчик 11переполняется, а сигнал переполне ния с выхода счетчика 11 устанавлива ет в нулевое состояние все триггеры 3 в одноименном столбце матрицы. Одновременно высокий потенциал с выхода переполненного счетчика 11 подает ся на одноименный вход элемента И-НЕ 19 и элемент НЕ 12. Появление низкого потенциала на выходе элемента НЕ 12(на первом входе элемента И 13) вызывает прекращение подачи счетных импульсов через элементы И 13 на вход регистрирующего счетчика . Переброс триггеров 3 в одноименном столбце в нулевое состояние вызывает появление импульса через дифференцирующие цепочки k на входе триг геров 5, в результате чего они запоминают предыдущее состояние тригге ров 3 одноименного формирователя 2 дуги, а также появление импульса через элементы ИЛИ 7 на входе триггера 9 очередного столбца. Этот импульс переводит триггер 9 в единичное состояние, вследствие чего на первом входе элемента И 10 о/: оименного столбца появляется высокий потенциал. Появление разрешающего потенциала на первом входе элемента И 10 обеспечивает возможность прохожде ния счетных импульсов через элемент И 10 на вход счетчика 11 (веса вершины) очередного столбца матрицы. При этом формируется разрешение поступления импульсов на входы счетчиков 11, из соответствующих вершин которых исходят дуги, приводящие в сформированную, ранее вершину. Подсчет импульсов продолжается до тех пор,, пока на выходах всех сче чиков 1.1 не будут присутствовать высокие потенциалы, появляющиеся из-за переполнения этих счетчиков. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких потенциалов на выходах счетчиков 11 обеспечивает через элемент И-НЕ 19 прекращение пода чи счетных импульсов с выхода генера тора 20 через элемент И 21 на входы элементов И 10 и 13. Суммарное число импульсов, поступившее с выхода генератора 20 через элемент И 2lJ, на входы счетчиков 1, соответствует кодам минимальным fкритическим; величинам путей графа из данной (в том числе и начальной вершины до конечной вершины моделируемого графа сети. Наличие низкого потенциала на выходе элемента И-НЕ 19 через элемент НЕ 22 обеспечивает подачу счетных импульсов с выхода генератора 20 на счетчик 2, с выхода которого информация поступает на вход дешифратора 25. На выходе дешифратора 25 возбуждаются поочередно все шины, начиная с первой и кончая п-ой. При возбуждении первой выходной шины на выходе дешифратора 25 высокий потенциал поступает на первый вход элемента И 17 , в результате чего высокий потенциал поступает на первые входы элементов И 6 первой строки матричной модели сети. Высокий потенциал появляется только на тех выходах элементов И 6, соответствующие триггеры 5 которых находятся в еди-; ничном состоянии, поэтому только в этих столбцах на элементах ИЛИ 8 будут высокие потенциалы, которые поступают на первые входы соответствующих элементов И группы 15, в результате чего на входы блока 18 поступают коды с выходов соответствующих счетчиков k. Блок 18 обеспечивает выбор из поступивших на ее входы кодов максимального числа ( входы элементов И 15 группы подсоеДинены к обратным выходам триггеров It) и переброс счетчиков 14J и переброс соответствующего триггера 16 (или триггеров, если таких кодов несколько) в единичное состояние. Далее к содержимому счетчика 2k добавляется очередной импульс, на выходе дешифратора 25 возбуждается очередная шина, и процесс идентификации вершин, образующих минимальный путь, продолжается до тех пор, пока на выходе 27 триггера 1бц, соответствующего последней вершине моделируемого графа, не появится высокий потенциал. Блок 18 работает следующим образом. На входные шины 33 блока 18 поступают п чисел, каждое из которых представлено m разрядами, с обратных выходов триггеров счетчиков И через элементы И 15. В первый момент анализируются старшие разряды. Если хотя бы один из старших разрядов чисел равен 1, то на выходе элемент ИЛИ-НЕ 32v| (в старшем разряде) фбрм руется О, который вырабатывает сигнал запрета для каждого из чисел. При этом, если старший разряд i-ro числа равен О, то все числа не прох дят через элементы И 31 i-ой группы первого узла 28 переноса. Если старший разряд i-ro числа равен 1 то i-oe число проходит через элемен ты И 31 i-ой группы первого узла 28 переноса. Если старшие разряды всех чисел равны О, то на выходе элемента ИЛ НЕ 32 формируется 1, которая дает разрешение на прохождение всех п чисел через элементы И 31 узла 28 Вторым элементом ИЛИ-НЕ 322 совмест но с элементами ИЛИ 30 узла 283. ана лизлруются вторые по старшинству разряды п чисел таким же образом, как и старших разрядов, и т.д. Таким образом, позиционный код номера экстремального числа получается путем совпадения всех m сигнал запрета, сформированных в каждом i-OM узле 28 переноса. Работа устройства при определении минимального пути в графе поясняется следующим примером: пусть задан граф, описываемый матрицей смежности А и вектором Т- весов дуг, причем

Т 11; 2; 3; ; 3; 2; 5; Ц 2,

0,если нет дуги из где элементы i-ой вершины в j-yioj

а..

1,если есть дуга из j i-йй вершины в j-ую; вес i-ой вершины

i

моделируемого графа.

После занесения исходной инфоржации на первом входе триггера 9 будет высокий потенциал, поэтому после подачи пускового сигнала ( вход 26 устройства счётные импульсы с выхода генератора 20 через элемент И 21 будут поступать на входы элеменlOg на

Юр и

через элементы И 10,

4 с б Д Процесс подсчета импульсов заканчивается с приходом одиннадцатого импульса, после чего все счетчики 11 будут переполнены, и с выхода элемента И-НЕ 19 будет поступать низкий потенциал, поэтому прекращается подача счетных импульсов с выхода генератора 20 через элемент И 21..Показания счетчиков И соответствуют мижмальным величинам путей для 1каждой вершины графы до его конечной вершины, при этом каждому номеру вершины сопоставлен свой счетчик. В дан- . ном примере эти показания (начиная с первого следующие: 10; 9; llj-10; 9; 6; 2. трв и 10 и и 13, а далее на входы всех регистрирующих счетчиков Т, . так как отсутствие сигнала переполнения на счетчиках весов вершин 11 обеспечивает наличие высокого потенциала с выходов элементов НЕ 12 (первых входов элементов И 13) и прохождение счетных импульсов на счетчкки }Ц. Кроме того, счетные имг1ульсы проходят через элемент И 11, вход счетчика 11. Через Ц 2, т.е.. с приходом второго импульса, который заполняет до полной емкости счетчик , на первом входе элемента И 13q появляется низкий потенциал, прекращается подача счетных импул сов на вход счетчика 1 4 . Одновременно сигнал переполнения счетчика переводит триггеры 3,9 Зр; в нулевое состояние, в результате чего с их выходов поступают импульсы напряжения через дифференцирующие цепочки на триггеры 57,9 и также через элементы ИЛИ JY и 7g на входы триггеров 9 и 9g. Переброс триггеров 9 и 9в обеспечивает подачу счетных импульсов через элементы И 10,. и lOg на счетчики весов вершины 1Ц и Tig. С приходом шестого импульса переполняется счетчик lU, после чего прекращается подача счетных импульсов на счетчик k и перебрасываются в нулевое состояние триггеры Зяд, Зо и 3gg. Импульсы напряжения с выходов эУих триггеров через дифференцирующие цепочки k поступают на соответствующие триггеры 5 и элементы ИЛИ 7л , 7, 7 перебрасывают триггеры 84. 95- и 9 в единичное состояние, тем самым обеспечивается поступление счетных импульсов Наличие низкого потенциала на вы ходе элемента И-НЕ 19 обеспечивает подачу счетных импульсов с выхода генератора 20 на вход счетчика 24. С приходом первого импульса возбужд ется первая выходная шина дешифрато 25, и высокий потенциал поступает на первый вход элемента И 17f и далее на первые входы элементов И 6 первой строки матричной модели. Высо кий потенциал появляется только на выходах элементов , и 6 , поэтому на входы блока 18 поступают толь ко коды со счетчиков 14 и 14 через элементы И ISg. и 4 Минимальный из этих кодов - 9i поэтому в .единичное состояние будет переброше триггер 1631, и т.д. В результате минимальный путь составят вершины: 1; 2; 7; 9. Таким образом предлагаемое устройство за счет введения дополнител ных элементов с новыми связями обес печивает получение-нового положител ного эффекта, который заключается в том, что значительно расширяются фу циональные возможности; кроме велич ны минимального пути в графе, опред ляется также и конфигурация критиче кого минимального пути при высоком быстродействии по сравнению § други ми аналогичными устройствами. Формула изобретения Устройство для определения минимальных путей в графах, содержащее формирователи дуг по числу строк и столбцов матричной модели графа, каждый из которых содержит первый . триггер, выход которого соединен с входом дифференцирующей цепочки, пе вую группу элементов ИЛИ по числу строк матричной модели графа, входы которых подключены к выходам дифференцирующих цепочек одноименных стр матричной модели графа, группу триг геров по числу столбцов матричной модели графа, первую и вторую группы элементов И по числу столбцов матричной модели графа, счетчики по числу столбцов матричной модели гра фа, группу элементов НЕ по числу столбцов матричной модели графа, группу регистрирующих счетчиков по числу столбцов матричной модели гра фа, первый элемент И, элемент И-НЕ и генератор тактовых импульсов. причем выходы дифференцирующих цепочек формирователей дуг одноименной строки подключены к входам элемента ИЛИ первой группы одноименной строки, выход каждого элемента ИЛИ группы соединен с входом триггера группы одноименного столбца, выход которого подключен к первому входу элемента И первой группы одноименного столбца, выход каторого соединен с входом счетчика группы одноименного столбца, выход генератора тактовых импульсов соединен с первым входом первого элемента И, выход которого подключен к вторым входам элементов И первой группы и первым входам элементов И второй группы, выход счетчика группы одноименного столбца соединен с входом элемента НЕ группы одноименного столбца, с входом первых триггеров формирователей дуг одноименного столбца и соответствующим входом элемента И-НЕ, выход которого подключен к второму входу первого элемента И, выход элемента НЕ группы одноименного столбца соединен с вторым входом элемента И второй группы одноименного столбца, выход которого подключен к входу регистрирующего счетчика группы одноименного столбца, отличающееся тем, что, с целью повышения быстродействия, в него дополнительно введены элемент НЕ, второй элемент И, счетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа, вторая группа элементов ИЛИ по числу столбцов матричной модели графа, блок выбора кодов максимального числа, а также в каждый фсцэмирователь дуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом формирователе дуг выход дифференцирующей цепочки подключен к , входу второго триггера,выход которого соединен с первым входом элемента И, выходы элементов И формирователей дуг одноименного столбца соединены соответственно с входами элемента ИЛИ второй группы одноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика гру пы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кодов максимального числа, выходы которого соединены с входами регистрирующих триггеров группы, выход регистрирующего триггера группы одноименного столбца подключен к первому входу элемента И четвертой группы одноименного столбца, выход которого соединен с вторыми входами элементов И формирователей дуг одноименной строки, выход генератора тактовых импульсов подключен к первому входу второго элемента И, ВЫХОД которого через счетчик соединен с входом дешифратора, выходы которого соединены соответственно с вторыми входами элемента И четвертой группы, выход элемента И-НЕ соединен с входом f элемента НЕ, выход которого подключен к второму входу второго элемента И. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР по заявке N° 2830339/18-24, кл. G 06 G 7/122, 1979. 2.Авторское свидетельство СССР по заявке № 288061 4/18-2, . кл, G Об G 7/122, 1980 (прототип).

Фиг. 2