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

Союз Советских Социалистических Республик(51)М. К.2 О 06 6 7/122 Государственный комитет СССР по делам изобретений и открытий(71 Заявитель 54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ГРАФЕ Изобретение относится к цифровой вычислительной технике и может быть применено при расчетах транспортной сети, сетевых графиков, электрических 5 сетей и тестов контроля релейных структур.Известно устройство для определения гамильтоновых линий на связном графе, содержащее двоичный счетчик, вход которого соединен со счетным входом первого триггера и выход - с нулевым входом второго триггера, единичный выход второго триггера соединен с управляющим входом первого ключа, информационный выход которого соединен со счетным входом первого триггера, печатающее устройство, вход которого соединен с выходом второго ключа, наборное поле, коммутирующее устройство, триггеры, ключи, диоды, элемент задержки. Особенностью устройства является то, что оно может выполнять анализ графов, связанный с выбором из множества перебираемых состояний графа отдельных состояний, обладающих определенными признаками 1.Однако формирователь, анализировать, выделять и обрабатывать ответную информацию тестовых команд, выдаваемых на входы модели граФа и выражающих один или несколько критических путей между заданными вершинами моделей ориентированных графов, такое устройство не может.Наиболее близким техническим решением к изобретению является устройство для моделирования экстремальных путей на графе, содержащее элемент И, выход которого соединен с счетным входом первого триггера и с входом счетчика, выход которого подключен к нулевому входу второго триггера, единичный выход которого соединен с, первым входом элемента И, второй вход которого является выходом устройства, нулевой выход первого триггера подключен к управляющему входу ключа, выход которого соединен с входом блока регистрации, линию задержки, выход которой подключен к нулевой вершине модели графа, каждая модель дуги которого состоит из последовательно соединенных Формирователя импульса, светодиода оптрона и линии задержки дуги, коммута" тор, входы которого подключены к соответствующим вершинам модели графа,Устройство позволяет проиэводить ранжирование вершин направленного граФа 2,Однако оно не позволяет определять экстремальные пути,Цель изобретения - расширениефункциональных воэможностей эа счетопределения экстремальных путеймежду любыми вершинами графа.Укаэанная цель достигается тем,что в устройство для определенияэкстремальных путей на графе, содержащее элемент И, выход которого соединен со счетным входом первоготриггера и с входом счетчика, выходкоторого подключен к нулевому входувторого триггера, единичный выход 415которого соединен с первым входом.эле(пента И, второй вход которогоявляется выходом устройства, нулевойвыхбд первого триггера подключен куправляющему входу ключа выход которного соединен с входом блока регистрации, линию задержки, выход которой подключен к нулевой вершине моделИ графа, каждая модель други которого состоит из последовательно сое- д 5диненных формирователя импульсасветодиода оптрона и линии задержкидугй, коммутатор, входы которого подключены к соответствующим вершинаммодФлн граФа, введены сумматор, блоккодирования и блок памяти тестовыхкоманд, выходы которого соединенычерез Фотодиоды соответствующихоптронов с соответствующими входамиблока кодирования,.выходы которогоподключены к входам сумматора, выходкоторого соединен с входом ключа,управляющий вход сумматора подключенк нулевому выходу первого триггера,единичный выход которого соединенс взводом линии задержки.и с управ.ляющим входом блока памяти тестовыхкоманд, управляющий выход которогоподключен к управляющему входу коммутатора.На чертеже приведена структурнаясхема устройства.Устройство содержит наборное поле1 дЛя набора моделей графов, формирователи 2 импульсов, оптроны 3, линию задержки дуги 4, первый триггер 5, блок 6 йамяти тестовых команд,линию задержки 7, ключ 8, коммутатор9, блок 10 кодирования, состоящий изперЕключателей 11 и диодов 12, блок13 регистрации, элемент 14 Ч, второйтЬиггер 15, счетчик 16, сумматор 17и вход 18,Блок 10 кодирования служит длявыражения продолжительности с каж1,)дой работы ( х х) двоичным кодом.Сумматор 17 осуществляет исследо Щвательное суммирование пачки импуль:ов иэ одного, двух и более двоичныхкодов, поступающих на его входы синтервалами задержки ь 1, задаваемыми линиями 4,Двоичный счетчик 16 Формирует импульс переполнения при отработке заданного числа управляющих тестовыхкоманд, поступающих иэ блока 6 черезвыходные цепи оптронов на блок 10кодирования.Работа устройства состоит в следующем,Ориентированный граф представляетсетевой график, на котором дугиграфа выражают работы, т.е. некоторые мероприятия, требующие затрат времени и материальных средств, а вершины граФа (х, х х х) выражают события, которые состоят в завершении одной или нескольких работ.Конечным событием считается завершение всего комплекса работ (проекта),События на сетевом графике пронумерованы, т.е. для любой (х х,)работы, выполняется условие 1 (и каждой (х , х) работе задана еепродолжительность,В блок 6 памяти тестовых команддля каждой пары событий (х 0, х ) заносятся группы наборов, каждый из которых выделяет один из путей междухи х,Каждый набор выделения пути междусобытиями х х формируется путемподстановки единиц в разряды, ссорветствующие дугам, входящим в нуть.Реализация любого набора в устройстве осуществляется путем подачи единичного сигнала через фотодиодыоптронов 3 тех дуг модели, которымсоответствуют единичные значения соответствующих переменных в наборе. Всеостальные Фотодиоды оптронов в дугахмодели графа обеспечены.При этом единичный сигнал, пропускаемый через выходную обмотку любогооптрона, при прохождении через блок10 преобраэовывается в двоичный код,задаваемый переключателями 11 прикаждом очередном распределении ресурсов (например, рабочей силы), формируемый двоичный код на выходе блока10 равен длительности работы.Поскольку по отдельному наборуподключаются фотодиоды оптронов,составляющих только один путь из хв х событие, то на выходе блока 10при каждОм импульсном возбужденииначала (х ) модели графа формируетсясерия параллельных двоичных кодовиз одного, двух, трех и т,д. кодовследующих с интервалами ь 1определенными линиями 4 задержки.Параллельные двоичные коды каждой серии последовательно суммируютсясумматором 17 и по команде записываются в блоке 13 в виде десятичного(Исх), по которой блок 6, счетчик 16, триггеры 5 и 15, сумматор 17,коммутатор 9 устанавливаются в исходное состояние, т.е. вершину гра 742962фа х, подключает на минус, элемент 14 закрывается, на вход 18 устройства подается последовательностьимпульсов частоты Г,В счетчик 16 вводится дополнение(Р), обеспечивающее выдачу импульса 5переполнения при отсчете всех наборов .С помощью переключателей 11 набираются двоичные числа, соответствующие продолжительности работ ОПо комайде Пуск триггер 15переходит в единичное состояниеи открывает элемент 14.Первый из импульсов частоты Йпоступает на вход счетчика 16 и счетный вход триггера 5. На единичном выходе триггера 5 формируется сигнал,который поступает на управляющийвход блока 6 и через линию 7 задержки на вход х (начало проекта) моделиграфа. При этом блок 6 выдает первыйнабор. Первый набор,пройдя через мо-,дель графа и блок 10 кодирования,поступает на ход сумматора 17 ввиде двоичного числа, отражающего С (продолжительность работы (первый25операнд), и суммируется с нулем(второй операнд) .В последующем при суммированиидвоичных кодов, соответствующих сериям импульсов, получаемые результа- ЗОты суммирования выступают в роливторого операнда операции суммирования,По второму импульсу частоты йтриггер 5 переходит в нулевое состояние и формирует команду управления,по которой начинается процесс суммирования, передачи полученного результата через ключ 8 на блок 13 и обнуление сумматора 17. 40По третьему импульсу частоты йтриггер 5 переводится в единичноесостояние и начинается второй циклреализации второго набора, при этомкоммутатор 9 подключает вершину графа х к минусу источника питания;По пятому, седьмому и последующим нечетным импульсам цикл реализации наборов повторяется, при этом хвераины графа подключаются к минусу 50источника тока после обработки всехнаборов, вычисленных для.х вершинымодели граФа.При отработке общего цикла, равного числу реализаций наборов, навыходе счетчика 16 Формируется импульс переполнения, который переводит триггер 15 в нулевое состояние,элемент 14 закрывается и работа устройства прекращается.По значению чисел, зафиксированных 60на бумажной ленте блока 13, определяют Т (критическое время) - наибольшее из чисел полного множествазафиксированных чисел; Я (критический путь) - соответствует дугам на бора, на котором определено критическое время Т ; Т (критическое(минимальное) время наступления события в )-ой вершине графа) - наибольшее из чисел подмножества, соответствующего х, х наборам; Я критический (максимальный) путь, соединяютщий события х и х ) - соответстовует дугам набора, на котором определено ТУстройство при наличии новых элементов и новых связей позволяет существенно расширить функциональныевозможности и вычислять критическиепути Я и время Т завершения проекта в целом и в каждой 3-ой вершинеориентированного графа (Т , Я) ) . Впроцессе выполнения проекта периодически и большое число раз производится распределение ресурсов (например,рабочей силы) на сети работ.Это приводит к необходимостивычисления большого объекта параметров Я , Т, Я , Т и связано сбольшйми,затратами времени и средств,устройство позволяет с высокой точностью,оперативностью и быстродействием производить вычисления исходных параметров для распределенияресурсов на сети работ, при этом поотношению к ручным методам быстродействие возрастает в зависимости отсложности графа на 2-4 порядка раз,исключаются субъективные ошибки исоздаются условия для принятияобъективных решений при распределенииресурсов,Формула из обретени яУстройство для определения экстремальных путей на графе, содержащее элемент И, выход которого соединен со счетным входом первого триггера, и с входом счетчика, выход которого подключен к нулевому входу второго триггера, единичный выход которого соединен с первым входом элемента И, второй вход которого является выходом устройства, нулевой выход первого триггера подключен к управляющему входу ключа, выход которого соединен с входом блока регистрации, линию задержки, выход которой подключен к нулевой вершине модели графа, каждая модель дуги которого состоит из последовательно соединенных формирователя импульса, светодиода оптрона и линии задержки дуги, коммутатор, входы которого подключены к соответствующим вершинам модели графа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения экстремальных путей между любыми вершинами графа, в него введены сумматор, блок кодирования и блок памяти тестовых команд, выходы742962 Составитель А.ЯицковТехред М, Петко Корректор Н,Григорук Редактор Т,Киселева Заказ 3620/1 б Тираж 751 Подписное ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москвар Ж 35 Раушская наб., д, 4/5Филиал ППП Патент, г. ужгород, ул, Проектная, 4,которого соединены через Фотодиодысоответствующих оптронов с соответству 1 ощими входами блока кодирования,выходы которого подключенык входамсумматора, выход которого соединенс входом ключа, управляющий входсумматора подключен к нулевому выходу первого триггера, единичный выход которого соединен с входом линии"задержки и с управляющим входом блок а и амя ти тестовых к оман д, упр авл яющий выход которого подключен к управляющему входу коммутатора.Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9424152, кл. С Об Р 15/20 1972,2, Авторское свидетельство СССРпо заявке Р 2447952/18-24,кл, 6 06 С 7/122 1977 (прототип),