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

 

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

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

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22} Заявлено 21.1277 (21) 2558658/18-24 с присоединением заявки Мо(23) Приоритет— (53}М. Кл.2

G G 7/122

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 25.06.80. Бюллетень È9 23

Дата опубликования описания 25,06.80 (S3) УДК 681.3çç. (088. 8) (72) Авторы изобретения

П.Е.Чистяков, В.А.Окунев и О.А.Романюха (71) Заявитель (5 4) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ

ПУТЕЙ НА ГРАФЕ

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

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

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

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

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

Устройство позволяет проиэводить ранжирование в ершин н аправленного граФа (2) .

Однако оно не позволяет определять экстремальные пути.

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

Укаэанная цель достигается тем, что в устройство для определения экстремальных путей на графе, содержащее элемент И, выход которого соединен со счетным входом первого триггера и с входом счетчика, выход которого подключен к нулевому входу второго триггера, единичный выход 15 которого соединен с первым входом. элемента И, второй вход которого является выходом устройства, нулевой выход первого .триггера подключен к управляющему входу ключа„ выход ко- 20 торого соединен с входом блока регистрации, линию задержки, выход которой подключен к нулевой вершине моделИ графа, каждая модель други которого состоит из последовательно сое- 75 диненных формирователя импульса„ светодиода оптрона и линии задержки дугй, коммутатор, входы которого подключены к соответствующим вершинам модфлн графа, введены сумматор, блок кодирования и блок памяти тестовых команд, выходы которого соединены через Фотодиоды соответствующих оптронов с соответствующими входами блока кодирования,.выходы которого подключены к входам сумматора, выход котОрого соединен с входом ключа, управляющий вход сумматора подключен к нулевому выходу первого триггера, единичный выход которого соединен с входом линии задержки.и с управ- 40 .ляющим входом блока памяти тестовых команд, управляющий выход которого подключен к управляющему входу коммутатора.

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

Устройство содержит наборное поле

1 дЛя набора моделей графов, формирователи 2 импульсов, оптроны 3, линию задержки дуги 4,. первый триггер 5, блок 6 йамяти тестовых команд, линию задержки 7, ключ 8, коммутатор

9, блок 10 кодирования, состоящий из перЕключателей 11 и диодов 12, блок

13 регистрации, элемент 14 Ч, второй тЬиггер 15, счетчик 16, сумматор 17 и вход 18.

Блок 10 кодирования служит для выражения продолжительности i- каж

1,) дой работы (х;, х„) двоичным кодом.

Сумматор 17 осуществляет исследо Щ вательное суммирование пачки импуль=ов иэ одного, двух и более двоичных .кодов, поступающих на его входы с интервалами задержки z t, задаваемыми линиями 4, Двоичный счетчик 16 Формирует импульс переполнения при отработке заданного числа управляющих тестовых команд, поступающих иэ блока 6 через выходные цепи оптронов на блок 10 кодирования.

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

Ориентированный граф представляет сетевой график, на котором дуги графа выражают работы, т.е. некоторые мероприятия, требующие затрат времени и материальных средств, а вершины графа (х„, х,, х ... х„) выражают события, которые состоят в завершении одной или нескольких работ.

Конечным событием считается завершение всего комплекса работ (проекта) .

События на сетевом графике пронумерованы, т.е. для любой (х;, х, } работы, выполняется условие i (3 и каждой (х, х„) работе задана ее продолжительность.

В блок 6 памяти тестовых команд для каждой пары событий (х, х ) заносятся группы наборов, каждый из кото рых выделяет один из путей между хо и х4

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

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

При этом единичный. сигнал, пропускаемый через выходную обмотку любого оптрона, при прохождении через блок

10 преобраэовывается в двоичный код, задаваемый переключателями 11 при каждом очередном распределении ресурсов (например, рабочей силы) . Формируемый двоичный код на выходе блока

10 равен длительности работы.

Поскольку по отдельному набору подключаются фотодиоды оптронов, составляющих только один путь из х в х событие, то на выходе блока 10 при каждом импульсном возбуждении начала (х ) модели графа формируется серия параллельных двоичных кодов из одного, двух, трех и т.д. кодов„следующих с интервалами h t определенными линиями 4 задержки.

Параллельные двоичные коды каждой серии последовательно суммируются сумматором 17 и по команде записываются в блоке 13 в виде десятичного (двоичного) числа, Формируется команда Исходное (Исх ), по которой блок 6, счетчик 16, триггеры 5 и 15, сумматор 17, коммутатор 9 устанавливаются в исходное состояние, т.е. вершину гра742962 фа х, подключает на минус, элемент 14 закрывается, на вход 18 устройства подается последовательность импульсов частоты

В счетчик 16 вводится дополнение (D), обеспечивающее выдачу импульса 5 переполнения при отсчете всех наборов .

С помощью переключателей 11 набираются двоичные числа, соответствующие продолжительности работ !О

По комайде Пуск триггер 15 переходит в единичное состояние и открывает элемент 14.

Первый из импульсов частоты f поступает на вход счетчика 16 и счет- 5 ный вход триггера 5. На единичном выходе триггера 5 формируется сигнал, который поступает на управляющий вход блока 6 и через линию 7 задержки на вход х (начало проекта) модели графа. При этом блок 6 выдает первый набор. Первый набор, пройдя через мо-, дель графа и блок 10 кодирования, поступает на вход сумматора 17 в виде двоичного числа, отражающего t> продолжительность работы (первый 25 операнд), и суммируется с нулем (второй операнд) .

В последующем при суммировании двоичных кодов, соответствующих сериям импульсов, получаемые результаты суммирования выступают в роли второго операнда операции суммирования.

По второму импульсу частоты f триггер 5 переходит в нулевое состоя- 35 ние и формирует команду управления, по которой начинается процесс суммирования, передачи полученного результата через ключ 8 на блок 13 и обнуление сумматора 17. 40

По третьему импульсу частоты f триггер 5 переводится в единичное состояние и начинается второй цикл реализации второго набора, при этом коммутатор 9 подключает вершину графа х к минусу источника питания ° ;

По пятому, седьмому и последующим нечетным импульсам цикл реализации наборов повторяется, при этом х. вераины графа подключаются к минусу 5О источника тока после обработки всех наборов, вычисленных для.х„ вершины модели графа.

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

По значению чисел, зафиксированных 6О на бумажной ленте блока 13, определяют Т„(критическое время) - наибольшее из чисел полного множества зафиксированных чисел; S (критический путь) — соответствует дугам на- 65 бора, на котором определено критическое время T„Т (критическое

J (минимальное) время наступления собы тия в )-ой вершине графа) — наибольшее из чисел подмножества, соответствующего х, х наборам; S критический (максимальный) путь, соединяю щий события х и х ) — соответсто вует дугам набора, на котором определено Т„.

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

Это приводит к необходимости вычисления большого объекта параметров S Т, $„, Т„ и связано с большйми,затратами времени и средств. устройство позволяет с высокой точностью,оперативностью и быстродействием производить вычисления исходных параметров для распределения ресурсов на сети работ, при этом по отношению к ручным методам быстродействие возрастает в зависимости от сложности графа на 2-4 порядка раз, исключаются субъективные ошибки и создаются условия для принятия объективных решений при распределении ресурсов.

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

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

742962

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

Техред N. Петко Корректор Н.Григорук

Редактор Т.Киселева

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

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

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

Филиал ППП Патент, r ужгород, ул, Проектная, 4, которого соединены через фотодиоды соответствующих оптронов с соответству1ощими входами блока кодирования, выходы которого подключены к входам сумматора, выход которого соединен с входом ключа, управляющий вход сумматора подключен к нулевому выходу первого триггера, единичный выход которого соединен с входом линии

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

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

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

1424152, кл. G 06 F 15/20„ 1972, 2. Авторское свидетельство СССР по заявке Р 2447952/18-24, кл G 06 G 7/122,, 1977 (прототип) °