Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/419 

Фи&1

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

Целью изоСретения является сокрэще- ,-ие аппаратурных затрат при поиске крити- -еского пути в графе.

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

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

Блок 2 определения дерева критических путей содержит коммутатор 9, многоканальный счетчик 10, накапливающий узел 11 логического сложения, узел 12 определения исходящих дуг, многоканальный таймер 13, узел 14 синхронизации, вход 15 пуска блока 2, выходы 16 и 17 узла 14, зходы 18 задания конечной вершины, выход 19 признака скончания моделирования конечной вершины пути блока 2, входы 20 задания начальной верчшны пути блока 2, входы 2; задания режима исполнения вершин блока 2, входы 22 признаков наличия дуг блока 2, выходы 23 признаков принадлежности дуг дереву критических путей и выход 24 узла 14 синхронизации.

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

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

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

взвешенным графом, и, закончив моделирование (исполнение) очередной вершины, выдает на один из своих выходов признак принадлежности дуги дереву критиЧ зских (экстремальных) путей. Закончив моделирование конечной вершины пути, блок 2 выдает на свой выход соответствующий признак. При этом блок 3 выдает на выходы в устройстве состав дуг критическо0 го пути в графе.

Блок 2 определения дерева критических путей работает следующим образом. Перед началом работы на один (или несколько) из входов 18 задания конечной вершины пути

5 подают сигнал уровня логической единицы. При этом коммутатор 9 подключает к своему информационному выходу соответствующий выбранному входу 18 (выбранным входам 18) информационный вход

0 (информационные входы). В К-и канал многоканального счетчика (К 1 В, где В количество вершин в графе) заносят число, дополняющее количество дуг, заходящих в К-ю вершину графа до полной емкости ка5 чала. По входу 20 блока 2 устанавливают в 1 Н- и разряд накапливающего узла 11 логического сложения, где Н - номер начальной вершины пути.

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

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

0На вход 15 пуска блока 2 подают сигнал

уровня логической единицы.

При этом узел 14 синхронизации формирует на своих выходах 16, 17 и 24 последовательность импульсов, предусмотренную

5 временной диаграммой его работы. Узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 17. При этом многоканальный таймер 13 устанавливает в О все признаки наличия пере0 полнения в группах каналов и в каналах групп, если отсутствует запрет их обнуления. Через время, достаточное для обнуле- н и ч признаков, узел синхронизации формирует импульс уровня логической еди5 ницы на своем выходе 24. При этом многоканальный таймер 13 выдает на свои выходы значения признаков наличия переполнения в группах каналов. Каналы счетчи- ка 10 увеличивав: свое значение на единицу (тем самым подсчитывается количество исполнения дуг, заходящих в вершину, номер которой соответствует номеру ка- нала счетчика). Одновременно накапливающий узел логического сложения устанавливает в 1 значение того информационного разряда, для которого выбрано первое направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них кратчайшего пути). В том случае, если один или несколько каналов счетчика 10 переполняется (т. е. если все входящие в вершину, номер которой соответствует номеру переполнившегося канала, дуги исполнены), то сигналами переполнения будут установлены в единичное состояние те разряды накапливающего узла логического сложения, для которых выбрано второе направление коммутации (тем самым фиксируется факт исполнения вершин при поиске проходящего через них дальнейшего пути). После установки в 1 всех разрешенных в данном цикле работы разрядов узла 11 узел 12 выдает на свои информационные выходы состав дуг, исходящих из всех опрошенных в данном цикле вершин. При этом многоканальный таймер 13 запускает те свои каналы, номера которых соответствуют дугам, исходящим из исполненных вершин. Одновременно таймер 13 останавливает работу тех своих каналов, которые относятся к группам, номера которых соответствуют номерам исполненных вершин, и запрещает установку в О признаков в этих группах. Через время, достаточное для окончания указанных действий, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 16. При этом те каналы таймера 13, работа которых разрешена в данном цикле, т. е. те, которые уже были запущены и которые не относятся к группам, работа которых запрещена (остановлена) ранее, увеличивают свое значение на единицу. Через время, достаточное для добавления единицы в каналах таймера 13, узел 14 синхронизации формирует импульс уровня логической единицы на своем выходе 24. После этого работа блока 2 повторяется.

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

.... В, где В - количество вершин в графе)

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

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

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

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

5 логического сложения, узел определения исходящих дуг, многоканальный таймер и узел синхронизации, причем вход пуска блока подключен к входу пуска узла синхронизации, с первого по третий выходы кото0 рого подключены к тактовому входу, к входу установки в О признаков и к входу опроса многоканального таймера соответственно, выход признака наличия переполнения в М--м канале К-й группы которого является

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

0 выходом признака окончания моделирования конечной вершины пути блока, вход задания режима исполнения К-й вершины и вход задания начальной вершины пути которого подключены к входу выбора на5 правления коммутации по К-му разряду информационного входа и к входу установки в 1 К-го разряда накапливающего узла логического сложения соответственно, М-й разряд информационного выхода которого подключен к М-му информационному входу

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

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

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

Фцг.2