Устройство для решения задач на графах

,.:1(Щ- ТЕ)гВЧЕВИ ,1 лИЭ 1 Егф А ИЯ Е ИЗОБР ЛЬСТВУ ОМУ СВИ АВ лирования в ССС 987 ССС 986 167фигОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР(71) Институт проблем модэнергетике АН УССР(56) Авторское свидетельствоФ 1418736, кл. С 06 Е 15/20,Авторское свидетельствоВ 1377867, кл. 6 06 Е 15/20,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧНА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано дляисследования путей в графах. Целью изобретения является сокращение аппаратурых затрат при поиске критического пути в графе, Устройство содержит блок 1 задания матрицы смежности, блок 2 определения дерева критических путей, блок 3 определения кратчайшего маршрута, вход 4 пуска устройства, входы 5 задания режимов исполнения вершин, входы 6 задания начальной вершины пути, входы 7 задания конечной вершины пути и выходы 8 признаков принадлежности дуг множеству дуг критического пути. Перед началом работы в блок 1 задания матрицы смежности заносят информацию а топологии графа, в блок 2 определения дерева кратчайших путей заносят информацию о весах дуг графа. На вход 4 пуска устройства подают сигнал уровня логической единицы. При этом на выходах 8 устройства формируется состав дуг (или вершин), принадлежащих критическому пути в графе. 1 з, и. ф - лы. 2 ил.Изобретение относится к вычислительной технике и может быть использовано дляисследования путей в графах,Целью изобретения является сокраще, ие аппаратурных затрат при поиске крити-еского пути в графе.На фиг, 1 представлена функцин;.льная схема устройства; на фиг, 2 - функционъьная схема блока определения деревакритических путей, 10Устройство содержит блок 1 заданияматрицы смежно ти, олок 2 определениядерева критических путей, Блок 3 определения кратчайшего маршрута, вход 4 пускаустройства, входы 5 задания режимов исполнения вершин, входы 6 задания начальной вершины пути, входы 7 заданияконечной вершины пути и выходы 8 признаков принадлежности дуг множеству дуг критическо о пути, 20Блок 2 определения дерева критическихпу 1 ей содержит коммутатор 9, многоканальный счетчик 10, накапливающий узел 11 логического сложения, узел 12 определенияисходящих дуг, многоканальный таймер 13, 25узел 14 синхронизации, вход 15 пуска блока2, выходы 16 и 17 узла 14, входы 18 заданияконечной вершины, выход 19 признакаокончания моделирования конечной вершины пути блока 2, входы 20 задания начальной вершины пути блока 2, входы 2:задания режима исполнения вершин блока2, входы 22 признаков наличия дуг блока 2,выходы 23 признаков принадлежности дугдереву критических путей и выход 24 узла 3514 синхронизации,Устрсйство работает следующим образом.Пусть требуется определить критический(максимальный или минимальный) путь 40в графе.Перед началом работы ь блок 1 заданияматрицы смежности заносят информацию отополо иирафа, в блок 2 определения дерева кратчайших путей заносят информацию о весах дуг (и/или вершин) графа,устанавливают ь исходное состояние (обнуляют) блок определения кратчайшего маршрута, по входам 5 задаю режимыисполнения вершин (например, в графе без 50взвешенных вершин при поиске кратчайшего пути вершина считается исполненной.тем исполнена котя бы одна входящая в неедуга, а при поиске длиннейшего пути - еслиисполнены все входящие в нее дуги), по 55входам 6 - начальную, а по входам 7 конечную вершины пути. На вход 4 пуска подают сигнал уровня логической еди: ицы. Приэ 1 ом блок 2 определения дерева критических путей моделирует сис 1 ему заданную взвешенным графом, и, закончив моделирование (исполнение) очередной вершины, выдает на один из своих выходов признак принадлежности дуги дереву критич вских экстремальных) путей. Закончив моделирование конечной вершины пути, блок 2 выдает на свой выход соответствующий признак. При этом блок 3 выдает на выходы в устройстве состав дуг критического пути в графе.Блок 2 определения дерева критических путей работает следующим образом. Перед началом работы на один (или несколько) из входов 18 задания конечной вершины пути подают сигнал уровня логической единицы, При этом коммутатор 9 подключает к своему информационному выходу соответствующий выбранному входу 18 (выбранным входам 18) информационный вход (информационные входы), В Кй канал многоканального счетчика (К = 1, В, где В - количество вершин в графе) заносят число, дополняющее количество дуг, заходящих в К-ю вершину графа до полной емкости канала. По входу 20 блока 2 устанавливают в "1" Н-й разряд накапливающего узла 11 логического сложения, где Н - номер начальной вершины пути,На входы 21 блока 2 подают набор логических нулей и/или единиц, задавая режим исполнения вершин графа, При этом для каждого разряда узла 11 выбирается информационное направление, определяющее накопление информации по данному разрядуОбнуляют все выходы признаков многоканального таймера 13, а его каналы загружают числами, определяющими веса соответствующих дуг графа,На вход 15 пуска блока 2 подают сигнал уровня логической единицы.При этом узел 14 синхронизации формирует на своих выходах 16, 17 и 24 последовательность импульсов, предусмотренную временной диаграммой его работы. Узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 17, При этом многоканальный таймер 13 устанавливает в "0" все признаки наличия переполнения в группах каналов и в каналах групп, если отсутствует запрет их обнуления. Через время, достаточное для обнуления признаков, узел синхронизации формирует импульс уровня логической единицы на своем выходе 24, При этом многоканальный таймер 13 выдает на свои выходы значения признаков наличия переполнения в группах каналов, Каналы счетчика 10 увеличивант свое значение на единицу (тем самым подсчитывается коли 16581715 10 чество исполнения дуг, заходящих в вершину, номер которой соответствует номеру канала счетчика), Одновременно накапливающий узел логического сложения устанавливает в "1" значение того информационного разряда, для которого выбрано первое направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них кратчайшего пути). В том случае, если один или несколько каналов счетчика 10 переполняется (т. е. если все входящие в вершину, номер которой соответсгвует номеру переполнившегося канала, дуги исполнены), то сигналами переполнения будут установлены в единичное состояние те разряды накапливающего узла логического сложения, для которых выбрано второе направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них дальнейшего пути), После установки в "1" всех разрешенных в данном цикле работы разрядов узла 11 узел 12 выдает на свои информационные выходы состав дуг, исходящих из всех опрошенных в данном цикле вершин. При этом многоканальный таймер 13 запускает те свои каналы, номера которых соответствуют дугам, исходящим из исполненных вершин, Одновременно таймер 13 останавливает работу тех своих каналов, которые относятся к группам, номера которых соответствуют номерам исполненных вершин, и запрещает установку в "0" признаков в этих группах, Через время, достаточное для окончания укаэанных действий, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 16, При этом те каналы таймера 13, работа которых разрешена в данном цикле, т. е, те, которые уже были запущены и которые не относятся к группам, работа которых запрещена (остановлена) ранее, увеличивают свое значение на единицу. Через время, достаточное для добавления единицы в каналах таймера 13, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 24. После этого работа блока 2 повторяется.Формула изобретения 1. Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок определения дерева критических путей и блок определения кратчайшего маршрута, причем вход пуска устройства подключен к входу пуска блока определения дерева критических путей, выход значения (К,М) - го элемента блока задания матрицы смежности (К = 1, , В, М = 1, , В, где 8 - количество вершин в графе) 15 20 25 30 35 40 45 50подключен к входу признака наличия (К,М) - й дуги блока определения кратчайшего маршрута и к входу признака наличия (К,М)-й дуги блока определения дерева критических путей, К-й вход задания начальной вершины пути которого является одноименным входом устройства, М-й вход задания конечной вершины пути которого подключен к одноименному входу блока определения дерева критических путей и к одноименному входу блока определения кратчайшего маршрута, выход признака принадлежности (К,М) - й дуги множества дуг кратчайшего маршрута которого является выходом признака принадлежности (К,М) - й дуги множеству дуг критического пути устройства, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат при поиске критического пути в графе. вход задания режиМа исполнения К-й вершины устройства подключен к одноименному входу блока определения дерева критических путей, выход признака принадлежности (К,М) - й дуги дереву критических путей и выход признака окончания моделирования конечной вершины пути которого подключены к входу признака принадлежности (К,М) - й дуги дереву критических маршрутов и к входу опроса конечной вершины блока определения кратчайшего маршрута соответственно.2. Устройство по и, 1, от л и ч а ю щ е ес я тем, что блок определения дерева критических путей содержит коммутатор, многоканальный счетчик, накапливающий узел логического сложения, узел определения исходящих дуг, многоканальный таймер и узел синхронизации, причем вход пуска блока подключен к входу пуска узла синхронизации, с первого по третий выходы которого подключены к тактовому входу, к входу установки в "0" признаков и к входу опроса многоканального таймера соответственно, выход признака наличия переполнения в М-м канале К-й группы которого является выходом признака принадлежности (К,М) - й дуги дереву критических путей блока, М-й вход задания конечной вершины пути которого подключен к М-му управляющему входу коммутатора, выход которого является выходом признака окончания моделирования конечной вершины пути блока, вход за 55 дания режима исполнения К - й вершины и К-й вход задания начальной вершины пути которого подключены к входу выбора направления коммутации по К - му разряду информационного входа ик входу установки в "1" К - го разряда накапливающего узла логического сложения соответственно, М - й разряд информационного выхода которого подключен к М - му информационному входу1658171 Фиг. Составитель А. Мишинор С. Пекарь Техред М,Моргентэл Корректор О.К Заказ 1714 Тираж 417 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5Производственно-издательский комбинат "Патент", г. Ужгоро Гагарина, 10 коммутатора. к входу останова каналов М-й группы и к входу запрета обнуления признаков в М-й группе каналов многоканального таймера и к входу опроса М-й вершины узла определения исходящих дуг, выход признака наличия (К,М)-Я исходящей дуги которого подключен к входу пуска М-го канала К-й группы многоканального таймера, выход признака наличия переполнения в К-й группе каналов которого подключен к К-му рвзряду первого информационного входа накапливающего узла логического сложения и к суммирующему входу К-го канала многоканального счетчика, выход признака пере полнения К-го канала которого подключенк К-му разряду второго информационного входа накапливающего узла логического сложения, вход признака наличия (К,М)-й дуги блока подключен к одноименному вхо ду узла определения исходящих дуг,