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

 

УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ. ОПТИМАЛЬНОГО ДЕРЕВА ГРАФА, содержащее генератор импульсов, формировательимпульсов , блок управления, включающий счетчик, и модели ветвей, соединенные согласно топологии графа , причем каждая модель ветви содержит , счетчик, о т л ич а ю щее с я тем, что, с целью повышения быстродействия, в него введены в каждую модель ветви сумматор по модулю два и реле, а в блок управления - триггер, ключ, одновибратор, регистр и элемент ИЛИ, причем в каждой модели ветви выход сумматора по модулю два соединен со счетным входом счетчика модели ветви, выход которого подключен к обмотке реле, первый вход сумматора по модулю .два через первый эамыкакщий контакт реле соединен со своим вторым вхо- ; дом, выход счетчика через второй и . . третий замыкающие контакты реле подключен соответственно к выходу . устройства, входу элемента ИЛИ и информационному входу регистра, вы .ход элемента ИЛИ соединен с входом одновибратора и первым S-вхрдом триггера, первый R-вход которого является входом устройства, второй R-вход триггера подключен к единич ному выходу последнего разряда регистра , вход считывания которого соединен с выходом ключа, информационный и управляющий входы кот.оро го подключены к выходам генератора сл импульсов и одновибратор а соответственно , выход регистра соединен со счетным входом счетчика блока управления , выход которого подключен к второму З входу триггера, выход которого соединен с входом формирователя импульсов и установочными со входами счетчиков моделей ветвей, а Од выход формирователя импульсов под00 ключен к первым входам сумматоров со по модулю два моделей ветвей, исхоо дя1цих из начальной вершины графа. .

СОЮЗ COBETCHHX

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

РЕСПУБЛИК (19) (И1. (594 6 F. 15 20

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3754916/24-24 (22) 13.06.84 (46) 07.12.85. Бюл. У 45 (72) Г.С.Колесник (53) 681. 331 (088. 8) (56) Авторское свидетельство СССР

Ф 329538, кл, G 06.С 7/48, 1970.

Авторское свидетельство СССР ((732898, кл, С 06 G 7/122, 1977.. (54)(57) УСТРОЙСТВО.ДЛЯ НАХОЖДЕНИЯ.

ОПТИМАЛЬНОГО ДЕРЕВА ГРАФА, содержащее генератор импульсов, формирователь импульсов, блок управления, включающий счетчик, и модели. ветвей, соединенные согласно топологии графа, причем каждая модель ветви содер кит счетчик, о т л и ч а ю щ ее с я тем, что, с целью повышения ..быстродействия, в него введены в каждую модель ветви суиматор по модулю два и реле, а в блок управления - триггер, ключ, одновибратор, регистр и элемент ИЛИ, причем в каждой модели ветви выход сумматора по модулю два соединен со счетным входои счетчика иодели ветви выход которого подключен к обмотке реле, первый вход сумматора по модулю. два через .первый эаиыкающий контакт реле соединен со своим вторым вхо- : дом, выход счетчика через второй и третий замыкающие контакты реле подключен соответственно к выходу устройства, входу элемента ИЛИ и информационному входу регистра, вы.ход элемента ИЛИ соединен с входом одновибратора и первым S-входом триггера, первый R-вход которого является входом устройства, второй

R-вход триггера подключен к единичному выходу последнего разряда регистра, вход считывания которого соединен с выходом ключа, информационный и управляющий входы которого подключены к выходам генЕратора импульсов и одновибратора соответственно, выход регистра соединен со счетным входом счетчика блока управления, выход которого подключен к второму S-входу триггера, выход которого соединен с входом формирователя импульсов и установочными входами счетчиков моделей ветвей, а выход формирователя импульсов подключен к первыи входам сумматоров по модулю два моделей ветвей, исходящих иэ начальной верщины графа, Ф 11

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

Цель изобретения — повышение быстродействия.

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

Устройство содержит модели ветвей 1, соединенные:согласно топологии графа, формирователь 2 импульсов, генератор 3 импульсов, блок 4 управления, Каждая модель ветви содержит сумматор 5 по модулю два, счетчик 6 ° реле 7 с замыкающими контактами 8 -8, входные и выходные полюса 9-12. Блок 4 управления содержит элемент ИЛИ 13 ° счетчик 14, триггер 15, ключ 16, одновибратор 17, регистр 18.

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

В исходном положении регистр 18 обнулен, триггер 15 находится в единичном состоянии (цепи установки в исходное состояние на чертеже не показаны). Наличие единичного потенциала на входе формирователя 2 импульсов запрещает выдачу импульсов на выход. В счетчики 6 заносят количество импульсов, пропорциональное весу ветвей — при определении дерева максимального веса, и равное М-В, (М— емкость счетчика,  — вес i-й ветви) — при определении дерева мини— мального веса. В графе с К вершинами дерево образует К-1 ветвей, поэтому в счетчик 14 заносят количество импульсов М-К+1, При поступлении сигнала с входа устройства на первый R-вход триггера 15 нулевой сигнал с его выхода поступает на вход формирователя 2 импульсов и разрешает выдачу импульсов на первые входы сумматоров 5 моделей ветвей, идентичных начальной вершине графа. Так как на вторые входы сумматоров 5 импульсы не поступают, то с выхода сумматоров 5 импульсы поступают на счетные входы счетчиков 6. Будем рассматривать задачу нахождения дерева минимального веса; тогда первым переполняется счетчик 6 ветви наименьшего веса и выдает импульс переполнения на обмотку реле 7. Оно срабатывает, самоблокируется до конца работы уст96890 2 ройства н замыкает контакты 8 -8

1 3 обуславливая соединение обоих входов сумматора 5, выдачу импульса на соответствующий выход устройства, выдачу импульса на соответствующие входы регистра 18 и элемента ИЛИ 13. Регистр 18 запоминает единицу в ячейке памяти, а с выхода элемента ИЛИ 13 импульс поступает щиеся единицы поступают на счетный вход счетчика 14, который соответственно увеличивает свои показания, I

По окончании опроса сигнал с единичного выхода последнего разряда регистра 18 поступает на второй

R- xone триггера 15, который выдает нулевой сигнал на вход формирователя 2 импульсов. Последний возобновляет выдачу импульсов на первые входы сумматоров 5 моделей ветвей, идентичных начальной вершине графа, и моделей ветвей, первые входы сумматоров 5 которых оказались подключенными к выходу формирователя

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

1в на первый S-вход триггера 15, который выдает Единичный сигнал на вход формирователя 2 импульсов и запрещает выдачу им импульсов на выход, а также на установочные входы счетчиков 6, сбрасывая их в исходное состояние (М-В,.).

С выхода элемента ИЛИ 13 единичный сигнал поступает также на вход одновибратора 17, который выдает на управляющий вход ключа 16 прямоуголь ный импульс,на время действия которого ключ 16 соединяет свой информационный вход с выходом. С выхода генератора 3 импульсы (частота их выбирается много большей частоты следования импульсов, выдаваемый формирователем 2 импульсов) проходят через ключ 16 на вход считывания регистра 18 и последовательно опрашивают ячейки его памяти; с ннформационного выхода регистра 18 все храня1196890

Составитель А.Шеренков

Редактор А,Шандор Техред JI,Ìàðòÿøoâà Корректор Е.Сирохман

Заказ 7566/49 Тираж 709 Подписное

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

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

Филиал ППП "Патент", г, Ужгород, ул, Проектная, 4 сумматора 5 и, следовательно, на его выход не проходят.Если на каждом шаге работы уст° ройства в дерево включается одна ветвь, то через К-1 шагов счетчик 14 выдает сигнал переполнения на вто- . рой S-вход триггера 15, единичный сигнал которого прекращает выдачу импульсов формирователем 2 импульсов. Поступление импульсов на соответствующие выходы устройства идентифицирует ветви оптимального дерева, суммарный вес которого определяется суммированием весов вошед,ших в дерево ветвей.

Если на том или ином шаге в дерево включаются две (или более) ветви, то эамлкание двух {или более)контактов 8 обуславливает за3 пись соответствующего числа единиц в ячейки памяти регистра 18. После их считывания счетчик 14 увеличивает

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