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

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

I

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

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

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

Наиболее близким к предлагаемому является устройство для определения экстремальных путей в графах, содержащее генератор тактовых импульсов, выход которого подключен к информационному входу элемента совпадения, матрицу формирователей дуг, каждый ПУТЕЙ В ГРАФАХ

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

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

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

20

Необходимость в этом возникает, например, при решении задач планиро-. вания организации выполнения некоторого множества работ, представляемых сетевым графикам. В этом случае необходимо определение величины критических (минимальных путей от произвоьной вершины графа до его конечной или (и начальной вершины, не прибегая при этом к трудоемкому пере ходу от графа с нагруженными вершинами к графу с нагруженными дугами, как это предусмотрено в аналогичных устройствах. Цель изобретения - повышение надежности устройства за счет сокращения аппаратурных затрат и .расширение его функциональных возможностей за счет определения величин минимальных путей от любой вершины графа до его конечной или начальной вершины. Указанная цель достигается тем, что в устройство для определения минимальных пут,ей в графах, содержащее цепочки по числу строк и столб цов матричной модели сети из последо вательно соединенных триггера и дифференцирующей цепочки, элементы ИЛИ по числу строк матричной модели сети, входы которых подключены к выход дифференцирующих цепочек одноименных строк матричной модели сети, группу триггеров по числу столбцов матрично модели сети, первую и вторую группы элементов И по числу столбцов матричной модели сети, счетчики по числу столбцов матричной модели сети и генератор импульсов, введены группа элементов НЕ по числу столбцов матрич ной модели сети, группа регистрирукяци счетчиков по числу столбцов матричной модели сети, элемент И-НЕ и элемент И, выход которого подключен к информационным входам элементов И первой и второй групп, управляющие входы которых соединены соответственно с вьгходами соответствуюпщх триггеров группы и элементов НЕ одноименных столбцов матричной модели сети, выходы элементов ИЛИ подключены ко входам триггеров соответствующих столбцов матричной модели сети, выход каждого элемента И первой группы соединен со входом счетчика одноименного столбца матричной модели сети, выход каждого их которых подключен ко входам триггеров соответствуюцего столбца матричной модели сети, ко входу элемента НЕ одноименного столбца матричной модели сети и к соответствующему входу элемента И-НЕ выход которого соединен с первым входом элемента И, второй вход которого подключен к выходу генератора импульсов , третий вход которого является входом устройства, выход каждого элемента И второй группы соединен со входом регистрирующего счетчика группы одноименногостолбца матричной модели сети. На чертеже представлена структурная схема устройства для определения минимальных путей в графах. Устройство содержит матричную модель сети I, которая состоит из триггеров с дифференцирующими цепочками 3((,з)7 Д число вершин в моделирующем графе, группу триггеров 4, первую группу элементов И 5, счетчики 6, группу элементов НЕ 7, вторую группу элементов И 8, регистрирующие счетчики 9, элемент И-НЕ 10, элемент И 1I, генератор 12 тактовых импульсов, пусковой вход 13 и элементы ИЛИ 14, при этом триггер 2 и диф;-ференцирующая цепочка 3 образуют формирователь 15 дуг. Устройство работает следукяии образом.. Первоначально в модель I заносится информация о топологии моделируемого графа (сети). При этом триггеры формирователей 15 дуг устанавлив единичное состояние, если ваются есть информационная связь из -ок вершины в j -ую вершину. Соответствукнций формирователь 15 fj определяется пересечением строки с номером i,(i -ая вершина и столбца с номером j ( /-ая вершина). В счетчики 6 соответствующих вершин графа заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков, а счетчики 9 находятся в сброшенном состоянии. В нулевое состояние устанавливаются также и все триггеры 4, за исключением триггера, номер которого соответствует номеру конечной вершины (этот триггер устанавливается в единичное состояние. При этом все триггеры 2 в строке, соответствующей конечной вершине матричной мо-в дели, находятся в нулевом состоянии. С появлением пускового сигнала на входе 13 элемента И 1 1 импульсы с выхода генератора I2 через элемент И I1 начинают поступать на входы элементов И 5 и 8 групп. Однако первоначально счетные импульсы проходят через элементы И 8 на все регистрирующие счетчики 9 и только через те 5.8 элементы И 5, на управляемом входе которых имеется высокий потенциал с единичного выхода триггера 4. В начальный момент такой потенциал посту пает только на элемент И 5, соответствукщий конечной вершине. Отсчитав число импульсов, пропорциональное весу моделируемой вершины графа, соответствукиций счетчик 6 переполняется, а сигнал переполнеНИН с выхода счетчика 6 устанавливает в нулевое состояние все триггеры 2 в одноименном столбце матрицы. Одновременно высокий потенциал с выхода переполненного счетчика 6 подается на одноименный вход элемента И-НЕ 10 и элемент НЕ 7. Появление низкого потенциана на выходе элемента НЕ 7 (на управляемом входе элемента И 8 вызывает прекращение подачи счетных импульсов через элементы И 8 иа вход регистра счетчика 9. Переброс триггеров 2 в одноименном столбце в нулевое состояние вызывает появление импульса через дифференцирукщие цепочки 3 и через элементы ИЛИ 14 на входе триггера 4 очередного столбца. Этот импульс переводит триггер 4 в единичное сос , тояние, благодаря чему на управляемом входе элемента И 5 одноименного столбца пояаляется высокий потенциал. Появление разрешающего потенциала на управляемом входе элеме та И 5 обеспечивает возможность про хождения счетных импульсов через элемент И 5 на вход счетчика 6 (веса вершины очередного столбца матрицы. При этом формируется разре шение поступления счетчиков 6, из соответствующих вершинкоторых исхо дят дуги, приводящие в сформированную ранее вершину. Вычислительный процесс продолжается до тех пор, пока на выходах всех счетчиков 6 не будут присутствовать высокие потенциалы, появля ющиеся из-за переполнения счетчиков Это свидетельствует о том, что все узлы исследуемого графа сформирован Наличие высоких потенциалов на выхо дах счетчиков 6 обеспечивает через элемент И-НЕ IО прекращение подачи счетных импульсов с выхода генерато 12 через элемент И 11 на входы элементов И 5 и 8. Суммарное число импульсов, поступившее с выхода генератора 12 через элемент И 11 на входы счетчиков 9, соответствуют одам минимальных (критических.) еличин путей Графа из данной (в том исле и начальной) вершины до конечой вершины моделируемого графа сети. Работу устройства при определеии минимальных путей в графе поясим на следующем примере. Пусть задан раф, описываемый матрицей смежности и вектором Т весов дуг, причем 01 1000000 0001 10100 00001 1000 0000001 10 А 000000010 000000110 000000001 000000001 000000000 т ; 2; 3; 4,- 3,- 2; 5-, 4} 2j, fO, если нет дуги из i-ой вершины в j-yw; И, если есть дуга из И-ой вершины в J-ую. 1 1 -ой вершины моделируемого графа. После занесения исходной информации на управляемом входе триггера 4.|g появляется высокий потенциал, поэтому после подачи пускового сигнала на вход 13 устройства счетные импульсы с выхода генератора 12 через элемент И 11 поступают на входы элементов И 5 и 8, а далее - на входы всех регистрирующих счетчиков 9, так как отсутствие сигнала переполнения на счетчиках 6 весов вершин.обеспечивает наличие высокого потенциала с выходов элементов НЕ 7 (управляемых входов элементов И 8 и прохождение счетных импульсов на счетчики 9. Кроме того, счетные импульсы проходят через элемент И на вход счетчика . Через т.е. с приходом второго импульса, который з олняет до полной емкости счетчик , на управляемом входе элемента И появляется низкий потенциал, прекращается подача счетных импульсог на вход счетчика . Одновременно сигнал переполнения счетчика 6 переводит триггеры 2e,io 29,iu в нулевое состояние, в результате чего с их выходов поступают импульсы напряжения через дифференцирующие цепочки 3 и элементы ИЛИ 14в и 14д на входы триггеров 4 и 4д. Переброс тоиггеров 4 и 4д обеспечивает пода7чу счетных импульсов через элементы И 50 и Зд на счетчики 6д на 65 весов вершины. С приходом шестого им пульса переполняется счетчик 6о, по ле чего прекращается подача счетных импульсов на счетчик 9 и перебрасьшаются в нулевое состояние тригге ры 2j ,235- и 2j. Импульсы напря жения с вькодов этих триггеров через дифференцирующие цепочки 3 и эл менты ИЛИ 144 5 перебрасьт ют триггеры 4, 4 в- и 4 в единичное состояние, тем самьим обеспечивается поступление счетных импульсов через элементы И 5 4 5j и 5 на счетчики 6 , 6jf и 6 ff и т.п. Вьмислительный процесс заканчивается с приходом одиннадцатого импуль са, после чего все счетчики 6 переполнены, и с выхода элемента И-НЕ IО поступает низкий потенциал, поэтому прекращается подача счетных импульсов с выхода генератора 12 через эле мент И II. Показания счетчиков 9 соо ветствуют минимальным величинам путей для каждой вершины графа до его конечной вершины, при этом каждому номеру вершины сопоставлен свой счет чик, В данном примере эти показания (начиная с первого) следующие: 10; 9у .П) 10} 9i 8 7) 6 2. При определении минимальных путей из первой вершины до любой (в том числе и конечной вершины графа исходную матрицу А нужно заносить в транспанированном виде относительно не главной диагонали, т.е. матрицу А 011000000 0001 1 1000 000101010 000000100 А 000000110 000000010 000000001 000000001 000000000 4, 5, 2i 3i 4 3-, 2s l По окончании работы устройства показания счетчиков 9 составляют 10, 10, 8-, 6) 6j 7$ 4 3,- 1. Таким образом, в предлагаемом устройстве для определения минимальньк величин путей в графах значитель но сокращаются аппаратурные затраты ( приблизительно, с точностью до одного триггера, на ()счетчиков, и которые заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков) по сравнению с известным устройством. Формула изобретения Устройство для определения минимальных путей в графах, содержащее цепочки по числу строк и столбцов матричной модели сети из последовательно соединенных триггера и дифференцирующей цепочки, элементы ИЛИ по числу строк матричной модели сети, входы которых подключены к выходам дифференхщруницих цепочек одноименных строк матричной модели сети, группу триггеров по числу столбцов матричной модели сети, первую и вторую группы элементов И по числу столбцов матричной модели сети, счетчики по числу столбцов матричной модели сети и генератор импульсов, отличающееся тем, что, с целью повьшгения надежности, в него введены группа элементов НЕ по числу столбцов матричной модели сети, группа регистрирукицих счетчиков по числу столбцов матричной модели сети, элемент И-НЕ и элемент И, выход которого подключен к информационным входам элементов И первой группы и второй труппы-, управляющие входы которых соединены соответственно с выходами соответствующих триггеров группы и элементов НЕ одноименных столбцов матричной модели сети, выходы элементов ИЛИ подключены ко входам триггеров соответствующих столбцов матричной модели сети, выход кавдого элемента И первой группы соединен со входом счетчика одноименного столбца матричной модели сети, выход каждого из которых подключен ко входам триггеров соответствующего столбца матричной модели сети, ко входу элемента НЕ одноименного столбца матричной модели сети и к соответствующему входу элемента И-НЕ, выход которого соединен с первым входом элемента И, второй вход которого подключен к выходу генератора импульсов, третий вход которого является входом устройства, выход каждого элемента И второй группы соединен со входом регистрирующего счетчи988600610

ка группы одноименного столбца ма:трич- 1. Авторское свидетельство СССР ной модели сети.№ 525954, кл. G Об F 15/20; 1974.

Источники информации, 640314, кл. G Об G 7/122, 1977

принятые во внимание при экспертизе t (прототип).

2. Авторское свидетельство СССР