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

 

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является сокращение аппаратурных затрат при поиске критического пути в графе. Устройство содержит блок 1 задания матрицы смежности, блок 2 определения дерева критических путей, блок 3 определения кратчайшего маршрута, вход 4 пуска устройства, входы 5 задания режимов исполнения вершин, входы 6 задания начальной вершины пути, входы 7 задания конечной вершины пути и выходы 8 признаков принадлежности дуг множеству дуг критического пути. Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа, в блок 2 определения дерева кратчайших путей заносят информацию о весах дуг графа. На вход 4 пуска устройства подают сигнал уровня логической единицы. При этом на выходах 8 устройства формируется состав дуг (или вершин), принадлежащих критическому пути в графе. 1 з. п. ф-лы, 2 ил. fe

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si>s G 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

g-И:ИЮЭНМ,. „ йщ- ТЕ)Ж1 ЧЖИН, 15)ll1231 Et".A

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

567

Фиг.1 (21) 4626380/24 (22) 26.12.88 (46) 23.06.91. Бюл. М 23 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В. Васильев и В.Л. Баранов (53) 681.333 (088.8) (56) Авторское свидетельство СССР

N -1418736, кл. G 06 F 15/20, 1987.

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

М 1377867, кл. G 06 F 15/20, 1986, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является сокращение аппаратурных затрат при поиске критического пути в

„„.ЫЛ„„1658171 А1 графе. Устройство содержит блок 1 задания матрицы смежности, блок 2 определения дерева критических путей, блок 3 определения кратчайшего маршрута, вход 4 пуска устройства, входы 5 задания режимов исполнения вершин, входы 6 задания начальной вершины пути, входы 7 задания конечной вершины пути и выходы 8 признаков принадлежности дуг множеству дуг критического пути. Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа, в блок 2 определения дерева кратчайших путей заносят информацию о весах дуг графа. На вход 4 пуска устройства подают сигнал уровня логической единицы. При этом на выходах 8 устройства формируется состав дуг (или вершин), принадлежащих критическому пути в графе. 1 з, и. ф — лы. 2 ил.

1658171

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

Целью изобретения является сокращеие аппаратурных затрат при поиске крити- 5

-еского пути в графе.

На фиг, 1 представлена функци.. н; льная схема устройства; на фиг. 2 — функционъ ьная схема блока определения дерева критических путей, 10

Устройство содержит блок 1 задания матрицы см; жно ти, олок 2 определения дерева критических путей, Блок 3 определения кратчайшего маршрута, вход 4 пуска устройства, входы 5 задания режимов ис- 15 полнения вершин, входы 6 задания начальной вершины пути, входы 7 задания конечной вершины пути и выходы 8 признаков принадлежности дуг множеству дуг критическо о пути, 20

Блок 2 определения дерева критических пу ей содержит коммутатор 9, многоканальный счетчик 10, накапливающий узел 11 логического сложения, узел 12 определения исходящих дуг, многоканальный таймер 13, 25 узел 14 синхронизации, вход 15 пуска блока

2, выходы 16 и 17 узла 14, входы 18 задания конечной вершины, выход 19 признака окончания моделирования конечной вершины пути блока 2, входы 20 задания началь- 30 ной вер мины пути блока 2, входы 2: задания режима исполнения вершин блока

2, входы 22 признаков наличия дуг блока 2, выходы 23 признаков принадлежности дуг дереву критических путей и выход 24 узла 35

14 синхронизации, Устрсйство работает следующим образом.

Пусть требуется определить критичеcêèé(максимальный или минимальный) пyть 40 в графе.

Перед началом работы ь блок 1 задания матрицы смежности заносят информацию о топологии рафа, в блок 2 определения дерева кратчайших путей заносят информа- 45 цию о весах дуг (и/или вершин) графа, устанавливают ь исходное состояние (обнуляют) блок определения кратчайшего маршрута, по входам 5 задаю режимы исполнения вершин (например, в графе без 50 взвешенных вершин при поиске кратчайшего пути вершина считается исполненной. тем исполнена котя бы одна входящая в нее дуга, а г ри поиске длиннейшего пути — если исполнены все входящие в нее дуги). по 55 входам 6 — начальную, а по входам 7 конечную вершины пути. На вход 4 пуска подают сигнал уровня логической еди: IIIqu. При э1ом блок 2 определения дерева критических путей моделирует систему. заданную взвешенным графом, и, закончив моделирование (исполнение) очередной вершины, выдает на один из своих выходов признак принадлежности дуги дереву критич . с ких (э кстре мал ьн ых) путей. Э а кончи в моделирование конечной вершины пути, блок 2 выдает на свой выход соответствующий признак. При этом блок 3 выдает на выходы в устройстве состав дуг критического пути в графе.

Блок 2 определения дерева критических путей работает следующим образом. Перед началом работы на один (или несколько) из входов 18 задания конечной вершины пути подают сигнал уровня логической единицы, При этом коммутатор 9 подключает к своему информационному выходу соответствующий выбранному входу 18 (выбранным входам 18) информационный вход (информационные входы), В К--й канал многоканального счетчика (К = 1, ..., В, где В— количество вершин в графе) заносят число, дополняющее количество дуг, заходящих в

V.-ю вершину графа до полной емкости канала. По входу 20 блока 2 устанавливают в

"1" Н-й разряд накапливающего узла 11 логического сложения, где Н вЂ” номер начальной вершины пути, На входы 21 блока 2 подают набор логических нулей и/или единиц, задавая режим исполнения вершин графа. При этом для каждого разряда узла 11 выбирается информационное направление, определяющее накопление информации по данному разряду

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

На вход 15 пуска блока 2 подают сигнал уровня логической единицы.

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

При этом многоканальный таймер 13 устанавливает в "0" все признаки наличия переполнения в группах каналов и в каналах групп, если отсутствует запрет их обнуления. Через время, достаточное для обнуления признаков, узел синхронизации формирует импульс уровня логической единицы на своем выходе 24. При этом многоканальный таймер 13 выдает на свои выходы значения признаков наличия переполнения в группах каналов. Каналы счетчика 10 увеличивант свое значение на единицу (тем самым подсчитывается коли1658171

10

55 чество исполнения дуг, заходящих в вершину, номер которой соответствует номеру канала счетчика), Одновременно накапливающий узел логического сложения устанавливает в "1" значение того информационного разряда, для которого выбрано первое направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них кратчайmего пути). В том случае, если один или несколько каналов счетчика 10 переполняется (т. е. если все входящие в вершину, номер которой соответсгвует номеру переполнившегося канала, дуги исполнены), то сигналами переполнения будут установлены в единичное состояние те разряды накапливающего узла логического сложения, для которых выбрано второе направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них дальнейшего пути), После установки в "1" всех разрешенных в данном цикле работы разрядов узла 11 узел 12 выдает на свои информационные выходы состав дуг, исходящих из всех опрошенных в данном цикле вершин. При этом многоканальный таймер 13 запускает те свои каналы, номера которых соответствуют дугам, исходящим из исполненных вершин. Одновременно таймер 13 останавливает работу тех своих каналов, которые относятся к группам, номера которых соответствуют номерам исполненных вершин, и запрещает установку в "0" признаков в этих группах.

Через время, достаточное для окончания укаэанных действий, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 16. При этом те каналы таймера 13, работа которых разрешена в данном цикле, т. е. те, которые уже были запущены и которые не относятся к группам, работа которых =.àïðåùåíà (остановлена) ранее, увеличивают свое значение на единицу. Через время, достаточное для добавления единицы в каналах таймера 13, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 24. После этого работа блока 2 повторяется.

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

1. Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок определения дерева критических путей и блок определения кратчайmего маршрута, причем вход пуска устройства подключен к входу пуска блока определения дерева критических путей, выход значения (К,М) — го элемента блока задания матрицы смежности (К = 1, ..., В, М = 1, ..., В, где 8 — количество вершин в графе) 15

50 подключен к входу признака наличия (К,М)— и дуги блока определения кратчайшего маршрута и к входу признака наличия (К,M)-й дуги блока определения дерева критических путей, К-й вход задания начальной вершины пути которого является одноименным входом устройства, М-й вход задания конечной вершины пути которого подключен к одноименному входу блока определения дерева критических путей и к одноименному входу блока определения кратчайшего маршрута, выход признака принадлежности (К,М) — и дуги множества дуг кратчайшего маршрута которого является выходом признака принадлежности (К,М) — и дуги множеству дуг критического пути устройства, о тл и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат при поиске критического пути в графе. вход задания режиМа исполнения К-й вершины устройства подключен к одноименному входу блока определения дерева критических путей, выход признака принадлежности (К,М) — и дуги дереву критических путей и выход признака окончания моделирования конечной вершины пути которого подключены к входу признака принадлежности (К,М) — и дуги дереву критических маршрутов и к входу опроса конечной вершины блока определения кратчайшего маршрута соответственно.

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

М-м канале К-й группы которого является выходом признака принадлежности (К,M) — и дуги дереву критических путей блока, М-й вход задания конечной вершины пути которого подключен к М-му управляющему входу коммутатора, выход которого является выходом признака окончания моделирования конечной вершины пути блока, вход задания режима исполнения К вЂ” и вершины и

К-й вход задания начальной вершины пути которого подключены к входу выбора направления коммутации по К вЂ” му разряду информационного входа и к входу установки в

"1" К вЂ” го разряда накапливающего узла логического сложения соответственно, М вЂ” и разряд информационного выхода которого подключен к М вЂ” му информационному входу

1658171

Составитель А. Мишин

Техред М,Моргентэл Корректор О.Кравцова

Редактор С. Пекарь

Заказ 1714 Тираж 417 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина. 101 коммутатора. к входу останова каналов М-й группы и к входу запрета обнуления признаков в М-й rpynne каналов многоканального таймера и к входу опроса М-й вершины узла определения исходящих дуг, выход признака наличия (К,М)-й исходящей дуги которого подключен к входу пуска М-ro канала K-A группы многоканального таймера, выход признака наличия переполнения в К-й группе каналов которого подключен к К-му рэзряду первого информационного входа накапливающего узла логического сложения и к суммирующему входу К-го канала многоканального счетчика, выход признака пере5 полнения К-го канала которого подключен к К-му разряду второго информационного входа накапливающего узла логического сложения, вход признака наличия (К,М)-й дуги блока подключен к одноименному вхо10 ду узла определения исходящих дуг,