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

 

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

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

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

РЕСПУБЛИК (я)з G 06 F 7/48

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4797646/24 (22) 09.01.90 (46) 23.05.93, Бюл. № 19 (72) О.Г.Алексеев, В,M.Ñûðîâ, А.Б. Щербань и Н.И.Ячкула (56) Авторское свидетельство СССР

¹ 732898, кл. G 06 G 7/122, 1980.

Авторское свидетельство СССР № 1411782, кл. 6 06 G 7/122, 1988. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛ ЬНОГО ДЕРЕВА СВЯЗНОСТИ ГРАФА

„„Я2„„1817089 А1 (57) Изобретение относится к вычислительной технике и может быть использовано для аппаратной реализации алгоритма задачи определения кратчайшего остова графа, Цель изобретения — сокращение аппаратурных затрат. Поставленная цель достигается тем. что устройство для определения оптимального дерева связности графа содержит блок 1 моделирования графа, блок 2 выбора дуги, генератор 3 тактовых импульсов, ключ

4 и элемент ИЛИ вЂ” НЕ 5. 1 ил.

1817089

Изобретение относится к вычислитель- входы моделей дуг, идидентных первой верной технике и может быть использовано для шине моделируемого графа — 61,ь I = 2,п. аппаратной реализации алгоритма задачи В каждой из этих моделей дуг импульсы определения кратчайшего остова графа, яв- поступают на один из входов сумматоров по ляющейся математической моделью широ- 5 модулю два 11, а с их выходов — на вычитакого класса прикладных задач, например, ющий вход счетчика 12, При поступлении R оптимизация схемы коммутации электриче- импульсов (R = mIn(K>, на выходе индикаской сети, сети трубопроводов и др, i ции нулевого состояния соответствующего елью изобретения является сокраще10 счетчика появляется сигнал уровня логичение аппар ур р ние аппа атурных затрат.

Функциональная схема устройства при- ской единицы. Пусть, например, на первом

ШаГЕ РЕШЕНИЯ R = КЦ = К1,п (т.Е. УСтРОйСтВО ведена на фиг.1, Уст ойство содержит блок б 1 моделиро- допускает поступление сигнала о достижении нулевого состояния от нескольких счетвания графа, блок 2 выбора дуг, генератор элемент 15 чиков одновременно), тогда сигналы с тактовых импульсов 3, ключ и элемент выходов счетчиков 12 моделей дуг 6ц и 61 и

ИЛИ вЂ” НЕ 5, Блок 1 моделирования графа предназ- через соответствующие элементы И 13, на другом входе которых присутствует сигнал начен для задания топологии и весов дуг исследуемого графа и содержит верхнюю высокого уровня с нулевого выхода триггера

20 9, поступают на элемент ИЛИ 7 и входы наддиагональную матрицу из m=2 v n(n ") элементов И 1711, 171,п и элементов ИЛИ моделей дуг 6 = 1 и — 1 ) = !+ и элемент 191.ь191, блока 2 выбора. СвыходаэлеменИЛИ 7 и вход возврата устройства в исход- та ИЛИ 7 сигнал поступает на вход элемента фа) Ка, ая мо ИЛИ вЂ” НЕ 5. При этом снимается сигнал с ное 8 (и — число вершин графа . Каждая модель дуги содержит триггер, регистр ер 9 регистр 10 25 Управляющего входа ключа 4, его информа11 вычитающий ционная с,цепь отсоединяет вход запуска сумматор по модулю два, вычитающий счетчик 12, элемент И, и ключ

12, И 13, люч 14. генератора 3 от шины питания и генератор .прекращает выработку импульсов, С выхоБлок 2 выбора дуг предназначен для дов элементов ИЛИ 191.ь 191,п сигнал постуопределения дуги, включаемой в оптимальное дерево связности на каждом шаге ра оаждом шаге раpo- 30 пает на входы всех схемно последующих элементов ИЛИ 19iI и инверсные входы элеты алгоритма и содержит генератор одиночных импульсов, счетчик, персчетчик 16 пер ментов И 17Ц, поэтому сигнал уровня логивую группу и m — 1)-го элемента (1) о элемента И 17 ческой единицы постУпает с выхода элемент ИЛИ 18, группу из (гп- )-го элеменз,„1) го е е„элемента 17),п на вход элемента ИЛИ 18 и р ппу из и, элементов 35 вход элемента И 20>,п. С выхода элемента 18 альнои установки ВеСа дуг сигнал поступает на вход запуска генератора импульсов 16, который при этом вырабаИ 20я и полюс начальной установки веса дуг тывает сигнал импульс, поступающий на

Принцип работы устройства основан на определении из дуг, нео разующих циклов р „Heo6pä äö ä„циклов вход счетчика 16, объединенные входы элес дугами, включенными в оптимальный подю енными в оптимальный под- 40 ментов И 20II и считывающие входы регистров 10 всех моделей дуг. Содержимое дуги с минимальным весом и включении ее счетчика 16 уменьшится на единицу, инфорв решение на данном шаге. мация с регистров 10 вновь перезапишется ением в регистры 1 0 моде . в соответствующие счетчики 1 2 и снимутся

Перед решением, в регистры модег осятся значения Ки если Ц-тая 45 сигналы с выходов индикации нУлевого соа есть в исследуемом графе и g если стояния счетчиков 12 моделей дуг 61,ь 61,п.

Ц- - в моделируемом графе нет {Ки — Одновременно сигнал с выхода элемента

Ц-той дуги в моделируемом графе нет { )—

sec IJ-той дуги, щ»Кл — емкость регистра), а 20ц поступает на единичный вход триггера счетчик 16блока 2 устанавливается В состо- 9 модели дуги 6ц моделируя тем самым яние и, Далее, подачей импульса на полюс и далее подачей импульса на полюс 50 включение 1,!-й дуги в оптимальное реше21 осуществляется перезапись содержимо- ние, С единичного выхода тРиггеРа 9 сигнал

ro регистров 10в соответствующие счетчики постУпает на УпРавлЯющий вход ключа 14, 12 моделей дуг и перевод счетчика 16 в информационная цепь которОго соединяет состояние и- . с о ниеп-1. при этом входы сумматора по модулю два решение начинается подачей напряже- 55 модели дуги 6ц и соединяет с выходом гения на шину питания. При этом напряжение нератора 3 соответствующие входы всех мос нее через замкнутую информационную делей дуг ицидентных I-й вершине графа. цепь ключа 4 поступает на вход запуска Это исключает поступление импульсов на генератора импульсов 3, С выхода генерато- счетчик 12 модели дуги 61, на последуюших ра импульсы посту а 3 импульсы поступают на обьединенные шагах Решения и выбор дуги для включения

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

После снятия сигнала уровня логиче- к-й группы блока выбора дуг, выход блока ской единицы с входа элемента 5 вновь вход моделирования графа — к первому входу запуска генератора 3 соединяется инфор- 5 элемента ИЛИ вЂ” НЕ, выход которого подклюмационной цепью ключа 4 с шиной питания чен к управляющему входу ключа, выход кои начинается второй шаг работы устройст- торого подключен к входу запуска-останова ва, который, как и последующие, будет ана- генератора тактовых импульсов, выход кологичен выше рассмотренному,. Заметим торого подключен к входу синхронизации только, если дуга из числа альтернативных 10 блока моделирования графа, выход блока на данном шаге решения может образовать выбора дуг подключен к второму входу злецикл с уже "включенными" дугами на пред- . мента ИЛИ вЂ” НЕ, вход единичного потенциашествующих шагах решения, то импульсы ла устройства — к информационному входу от генератора 3 будут поступать на оба вхо- ключа, при этом блок выбора дуг содержит да ее сумматора по модулю два 11, что рав- 15 2Н групп элементов И, Н групп элементов н о з н а ч н о и с к л ю ч е н и ю этой ду г и из WIN, элемент ИЛИ, счетчик и генератор такдальнейшего рассмотрения. . товых импульсов, при этом в блоке выбора

Решение заканчивается, когда после . дуг первый информационный вход обьедивыработки очередного импульса генерато- нен с выходом генератора тактовых импульром одиночных импульсов 15 счетчик 16 пе- 20 сов с помощью схемы МОНТАЖНОЕ. ИЛИ и рейдет в нулевое состояние, что . подключен к входу декремента счетчика и к свидетельствует об определении (и — 1)-й ду- первым входам элементов И первой группы, ги, входящей в оптимальное дерево связно- выхбд признака нулевого результата счетчи- сти графа. При этом сигнал с выхода ка подключен к выходу блока выборадуг, индикации нулевого состояния счетчика 16 25 второй информационный вход которого поступает на соответствующие вход эле- подключен к информационномувходусчетмента ИЛИ вЂ” НЕ 5, исключая запуск генера- чика, выходы элементов И к-й группы подтора 3 после включения в решение ключены соответственно к выходам к-й последней (n — 1)-й дуги, Множество дуг, вхо- . группы блока выбора дуг, первый информадящих в оптимальное дерево связности гра- 30 ционный вход первой группы которого подфа, однозначно определяется ключен к первому (инверсному) входу перешедшими в единичное состояние триг- первого элемента И (Н+1)-й группы. к первогерами9соответствующихмоделейдугбло- му входу первого элемента ИЛИ первой ка 1. группы, к второму входу первого элемента

Для возврата схемы в исходное необхо- 35 И первой группы и к первому входу элемендимо подать сигнал уровня логической еди- та ИЛИ, выход которого подключен к входу ницы на полюс 8. блока 1, с которого он запуска-останова генератора тактовых импоступает на объединенные у всех моделей пульсов, в-й информационный вход первой дуг нулевые входы триггеров 9, группы блока выбора дуг (где в=2,...,Н) подФ о р м у л а и з о б р е т е н и я 40 ключен к второму входу (в-1)-го элемента И

1. Устройство для определения опти- (Н+1)-й группы и к первому входу (в-1)-го мального дерева связности графа, содержа- элемента ИЛИ группы, выход (в-1)-ro элещее блок моделирования графа, причем мента И (Н+1)-й группы подключен к в-му вход установки в исходное состояние уст- . входу элемента ИЛИ и второму входу в-ro ройства подключен к входу установки в ис- 45 элемента И первой группы, с-й информаци. ходное состояние блока моделирования онный вход р-й группы блока выбора дуг(где графа, о т л и ч а ю щ е е с я тем, что, с целью р=2,...,Н, с=1,.;.,Н-р+1) подключен к первому сокращения аппаратурных затрат, оно со- входу с-го элемента ИЛИ р-й группы и к держит блок выбора дуг, элемент ИЛИ вЂ” НЕ, первому входу с-го элемента N(H+p)-й групключ и генератор тактовых импульсов, при 50 пы, выход с-го элемента И (Н+р)-й группы этом вход веса дуг подключен к первому подключен к второму входу с-го элемента И . информационному входу блока выбора дуг р-й группы и к с-му входу (р-1)-й группы и к управляющему входу блока моделирова- элемента ИЛИ, выход б- го элемента ИЛИ ния графа, вход числа дуг графа устройства первой группы (где б=1„...Н-1) подключен ко подключен к второму информационному 55 второму входу (б+1)-го элемента ИЛИ первходу блока выбора дуг, выходы к-й группы . вой группы и к второму (инверсному) входу блока моделирования графа (где к = 1,...,Н, (б+1)-го элемента И (Н+1)-й группы, выход

H — число вершин графа) подключены соот-: д-го элемента ИЛИ р-й группы (где д=1,...,Нветственно к информационным входам к-й р+1) подключен к второму входу (д+1)-ro группы блока выборадуг, информационные элемента ИЛИ р-й группы выход (Н-к)-го

1817089 элемента ИЛИ к-й группы подключен к второму входу первого элемента ИЛИ (к+1)й группы и второму(инверсному) входу первого элемента И (Н+к+1)-й группы..

Составитель Г.Смирнова

Техред M,Ìoðãåíòàë Корректор Л,Ливринц

Редактор Т.Иванова

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

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

2. Устройство no n.1, от л и ч а ю ще ес я тем, что блок моделирования графа содержит аерхнетреугольную матрицу узлов моделиреванйя ду, при этом вход установки в исходное состояние блока 10 подключен к входам установки в исходное состояние узлов моделирования дуг матрицы, управляющий вход блока — к первым управляющим входам узлов моделирования дуг матрицы, информационные входы к-й 15 группы блока — соответственно к информационных входам узлов моделирования дуг к-й строки матрицы, вход синхронизации . блока — к вторым управляющим входам узлов моделирования дуг первой строки мат- 20 рицы, первые выходы узлов моделирования дуг а-го столбца (где a=1,. „, Í) строк с первой по а-ю матрицы объединены с помощью схемы МОНТАЖНОЕ ИЛИ и подключены к вто-, рому управляющему входу узла 25 моделирования дуг (а+1)-.ro столбца (а+1)-й строки матрицы, выходы узлов моделирования дуг а-й строки à-ro столбца матрицы подключены соответственно к выходам а-й

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

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

 

Похожие патенты:

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

Изобретение относится к вычислительной технике

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

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

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

Изобретение относится к моделированию системы труб

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

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

Изобретение относится к области вычислительной техники, а именно к вычислительным системам на основе микропроцессоров с блоками вещественной и специализированной комплексной арифметики, включающими в себя подблоки операции умножения с накоплением. Техническим результатом является ускорение процесса выполнения потока независимых команд «умножения с накоплением» при разрешенной исключительной ситуации «потеря точности». Устройство содержит подблок предсказания суммы мантисс, счетчик старших нулей суммы мантисс, регистры мантисс чисел, входные регистры экспонент чисел, счетчик младших нулей мантиссы слагаемого, подблок вычисления сдвига выравнивания и предсказания сдвига предварительной нормализации, компаратор ранней потери точности, счетчик младших нулей суммы мантисс, компаратор поздней потери точности. 5 ил., 1 табл.

Изобретение относится к средствам векторных вычислений деления/обращения удвоенной точности на вычислительных платформах с одним потоком команд и множеством потоков данных (SIMD). Технический результат заключается в увеличении производительности векторных вычислений. Множество SIMD-полос предназначены для обработки одного элемента из множества данных, сохраненных в памяти, в соответствии с SIMD-инструкцией. Масштабируют множество аргументов для генерирования множества соответствующих масштабированных аргументов. Перемножают множество масштабированных аргументов для генерирования первого значения. Масштабируют порядковую часть и мантиссовую часть первого значения из множества значений данных для соответственного генерирования второго значения и третьего значения. Обращают второе значение и третье значение для соответственного генерирования четвертого значения и пятого значения. Перемножают четвертое значение и пятое значение для генерирования обратной версии первого значения. 3 н. и 14 з.п. ф-лы, 7 ил.

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

Изобретение относится к логическим преобразователям. Технический результат заключается в расширении арсенала технических средств для реализации простых симметричных булевых функций. Указанный результат достигается за счет того, что логический преобразователь содержит восемь мажоритарных элементов, которые имеют по три входа, причем выход i-гo и первые входы третьего, пятого, шестого мажоритарных элементов соединены соответственно с вторым входом (i+1)-го мажоритарного элемента и первым настроечным входом логического преобразователя, отличающийся тем, что в него введен девятый мажоритарный элемент, выход j-го и выход m-го мажоритарных элементов соединены соответственно с вторым входом (j+1)-го и третьим входом (3×m+2)-го мажоритарных элементов, а второй, третий входы и выход девятого мажоритарного элемента подключены соответственно к выходам пятого, восьмого мажоритарных элементов и выходу логического преобразователя, второй и первый настроечные входы которого соединены соответственно с первым входом девятого и первыми входами четвертого, седьмого, восьмого мажоритарных элементов. 1 ил.
Наверх