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

(я)5 6 06 ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ, В,М.Сыров, А.Б.Щербань идетельство СССР 06 6 7/122, 1980,идетельство СССР 06 6 7/122, 1988. О ДЛЯ ОПРЕДЕЛЕНИЯ ОПЕРЕВА СВЯЗНОСТИ ГРАФА(57) Изобретение относится к вычислительной технике и может быть использовано для аппаратной реализации алгоритма задачи определения кратчайшего остова графа, Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство для определения оптимального дерева связности графа содержит блок 1 моделирования графа, блок 2 выбора дуги, генератор 3 тактовых импульсов, ключ 4 и элемент ИЛИ - НЕ 5. 1 ил.Изобретение относится к вычислитель- входы моделей дуг, идидентных первой верной технике и может быть использовано для шине морелируемого графа - 6 ц, 1= 2,п.аппаратной реализации алгоритма задачи В каждой из этих моделей дуг импульсыопределения кратчайшего остова графа, яв- поступают на один из входов сумматоров поляющейся математической моделью широ модулю два 11, а с их выходов - на вычитакого класса прикладных задач, например, ющий вход счетчика 12, При поступлении Воптимизация схемы коммутации электриче- импульсов (В = вп(Кц на выходе индикаской сети, сети трубопроводов и др,ции нулевого состояния соответствующегоелью изобретения является сокраще 10 счетчика появляется сигнал уровня логичение аппар УР Рние аппа атурных затрат.Функциональная схема устройства при- ской единицы. Пусть, например, на первомшаге решения й = Кц = К 1, (т.е. Устройствоведена на фиг.1,Уст ойство содержит блокб 1 моделиро- допускает поступление сигнала о достижении нулевого состояния от нескольких счетвания графа, блок 2 выбора дуг, генераторэлемет 15 чиков одновРеменно), тогда сигналы стактовых импульсов 3, ключ и элементвыходов счетчиков 12 моделей дуг 6 ц и 61,лИЛИ - НЕ 5,Блок 1 моделирования графа предназ- через соответствующие элементы И 13, надругом входе которых присутствует сигналначен для задания топологии и весов дугисследуемого графа и содержит верхнюю высокого уровня с нулевого выхода триггера20 9, поступают на элемент ИЛИ 7 и входынаддиагональную матрицу иэ в=2 и п(п 1) элементов И 171,1, 171,п и элементов ИЛИ .моделей дуг 6;, 1 = 1,п - 1, ) = 1+1,п, элемент 191,ь 191,п блока 2 выбора, С выхода элеменИЛИ 7 и вход возврата устройства в исход- та ИЛИ 7 сигнал поступает на вход элементафа) Каждая мо- ИЛИ - НЕ 5 При этом снимается сигнал сное 8 п - число вершин графа . Каждая модель дуги содержит триггер, регистрер 9 регистр 10 25 Управляющего входа ключа 4, его информа 11 вычитающий ционная с цепь отсоединяет вход запускасумматор по модулю два, вычитающийсчетчик 12, элемент И, и ключ12, И 13, люч 14. генератора 3 от шины питания и генератор.прекращает выработку импульсов, С выхоБлок 2 выбора дуг предназначен длядов элементов ИЛИ 19 ц, 19 р сигнал постуопределения дуги, включаемой в оптимальное дерево связности на каждом шаге ра оаждом шаге рабо пает на входы всех схемно последующихэлементов ИЛИ 191 и инверсные входы элеты алгоритма и содержит генератородиночных импульсов, счетчик, пер 15 счетчик 16 пер- ментов И 171 поэтому сигнал уровня логивую группу и (в - 1)-го элемента( - 1)- о элемента И 17, ческой единицы поступает с выходаэлемент ИЛИ 18, группу из(в- )-го элеменИЛИ 18 из(в)-гоэлемен- элемента 17, на вход элемента ИЛИ 18 ир ппу из в элементов 35 вход элемента И 20,п, С выхода элемента 18альной установки веса дуг сигнал поступает на вход запуска генератора импульсов 16, который при этом вырабаИ 201 и полюс начальной установки веса дугтывает сигнал импульс, поступающий наПринцип работы устройства основан наопределении из дуг, нео разующих цикловд г необразующих циклов вход счетчика 16, объединенные входы элес ругами, включенными в оптимальный подю енными в оптимальный под 40 ментов И 2011 и считывающие входы регистров 10 всех моделей дуг. Содержимоедуги с минимальным весом и включении ее счетчика 16 уменьшится на единицу, инфорв решение на данном шаге. мация с регистров 10 вновь перезапишетсяением в регистры 1 0 моде . в соответствующие счетчики 12 и снимутсяПеред решением, в регистры модег осятся значения К 1 если Ц-тая 45 сигналы с выходов индикации нулевого сов есть в исследуемом графе и д/ если стояния счетчиков 12 моделеи дуг 6Ц- в моделируемом графе нет,К 1 - Одновременно сигнал с выхода элементаЦ-той дуги в моделируемом графе нет , 1 -вес Ц-той дуги, ЧЧК 11 - емкость регистра, а 201, поступает на единичный вход триггерасчетчик 16 блока 2 устанавливается в состо модели дУги 6 ц моделируя тем самымяние и, Далее, подачей импульса на полюси далее подачей импульса на полюс 50 включение 1,1-й дУги в оптимальное Реше 21 осуществляется перезапись содержимо- ние, С единичного выхода триггера 9 сигналго регистров 10 всоответствующие счетчики поступает на управляющий вход ключа 14,12 моделей дуг и перевод счетчика 16 в информационная цепь которого соединяетсостояние и- .с о ниеп. при этом входы сумматора по модулю дваРешение начинается подачей напряже модели дуги 6 ц и соединяет с выходом гения на шину питания, При этом напряжение нератора 3 соответствующие входы всех мос нее через замкнутую информационную делей дуг ицидентных 1-й вершине графа,цепь ключа 4 поступает на вход запуска Это исключает поступление импульсов нагенератора импульсов 3. С выхода генерато- счетчик 12 модели дуги 61,1 на последующихра импульсы постуа 3 импульсы поступают на обьединенные шагах решения и выбор дуги для включенияв решение на втором шаге из множества дуг входы к-й группы блока моделирования граицидентных первой и 1-й вершинам графа, фа подключены соответственно к выходамПосле снятия сигнала уровня логиче- к-й группы блока выбора дуг, выход блока ской единицы с входа элемента 5 вновь вход моделирования графа - к первому входу запуска генератора 3 соединяется инфор элемента ИЛИ - НЕ,выходкоторогоподклюмационной цепью ключа 4 с шиной питания чен к управляющему входу ключа, выход кои начинается второй шаг работы устройст- торого подключен к входу запуска-останова ва, который, как и последующие, будет ана- генератора тактовых импульсов, выход кологичен выше рассмотренному,. Заметим торого подключен к входу синхронизации только, если дуга из числа альтернативных 10 блока моделирования графа, выход блока на данном шаге решения может образовать выбора дуг подключен к второму входу злецикл с уже "включенными" дугами на пред- . мента ИЛИ - НЕ, вход единичного потенциашествующих шагах решения, то импульсы ла устройства - к информационному входу от генератора 3 будут поступать на оба вхо-. ключа, при этом блок выбора дуг содержит да ее сумматора по модулю два 11, что рав 2 Н групп элементов И, Н групп элементов нозначно исключению этой дуги из ИЛИ,элементИЛИ,счетчикигенератортакдальнейшего рассмотрения,товых импульсов, прй этом в блоке выбораРешение заканчивается, когда после . дуг первый информационный вход обьедивыработки очередного импульса генерато- нен с выходом генератора тактовых импульром одиночных импульсов 15 счетчик 16 пе сов с помощью схемы МОНТАЖНОЕ. ИЛИ и рейдет в нулевое состояние, что . подключен к входу декремента счетчика и к свидетельствует об определении (и - 1)-й ду- первым входам элементов И первой группы, ги, входящей в оптимальное дерево связно- выхбд признака нулевого результата счетчи-сти графа. При этом сигнал с выхода ка подключен к выходу блока выборадуг, индикации нулевого состояния счетчика 16 25 второй информационный вход которого поступает на соответствующие вход эле- подключен к информационномувходусчетмента ИЛИ - НЕ 5, исключая запуск генера- чика, выходы элементов И к-й группы подтора 3 после включения в решение ключены соответственно к выходам к-й последней (и - 1)-й дуги, Множество дуг, вхо-. группы блока выбора дуг, первый информадящих в оптимальное дерево связности гра ционный вход первой группы которого подфа, однозначно определяется ключен к первому (инверсному) входу перешедшими в единичное состояние триг- первого элемента И (Н+1)-й группы к первогерами 9 соответствующихмоделейдугбло- му входу первого элемента ИЛИ первой ка 1. группы, к второму входу первого элементаДля возврата схемы в исходное необхо И первой группы и к первому входу элемендимо подать сигнал уровня логической еди- та ИЛИ, выход которого подключен к входу ницы на полюс 8, блока 1, с которого он запуска-останова генератора тактовых импоступает на объединенные у всех моделей пульсов, в-й информационный вход первой дуг нулевые входы триггеров 9, группы блока выбора дуг (где в=2Н) подФ о р мул а из о бр ете н и я 40 ключен к второму входу(в)-го элемента И 1. Устройство для определения опти- (Н+1)-й группы и к первому входу (в)-го мального дерева связности графа, содержа- элемента ИЛИ группы, выход (в)-го элещее блок моделирования графа, причем мента И (Н+1)-й группы подключен к в-му вход установки в исходное состояние уст- . входу элемента ИЛИ и второму входу в-го ройства подключен к входу установки в ис элемента И первой группы, с-й информациходное состояние блока моделирования онный входр-й группы блока выборадуг(где графа, о т л и ч а ю щ е е с я тем, что, с целью р=2Н, с=1,.;.,Н-р+1) подключен к первому сокращения аппаратурных затрат, оно со- входу с-го элемента ИЛИ р-й группы и к держит блок выбора дуг, элемент ИЛИ - НЕ, первому входу с-го элемента И(Н+р)-й груп- ключ и генератор тактовых импульсов, при 50 пы, выход с-го элемента И (Н+р)-й группы этом вход веса дуг подключен к первому подключен к второму входу с-го элемента И . информационному входу блока выбора дуг р-й группы и к с-му входу (р)-й группы и к управляющему входу блока моделирова- элемента ИЛИ, выход б-го элемента ИЛИ ния графа, вход числа дуг графа устройства первой группы(где б=1 Н) подключен ко подключен к второму информационному 55 второму входу (б+1)-го элемента ИЛИ первходу блока выбора дуг, выходы к-й группы . вой группы и к второму (инверсному) входу блока моделирования графа (где к = 1Н, (б+1)-го элемента И (Н+1)-й группы, выход Н - число вершин графа) подключены соот-: д-го элемента ИЛИ р-й группы (где д=1,Н- ветственно к информационным входам к-й р+1) подключен к второму входу (д+1)-го группы блока выборадуг, информационные элемента ИЛИ р-й группы выход (Н-к)-го1817089 элемента ИЛИ к-й группы подключен к второму входу первого элемента ИЛИ (к+Г)- й группы и второму(инверсному) входу первого элемента И (Н+к+1)-й группы Составитель Г.СмирноваТехред М,Моргентал Корректор Л,Ливринц Редактор Т.Иванова Заказ 1723 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 52,Устройство поп.1,отл ича ющеес я тем, что блок моделирования графа содержит аерхнетреуговьную матрицу узлов моделированйя ду, при этом вход установки в исходное. состояние блока 10 подключен к входам установки в исходное состояние узлов моделирования дуг матрицы, управляющий вход блока - к первым управляющим входам узлов моделирования дуг матрицы, информационные входы к-й 15 группы блока - соответственно к информационных входам узлов моделирования дуг к-й строки матрицы, вход синхронизации . блока - к вторым управляющим входам узлов моделирования дуг первой строки мат рицы, первые выходы узлов моделирования дуга-го столбца(где а=1,.,Н) строк с первой по а-ю матрицы объединены с помощью схемы МОНТАЖНОЕ ИЛИ и подключены к вто-, рому управляющему входу узла 25 моделирования дуг (а+1)-.го столбца (а+1)-й строки матрицы, выходы узлов моделирования дуг а-й строки а-го столбца матрицы подключены соответственно к выходам а-й30 группы блока моделирования графа и входам а-й группы элемента ИЛИ, выход которого подключен к выходу блока моделирования графа, причем каждый узел моделирования дуг содержит триггер, ключ, регистр, счетчик, сумматор по модулю два и элемент И, при этом в каждом узле моделирования дуг первый управляющий вход, информационный вход и вход установки в исходное состояние узла моделирования дуг подключены соответственно к.входу синхронизации регистра, к входам установки в "1" и в "0" триггера, прямой выход которого подключен к информационному входу ключа, выход которого подключен к первому входу сумматора по модулю два и к первому выходу узла моделирования дуг, второй управляющий вход которого подключен к управляющему входу ключа и к второму входу сумматора по модулю два, выход которого подключен к входу декремента счетчика, выход признака нулевого результата которого подключен к первому входу элемента И, выход которого подключен к второму выходу узла моделирования дуг, инверсный выход триггера подключен к второму входу элемента И, выходы регистра подключены соответственно к информационным входам счетчика.