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

 

ОП ИСАНИ Е

ИЗО6РЕТЕН ИЯ

К ..АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик (и)942030 (61) Дополнительное к авт. свид-ву (22) Заявлено 10. 11. 80 (2! ) 3002818/18-24 (51)М. Кл.

G 06 F 15120 с присоединением заявки М

Ркударетвевныб квинтет

СССР пв делан кзебретенкк н открыткй (23 ) Приоритет

Опубликовано 07. 07. 82 ° Бкзллетень М25

Дата опубликования описания 07.07.82 (53) УДК681. 333 (088. 8) с

1

1

- ° --. (22) Авторы изобретения

В.А. Титов, В.Л. Гайдуков и А.Л. Гайдуков (71) Заявитель (S4) у Тр0й ТВ0 gj1S 0П Е ЕЛЕНИ НИНИНАЛ Н

ПУТЕЙ В ГРАФАХ

Изобретение относится:1к вычислительной технике и может быть использовано при исследовании параметров се. тевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определения минимальных путей в графах.

Известно устройство для определения минимальных путей в графах, содержащее блок управления, генератор импульсов„10 по числу строк и столбцов матричной модели, цепочки из последовательное соединенных счетчика, триггера и дифференцирующей цепочки, по числу столбцов матричной модели, элементы

ИЛИ, первый и второй триггеры, :первый, второй, третий и четвертый эле" менты И, элемент НЕ, два регистцирующих счетчика и схему сравнения 1). м

Недостатком известного устроиства. является его низкое быстродействие и черезмерная сложность при моделирова нии графов, вершинам которого соответствуют "веса" работ, а дугаминформационные связи между работами

Наиболее близким техническим peIIIeнием к предлагаемому является устройство для определения минимальных пу" тей в графах, содержащее генератор импульсов, первый элемент И, элемент

И-НЕ, по числу строк и столбцов мат.ричной модели формирователи дуг, по . числу строк матричной модели, Ilepase элементы ИЛИ, по числу столбцов матричной модели, управляющие триггеры, первые и вторые группы элементов И,. элементы НЕ, счетчики "весов" вервины, регистрирующие счетчики, входы каждого из которых подсоединены к выходу второго, элемента И „ первый вход которого подсоединен.к выходу йее вого элемента И, второй вход - к выходу элемента НЕ, входы каждого первого элемента ИЛИ подсоединены к tlGpBbIM выходам формирователей дуг одноименной строки матричной модели, 94203 а выход - к Входу управляющего триггера одноименного столбца матричной модели, первый вход каждого элемента И первой группы подсоединен к выходу первого-элемента И, второй 5 вход - к выходу управляющего триггера, а выход - к входу счетчика "веса" вершины, выход которого подсоединен к первым входам формирователей дуг одноименного столбца матричной модели, входу элемента НЕ и одноименному входу элемента И-НЕ, выход которого подсоединен к первому входу первого элемента И,второй вход которого подсоединен к выходу генерато- 15 ра импульсов (21.

Недостаток известного устройства— невозможность определения вершин, образующих минимальный путь в графе и недостаточное быстродействие. Необходимость в определении вершин, образующих минимальный путь в графе, возникает, например, при решении задач планирования, выполнения некоторого множества работ, представленных сетевым графиком, вершинам которого со,ответствуют "веса" работ, а дугам— связи между ними. В этом случае возникает необходимость определения вершин графа, образующих минимальный путь, а также величин минимальных путей для всех вершин графа.

Цель изобретения — повышение быстродействия.

Поставленная цель достигается тем, что в устройство для определения минимальных путей в графах, содержащее формирователи дуг по числу строк и столбцов матричной модели графа, 10 каждый из которых содержит первыи триггер, выход которого соединен со входом дифференцирующей цепочки, первую группу элементов ИЛИ по числу строк матричной модели графа, входы которых подключены к выходам диффе"

45 ренцирующих цепочек одноименных строк матричной модели графа, группу триггеров по числу столбцов матричной модели графа, первую и вторую группу элементов И по числу столбцов матрич- о ной модели графа, счетчики по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, группу регистрирующих счетчиков по числу И столбцов матричной модели графа, первый элемент И, элемент И-НЕ и генератор тактовых импульсов, причем

0 ф выходы дифференцирующих цепочек формирователей дуг одноименной строки подключены ко входам элемента ИЛИ первой группы одноименной строки, вы. ход каждого элемента ИЛИ группы соединен со входом триггера группы одноименного столбца, выход которого подключен к первому входу элемента

И первой группы одноименного столбца, выход которого соединен со входом счетчика группы одноименного столбца, выход генератора тактовых импульсов соединен с первым входом первого элемента И, выход которого подключен к вторым входам элементов И первой группы и первым входам элементов И второй группы, выход счетчика группы одноименного столбца соединен со входом элемента ,НЕ группы одноименного столбца, со входами первых триггеров формирователей дуг одноименного столбца и соответствующим входом элемента И-НЕ, выход которого подключен ко второму входу первого элемента И, выход элемента НЕ группы одноименного столбца соединен со вторым входом элемента И второй группы одноименного столбца выход которого подключен ко входу регистрирующего счетчика группы одноименного столбца, дополнительно введены элемент НЕ, второй элемент И, счетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной модели графа, вторая группа элементов ИЛИ по числу столбцов матричной модели графа, блок выбора кодов максимального чис ла, а также в каждый Формирователь дуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом.формирователе дуг выход дифференцирующей цепочки подключен ко входу второго триггера, выход которого соединен с первым входом элемента И, выходы элементов

И формирователей дуг одноименного столбца соединены соответственно со входами элемента ИЛИ второй группы одноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика груп0 6 элемент И 21, элемент НЕ 22, второй элемент И 23, счетчик 24, дешифратор

25, пусковой вход 26 и выход 27.

Блок 18 (фиг.2) содержит поразрядные узлы 28 - 28 и переноса, где

m - максимальное число разрядов в счетчиках 14, группы элементов И и ИЛИ 29 29, состоящие из элементов ИЛИ 30 и элементов.И 31, элементы ИЛИ-НЕ 32, входные шины 33„, 321,,„, выходные шины 34„,,... 34 .

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

Первоначально в модель 1 заносится информация о топологии моделируе" мого графа (сети) . При этом триггеры 3,, (1,j = 1,п), где n - число, вершин в моделируемом графе, соответствующих формирователей 2 устанав(ливается в единичное состояние, если есть информационная связь из

i-ой вершины a j-ую вершину. Соответствующий формирователь 2„" определяется пересечением строки с номером

i(i-ая вершина) и столбца с номером

j(j-ая вершина}. В счетчики 10 соответствующих вершин графа заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков, а счетчики 14 и 24 находятся в сброшенном»состоянии. В нулевое состояние устанавливаются все триггеры

5, а также триггеры 9, кроме триггера 9, соответствующего последней и у вершине графа, и триггеры 16, кроме триггера 1(, соответствующего первой вершине графа, эти триггеры устанавливаются в единичное состояние.

После занесения исходной информации все триггеры 3 в строке, соответст- вующей конечной вершине матричной модели, находятся в нулевом состоянии. Такое занесение исходной информации о графе позволяет использовать для расчета минимального пути процедуру. динамического программирования.

С появлением пускового сигнала на входе 26 элемента И 21 импульсы с выхода генератора 20 через элемент

И 21 начинают поступать на входы элементов И 10 и 13 групп. Однако пер. воначально счетные импульсы проходят через элементы И 13 на все регистрирующие счетчики 14 и только через те элементы И 10, на первом входе которых имеется высокий потенциал с единичного выхода триггера 9. В на» чальный момент такой потенциал посту5 94203 пы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока вы бора кодов максимального числа, выходы которого соединены со входами; регистрирующих триггеров группы, выход регистрирующего триггера группы одноименного столбца подключен к первому входу элемента И четвертой группы одноименного столбца, выход ко-10 торого соединен со вторыми входами элементов И формирователей дуг одноименной строки, выход генератора тактовых импульсов подключен к первому входу второго элемента И, выход кото- 15 рого через счетчик соединен со входом дешифратора, выходы которого соединены соответственно со вторыми входами элемента И четвертой группы, выход элемента И-НЕ соединен со входом 2О элемента НЕ, выход которого подключен ко второму входу второго элемента И.

На фиг. 1 показана структурная схема устройства для определения 25 минимальных путей в графах; на фиг.2структурная схема блока выбора кодов максимального числа.

Устройство содержит матричную модель 1 которая представляет со- зо бой матрицу формирователей 2 дуг в составе первого триггера 3, рифференцирующей цепочки 4, второго триг гера 5 и элемента И 6, по числу строк матричной модели графа первую группу элементов ИЛИ 7 по числу строк матричной модели графа, вторую груйпу weментов ИЛИ 8 по числу столбцов матричной модели графа, группу триггеров

9 по числу столбцов матричной модели графа, первую группу элементов И 10 по числу столбцов матричной модели графа, группу счетчиков 11 по числу столбцов матричной модели графа, груп. пу элементов HE 12 по числу столбцов матричной модели графа, вторую группу элементов И l3 по числу столбцов матричной модели графа, группу регистрирующих счетчиков 14 по числу столбцов матричной модели графа, третью группу элементов И 15 по числу столбцов матричной модели графа, группу регистрирующих триггеров t6 по числу столбцов матричной модели графа, четвертую группу элементов И 17

55 по числу столбцов матричной модели графа, блок 18 выбора кодов*максимального числа, элемент И-НЕ 19, генера тор 20 тактовых импульсов, первый

7 9420 пает только на элемент И 10, соответствующий конечной вершине.

Отсчитав число импульсов, пропорциональное "весу" моделируемой модели графа, соответствующий счетчик s

11 переполняется, а сигнал переполнения с выхода счетчика 11 устанавливает в нулевое состояние все триггеры

3 в одноименном столбце матрицы, Одновременно высокий потенциал с выхода переполненного счетчика 11 подается на одноименный вход элемента И-НЕ

19 и элемент НЕ 12. Появление низкого потенциала на выходе элемента HE

l2 (на первом входе элемента И 13) вызывает прекращение подачи счетных импульсов через элементы И 13 на вход регистрирующего счетчика 14.

Переброс триггеров 3 в одноименном столбце в нулевое состояние вызыва- 20 ет появление импульса через дифференцирующие цепочки 4 на входе триг. герон 5, в результате чего они запоминают предыдущее состояние тригге ров 3 одноименного формирователя 2 25 дуги, а также появление импульса через элементы ИЛИ 7 на входе триггера 9 очередного столбца. Этот импульс переводит триггер 9 в единичное состояние, вследствие чего на зо первом входе элемента И 10 оДЬоименного столбца появляется высокий потенциал. Появление разрешающего потенциала на первом входе элемента И

10 обеспечивает возможность прохожде- з ния счетных импульсов через элемент

И 10 на вход счетчика 11 ("веса" вершины) очередного столбца матрицы.

При этом формируется разрешение поступления импульсов на входы счетчи- 4g ков 11, из соответствующих вершин которых исходят дуги, приводящие в сформированную. ранее вершину.

Подсчет импульсов продолжается до тех пор,. пока на выходах всех счет 4 чиков 1,1 не будут присутствовать вы- сокие потенциалы, появляющиеся из-за переполнения этих счетчиков. Это свидетельствует о том, что все узлы исследуемого графа сформированы.

Наличие высоких потенциалов на выходах счетчиков 11 обеспечивает через элемент И-НЕ 19 прекращение подачи счетных импульсов с выхода генера-; тора 20 через элемент И 21 на входы элементов И 10 и 13. Суммарное число импульсов, поступившее с выхода генератора 20 через элемент И 21

1 на входы счетчиков 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 поступают и чисел, каждое из которых представлено m разрядами, с обратных выходов триггеров счетчиков 14 через элементы И 15. В первый момент анализируются старшие разряды. Если хотя бы один из старших разрядов

2030

10 тов И 10 и И 13, а далее на входы всех регистрирующих счетчиков 14, так как отсутствие сигнала переполнения на счетчиках "весов" вершин 11

s обеспечивает наличие высокого потенциала с выходов элементов НЕ 12 (первых входов элементов И 13) и про. хождение счетных импульсов на счетчики 14. Кроме того, счетные импульtO сы проходят через элемент И 16 на вход счетчика 11 . через = 2, Т.e... с приходом второго импульса, который заполняет до полной емкости

Р счетчик 11, на первом входе элемен1s та И 13 появляется низкий потенциал, прекращается подача счетных импульсов на вход счетчика 14 . Одновременно сигнал переполнения счетчика 11 переводит триггеры 3> и 3 в нулевое

2в состояние, в результате чего с их выходов поступают импульсы напряжения через дифференцирующие цепочки 4 на триггеры 57 и 5В, а также через элементы ИЛИ jт и 7 на входы триг25 геров 9 и 9 Переброс триггеров 9> и 9 обеспечивает подачу счетных

9 94 чисел равен 1, то на выходе элемента

ИЛИ-НЕ 32„ (в старшем разряде ) фдрмируется О, который вырабатывает сигнал запрета для каждого из чисел.

При этом, если старший разряд i-го числа равен О, то все числа не проходят через элементы И 31 i-ой группы первого узла 28 переноса.. Если старший разряд i-ro числа равен "1", то i-ое число проходит через элементы И 31 i-ой группы первого узла

281 переноса.

Если старшие разряды всех чисел равны "О", то на выходе. элемента КЛИНЕ 32 формируется "1", которая дает разрешение на прохождение всех и чисел через элементы И 31 узла 28 .

Вторым элементом ИЛИ-НЕ 32 совместно с элементами ИЛИ 30 узла 28 анализируются вторые по старшинству разряды и чисел таким же образом, как и старших разрядов, и т.д.

Таким образом, позиционный код номера экстремального числа получается путем совпадения всех m сигналов запрета, сформированных в каждом

i-ом узле 28 переноса. импульсов через элементы И 10„ и

Работа устройства при определе" нии минимального пути в графе поясняется следующим примером: пусть задан граф, описываемый матрицей смежности A и вектором Т-"весов" дуг, причем

000000001

000000001

000000000

После занесения исходной информации на первом входе триггера 9 бу9 дет высокий потенциал, поэтому после подачи пускового сигнала íà вход.

26 устройства счетные импульсы с выхода генератора 20 через элемент И

21 будут поступать на входы элеменТ= 1; 2; 3; 4; 3i 2i 5; 4;2, 45 где элементы О, если нет дуги из

i-ой вершины в j-ye; а.. =

1, если есть дуга из

i äé вершины в j-ую;

"вес" i-ой вершины

Ю моделируемого графа, 10 на счетчики "весов" вершины

11 и llg. С приходом шестого импульса переполняется счетчик 11, после чего прекращается подача счетных импульсов на счетчик 14 и перебра;сываются в нулевое состояние триггеры 3В, ЗВ5 и 3В . Импульсы напряжения выхо ов эт их т иг е ов е с д р г р чер з дифференцирующие цепочки 4 поступают на соответствующие триггеры 5 и weменты ИЛИ 7„, 7, 76, перебрасывают триггеры 94, 9 и 9 в единичное состояние, тем самым обеспечивается поступление счетных импульсов через элементы И 104, 10 и 10 на счетчики 114, 115 и 116 и т.а Процесс подсчета имйульсов заканчивается с приходом одиннадцатого импуль. са, после чего все счетчики 11 бу-. дут переполнены, и с выхода элемен-. та И-НЕ 19 будет поступать низкий потенциал, поэтому прекращается подача счетных импульсов с выхода генератора 20 через элемент И 21. Показания счетчиков 14 соответствуют минимальным величинам путей для каждой вершины графы до его конечной вершины, при этом каждому номеру вершины сопоставлен свой счетчик. В дан- . ном примере эти показания (начиная с nepsora) ñëåäóþùèå: 10; 9; 11

1О; 9; 81;7; 6; 2 °

ll 9420

Наличие низкого потенциала на выходе элемента И-HE 19 обеспечивает подачу счетных импульсов с выхода генератора 20 на вход счетчика 24.

С приходом первого импульса возбужда- ется первая выходная шина дешифратора

25, и высокий потенциал поступает на первый вход элемента И 17 и далее на первые входы элементов И 6 первой строки матричной модели. Высо- 1О кий потенциал появляется только на выходах элементов 6,1, и 6, поэтому на входы блока 18 поступают только коды со счетчиков 14 и 14> через элементы И 15< и 151.. Минималь- 15 ный из этих кодов - 9, поэтому в ,единичное состояние будет переброшен триггер 16, и т.д. В результате минимальный путь составят вершины:

2; 7; 9 ° ю

Таким образом предлагаемое устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в у том, что значительно расширяются функциональные возможности; кроме величины минимального пути в графе, определяется также и конфигурация критического минимального пути при высоком Зв быстродействии по сравнению д другими аналогичными устройствами.

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

Устройство для определения минимальных путей в графах, содержащее формирователи дуг по числу строк и столбцов матричной модели графа, 40 каждый из которых содержит первыи триггер, выход которого соединен с входом дифференцирующей цепочки, первую группу элементов ИЛИ по числу строк матричной модели графа, входы которых подключены к выходам диффе"

45 ренцирующих цепочек одноименных строк матричной модели графа, группу триггеров по числу столбцов матричной модели графа, первую и вторую группы элементов И по числу столбцов матричной модели графа, счетчики по числу столбцов матричной модели графа, группу элементов HE по числу столбцов матричной модели графа, группу регистрирующих счетчиков по N числу столбцов матричной модели графа, первый элемент И, элемент И-HE и генератор тактовых импульсов, 30 12 при чем выходы дифференцирующи х цепочек формирователей дуг одноименной строки подключены к входам элемента

ИЛИ первой группы одноименной строки, выход каждого элемента ИЛИ группы соединен с входом триггера группы одноименного столбца, выход которого подключен к первому входу элемвнта И первой группы одноименного столбца, выход каторого соединен с входом счетчика группы одноименного столбца, выход генератора тактовых импульсов соединен с первым входом первого элемента И, выход которого подключен к вторым входам элементов

И первой группы: и первым входам элементов И второй группы, выход счетчика группы одноименного столбца соединен с входом элемента HE группы одноименного столбца, с входом первых триггеров формирователей дуг одноименного столбца и соответствующим входом элемента И-НЕ, выход которого подключен к второму входу первого элемента И, выход элемента

НЕ группы одноименного столбца соединен с вторым входом элемента И второй группы одноименного столбца, выход которого подключен к входу регистрирующего счетчика группы одноименного столбца, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, s него дополнительно введены элемент НЕ, второй элемент И, счетчик, дешифратор, третья и четвертая группы элементов И по числу столбцов матричной модели графа, группа регистрирующих триггеров по числу столбцов матричной моде. ли графа, вторая группа элементов

ИЛИ по числу столбцов матричной модели графа, блок выбора кодов максимального числа, а также в каждый формирователь дуг матричной модели графа дополнительно введены второй триггер и элемент И, причем в каждом формирователе дуг выход дифференцирующей цепочки подключен к входу второго триггера, выход которого соединен с первым входом элемента И, выходы элементов И формирователей дуг одноименного столбца соединены соответственно с входами элемента ИЛИ . второй группы одноименного столбца, выход которого подключен к первому входу элемента И третьей группы одноименного столбца, второй вход которого соединен с выходом регистрирующего счетчика группы одноименного столб13 9420 ца, второй вход которого соединен с выходом реги ст ри рующего счет чи ка группы одноименного столбца, выходы элементов И третьей группы подключены к соответствующим входам блока выбора кодов максимального числа, выходы которого соединены с входами регистрирующих триггеров группы, выход регистрирующего триггера группы одноименного столбца подключен к 10 первому входу элемента И четвертой группы одноименного столбца, выход которого соединен с вторыми входами элементов И формирователей дуг одноименной строки, выход генерато- И ра тактовых импульсов подключен к первому входу второго элемента И, 30 14 выход которого через счетчик соединен с входом дешифратора, выходы которого соединены соответственно с вторыми входами элемента И четвертой группы, выход элемента И-НЕ соединен с входом (элемента НЕ, выход которого подключен к второму входу второго элемента И.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке N 2830339/18-24, кл. 6 06 6 7/122, 1979.

2. Авторское свидетельство СССР по заявке и 2880614/18-24, кл. G 06 G 7/122, 1980 (прототип).

Составитель И. Дубинина

Редактор И. Ковальчук Техред Т. Наточка Корректор Г. Огар

Заказ 4842/40 Тираж 731 Подписное

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

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

Филиал ППП "Патент, г.ужгород, vn. Проектная, 4