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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (6!) Дополнительное к авт. свид-ву Р 491132 (22} Заявлено 060378 (21) 2587569/18-24 ($)) . ял.2

G 06 F 15/20 с присоединением заявки ¹

Государственный комитет с с с р. по делам изобретений и открытий (23) Приоритет

Опубликбвано 3006.80.Бюллетень ¹ 24 (53) УДК 681 ° 333 (088. 8) Дата опубликования описания 30.06.80 (72) Авторы изобретения

С. В. Назаров и В. A. Титов (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНЫХ

ВЕЛИЧИН ПУТЕЙ В ГРАФАХ

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

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

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

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

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

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

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

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

На чертеже показана структурная схема предлагаемого устройства.

Оно содержит матричную модель 1 сети,. блок 2 управления, генератор

3 тактовых импульсов„ формирователи

4 весов луг, включающие счетчик 5 и триггер 6, элементы И 7, элементы

HE 8, дополнительные элементы И 9 и регистрирующие счетчики 10. устройство работает следующим образом.

Первоначально в модель 1 заносит(О ся информация о топологии моделируемого графа (сети) . При этом триггеры 6 формирователей 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 20

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

Счетчики 10 в исходном состоянии сброшены в нулевое состояние.

Исходный граф заносится в матричную модель сети в инверсном порядке, 40 т.е. матрица смежности заносимого графа транспортирована относительно неглавной диагонали . Это позволяет использовать для расчета максимальных путей в графе процедуру динами- 45 ческого программирования °

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

3 на .входы всех элементов И 9. При этом импульсы проходят только на входы счетчиков 5 тех формирователей 4, которые моделируют веса дуг, исходящих из начальных узлов.

Эти же импульсы проходят на регистрирующие счетчики 10 всех вершин графа, кроме начальной, так как на выходе соответствующего элемента 7 высокий потенциал, а следовательно, на выходе элемента HE 8 низкий.

Отсчитав число импульсов, пропор- Щ циональное весу моделируемой дуги, счетчик 5 одного из формирователей переполняется, устанавливает.в нулевое состояние соответствующий триггер 6, и на вход соответствующего g5 элемента И 7 поступает разрешение с нулевого выхода этого триггера.

Если на остальных входах этого элемента И 7 — разрешающие потенциалы, то на его выходе появляются импульсные сигналы. Это свидетельствует о том, что все веса дуг, входящих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом 7, сформированы. При этом формируется разрешение поступления импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исходящие из сформированного узла, Одновременно. с этим на вход элемента HE 8 одноименного столбца подается высокий потенциал, а с его выхода — низкий, следовательно, подача импульсов на вход счетчика 10 через элемент И 9 прекратится и на выходе счетчика 10 зафиксируется время максимального пути для данной вершины графа.

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

Блок 2 управления при этом прекраща-, ет подачу импульсов на входы формирователей 4 и элементов 9. число импульсов, зафиксированное на счетчиках 10, соответствует максимальной величине пути для данной вершины (величине максимального пути в графе от данной вершины до конечной).

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

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

ФорМула изобретения-, Устройство для. определения максимальных величин путей в графах по авт .св. Р 491132, о т л и ч а ю щ ее с я тем, что, с целью расширения

Функциональных возможностей за счет

J 144592

Составитель A.ßèöíîâ

ТехредХ. Кастелевич Корректор М.Вигула

Редактор Т,Горячева

Заказ 3663/4 Тираж 751 Подписное

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

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

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