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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для аппаратной реализации алгоритма задачи определения кратчайшего остова графа. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем. что устройство для определения оптимального дерева связности графа содержит блок 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" триггера, прямой выход которого подключен к информационному входу ключа, выход которого подключен к первому входу сумматора по модулю два и к первому выходу узла моделирования дуг, второй управляющий вход которого подключен к управляющему входу ключа и к второму входу сумматора по модулю два, выход которого подключен к входу декремента счетчика, выход признака нулевого результата которого подключен к первому входу элемента И, выход которого подключен к второму выходу узла моделирования дуг, инверсный выход триггера подключен к второму входу элемента И, выходы регистра подключены соответственно к информационным входам счетчика.