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

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

Иллюстрации

Показать все

Реферат

 

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

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

Респубнин.К АВТОРСКОМУ СВИДВТИЛЬСТВУ (61) Дополнительное к авт. сена-ву— (22)Заявлена 01.02.80 (21) 2880614/18-24 с присоединением заявки М—

G 06 G 7/1.22

5мудаустиааьб1 квинтет

CCCP ав делан язабретевв11 н аткрнтвй (23) Приоритет—

Опубликовано 30.11.81, Бюллетень йа 44

Дата опубликования описания 30.11.81 (53) УДК 681.333. (088.8) О.А.Кузьйе"М 4 Щ9ъ у " щ,,д 1 (72) Авторы изобретения

В.А.Титов, Л.П.Гудыно, А.Г.Шевченко

""Мй4,"Р т 1 (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНЫХ

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

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

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

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

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

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

Необходимость в этом возникает, например, при решении задач планиро-. вания организации выполнения некоторого множества работ, представляемых сетевым графикам. В этом случае необходимо определение величины критических (минимальных) путей от произвоьной вершины графа до его конечной или (и) начальной вершины, не прибегая при этом к трудоемкому переходу от графа с нагруженными вершинами к графу с нагруженными дугами, как это предусмотрено в аналогичных устройствах. 10

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

Указанная цель достигается тем, что в устройство для определения минимальных путей в графах, содер- 20 жащее цепочки по числу строк и столбцов матричной модели сети из последовательно соединенных триггера и дифференцирующей цепочки, элементы ИЛИ по числу строк матричной модели се- ?s .ти, входы которых подключены к выходам дифференцирующих цепочек одноименных строк матричной модели сети, группу триггеров по числу столбцов матричной модели сети, первую и вторую группы щ элементов И по числу столбцов матричной модели сети, счетчики по числу столбцов матричной модели сети и генератор импульсов, введены группа элементов HE по числу столбцов матричной модели сети, группа регистрирующих счетчиков по числу столбцов матричной модели сети, элемент И-НЕ и элемент И, выход которого подключен к информационным входам элементов И первой и второй групп, управляющие входы которых соединены соответственно с выходами соответствующих триггеров группы и элементов НЕ одноименных столбцов матричной модели се45 ти, выходы элементов ИЛИ подключены ко входам триггеров соответствующих столбцов матричной модели сети, выход каждого элемента И первой группы соединен со входом счетчика одноименного столбца матричной модели сети, 50 выход каждого их которых подключен ко входам триггеров соответствующего столбца матричной модели сети, ко входу элемента НЕ одноименного» столбца матричной модели сети и к соответствующему входу элемента И-НЕ, выход которого соединен с первым входом элемента И, второй вход которого

886006

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

На чертеже представлена структур" ная схема устройства для определения минимальных путей в графах.

Устройство содержит матричную модель сети l, которая состоит из триггеров 2 1 с дифференцнрукщими цепочками 3 (1, = 1,л, где и число вершин в моделирующем графе, группу триггеров 4, первую группу с элементов И 5, счетчики 6, группу элементов НЕ 7, вторую группу элементов И 8, регистрирукщие счетчики 9, элемент И-HE 10, элемент И

11, генератор 12 тактовых импульсов, пусковой вход 13 и элементы

ИЛИ 14, при этом триггер 2 и диф;ференцирующая цепочка 3 образуют формирователь !5 дуг.

Устройство работает следующим образом, Первоначально в модель 1 заносится информация о топологии моделируемого графа (сети) . При этом триггеры

2„> формирователей 15 дуг устанавливаются в единичное состояние, если есть информационная связь из,1 -ой вершины в -ую вершину. Соответствующий формирователь 15 1,1 определяется пересечением строки с номером

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

j(f -ая вершина) . В счетчики б соответствующих вершин графа заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков, а счетчики 9 нахоцятся в сброшенном состоянии. В нулевое .состояние устанавливаются также и все триггеры 4, за исключением триггера, номер которого соответствует номеру конечной вершины (этот триггер устанавливается в единичное состояние) . При этом все триггеры 2 в строке, соответствующей конечной вевшине матричной мо-, дели, находятся в нулевом состоянии.

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

И 11 начинают поступать на входы элементов И 5 и 8 групп. Однако первоначально счетные импульсы проходят через элементы И 8 на все регистрирующие счетчики 9 и только через те. 886006

01 1000000

0001 1 01 00

00001 1000

0000001 1 0

0000 000! 0

0000001 1 О

000000001

000000001

000000000

Т =(1; 2; где

1; -"вес" емого графа. элементы И 5, на управляемом входе которых имеется высокий потенциал с единичного выхода триггера 4. В начальный момент такой потенциал поступает только на элемент И 5, соответствукиций конечной вершине.

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

6 переполняется, а сигнал переполнения с выхода счетчика 6 устанавливает в нулевое состояние все триггеры 2 в одноименном столбце матрицы.

Одновременно высокий потенциал с выхода переполненного счетчика 6 подается на одноименный вход элемента

И-НЕ 10 и элемент НЕ 7. Появление низкого потенциана на выходе элемента HE 7 (на управляемом входе элемента И 8) вызывает прекращение подачи счетных импульсов через элементы И 8 на вход регистра счетчика 9.

Переброс триггеров 2 в одноименном столбце в нулевое состояние вызывает появление импульса через дифференцирукнцие цепочки 3 и через элементы ИЛИ 1 4 на входе триггера 4 очередного столбца. Этот импульс переводит триггер 4 в единичное сос, тояние, благодаря чему на управляемом входе элемента И 5 одноименного столбца появляется высокий пстенциал. Появление разрешающего потенциала на управляемом входе элемента И 5 обеспечивает возможность прохождения счетных импульсов через элемент И 5 на вход счетчика 6 ("веса" вершины) очередного столбца матрицы. При этом формируется разрешение поступления счетчиков 6, из соответствукицих вершин которых исхо-. дят дуги, приводящие в сформированную ранее вершину.

Вычислительный процесс продолжается до тех пор, пока на выходах всех счетчиков 6 не будут присутствовать высокие потенциалы, появляющиеся из-за переполнения счетчиков.

Это свидетельствует о том, что все . узлы исследуемого графа сформированы.

Наличие высоких потенциалов на выходах счетчиков 6 обеспечивает через элемент И-НЕ 10 прекращение подачи счетных импульсов с выхода генератора !

2 через элемент И 11 на входы элементов И 5 и 8. Суммарное число импульсов, поступившее с выхода генератора 12 через элемент И 11 на входы счетчиков 9, соответствуют

4 кодам минимальных (критических,) величин путей графа из данной (в том числе и начальной) вершины до конечной вершины моделируемого графа сети.

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

А и вектором Т "весов" дуг, причем

3;4;3;2;5,4;2), О, если нет дуги из

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

i îé вершины в j-ую. -ой вершины моделируПосле занесения исходной информации на управляемом входе триггера

И 4 появляется высокий потенциал, поэтому после подачи пускового сигнала на вход 13 устройства счетные импульсы с выхода генератора 12 через элемент И 11 постунают на входы эле- ментов И 5 и 8, а далее — на входы всех регистрирующих счетчиков 9, так как отсутствие сигнала переполнения на счетчиках 6 "весов" вершин обеспечивает наличие высокого потенциа° ла с выходов элементов HE 7 (управляемых входов элементов И 8) и прохождение счетных импульсов на счетчики 9. Кроме того, счетные импульсы проходят через элемент И 51О на вход счетчика 61 . Через %<о 2, т.е. с приходом второго импульса, который заполняет до полной емкости счетчик

61О, на управляемом входе элемента

И 8,!> появляется низкий потенциал,. прекращается подача счетных импульсот на вход счетчика 9 0 . Одновременно сигнал переполнения счетчика 6.!!! переводит триггеры 2я

55 . с их выходов поступают импульсы напряжения через дифференцирующие цепочки 3 и элементы ИЛИ 148 и 14g на входы триггеров 4В и 4 . Переброс тоиггеров 4В и 4g обеспечивает пода886006

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

О1 1000000

0001 1 1000

0000001 00

0000001 I 0

00000001 0

000000001

000000001

000000000

А =

3О

SS чу счетных импульсов через элементы

И 5g и 5g на счетчики ЬЗ на бр "весоа" вершины. С приходом шестого импульса переполняется счетчик 6>, после чего прекращается подача счетных импульсов на счетчик 9 н перебрасываются в нулевое состояние триггеpbl 29, 29 и 2 9 ь . Импульсы напря жения с выходов этих триггеров через дифференцирующие цепочки 3 и элементы ИЛИ 14, 14 и 146 перебрасывают триггеры 4г,4 -и 46 в единичное состояние, тем самым обеспечивается поступление счетных импульсов через элементы И 5г, 59. и 56 на счетчики

6,6 и бя и т.п.

Вычислительный процесс заканчивается с приходом одиннадцатого импульса, после чего все счетчики 6 переполнены, и с .выхода элемента И-НЕ 10 поступает низкий потенциал, поэтому прекращается подача счетных импульсов с выхода генератора 12 через элемент И 11. Показания счетчиков 9 соответствуют минимальным величинам путей для каждой вершины графа до его конечной вершины, при этом каждому номеру вершины сопоставлен свой счетчик, В данном примере эти показания (начиная с первого) следунхцие: 10; — 9, I I) 10; 9; 8 7> 6 2.

При определении минимальных путей из первой вершины до любой (в том числе и конечной) вершины графа исходную матрицу А нужно заносить в транспанированном виде относительно не главной диагонали, т.е. матри-, цу А

Т = 21 4; 5; 2; Зэ 4у 3; 2» I)

По окончании работы устройства показания счетчиков 9 составляют 10, 10, 8; 6) бу 7) 4, 3; 1.

Таким образом, в предлагаемом устройстве для определения минимальных величин путей в графах значительно сокращаются аппаратурные затраты!

ЗФ

2S

ЗФ

SS

49 (приблизительно, с точностью до одного триггера, на(и -lq)cfeTwHKoB, s которые заносятся числа импульсов, дополняющие "веса" вершин до полной емкости счетчиков) по сравнению с известным устройством.

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

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

Редактор И.Михеева Техред И. Гайду Корректор М.Пожо

Заказ 10560/78 Тираа 748 Подписное

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

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

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

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

1 . .Авторское

У 525954, кл. G

2. Авторское

У 640314, кл. G

11 (прототип).

10 свидетельство СССР

06 F 15/20, 1974. свидетельство СССР

06 G 7/122, 1977