Устройство для нахождения оптимального дерева графа Советский патент 1985 года по МПК G06F15/173 

«

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

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

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

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

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

В исходном положении регистр 18 обнулен, триггер 15 находится в единичном состоянии (цепи установки в исходное состояние на чертеже не показаны). Наличие единичного потенциала на входе формирователя 2 импульсов запрещает выдачу импульсов на выход. В счетчики 6 заносят количество импульсов,пропорциональное весу ветвей - при определении дерева максимального веса, и равное М-В. (М емкость счетчика, В. - вес i-й ветви) - при определении дерева мини- мгшьного веса, В графе с К вершинами дерево образует К-1 ветвей, поэтому в счетчик 14 заносят количество импульсов М-К+1,

При поступлении сигнала с входа устройства на первый R-вкод триггера 15 нулевой сигнал с его выхода поступает на вход формирователя 2 импульсов и разрешает выдачу импульсов на первые входы сумматоров 5 моделей ветвей, идентичных начальной вершине графа. Так как на вторые входы cyi iaTopoB 5 импульсы не поступают, то с выхода сумматоров 5 импульсы поступают на счетные входь счетчиков 6, Будем рассматривать задачу нахождения дерева минимального веса; тогда первым переполняется счетчик 6 ветви наименьшего веса и выдает импульс переполнения на обмотку реле 7. Оно срабатывает, самоблокируется до конца работы уст968902

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

10 на первый S-вход триггера 15, который выдает единичный сигнал на вход формирователя 2 импульсов и запрещает выдачу им импульсов на выход, а также на установочные входы

J5 счетчиков 6, сбрасывая их в исходное состояние (М-В.),

С выхода элемента ИЛИ 13 единичный сигнал поступает также на вход одновибратора 17, который вьщает на

20 управляющий вход ключа 16 прямоугольный импульс,на время действия которого ключ 16 соединяет свой информационный вход с выходом, С выхода генератора 3 импульсы (частота их выбирается много большей частоты следования импульсов, выдаваемый формирователем 2 импульсов) проходят через ключ 16 на вход считывания регистра 18 и последовательно опрашивают ячейки его памяти; с информаци30онного выхода регистра 18 все хранящиеся единицы поступают на счетный вход счетчика 14, который соответственно увеличивает свои показания,

I

35

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

сумматоров 5 которых оказались подключенными к выходу формирователя импульсов 2 через замкнутый контакт 8 модели ветви, включенный в оптимальное дерево на первом шаге

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

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

сумматора 5 и, следовательно, на его выход не проходят.

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

деляется суммированием весов вошед.ших в дерево ветвей.

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

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