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

 

Изобретение относится к области вычислительной техники и может быть использовано при решении на извешенных графах задач нахождения оптимального дерева. Целью изобретения является повышение быстродействия устройства. Устройство содержит ,fB -т... j2L,i е i (Л

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

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

РЕСПУБЛИК (19) (11) А1 (sn 4 С 06 F 15/20--, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3840885/24-24 (22) 09.01.85 (46) 15.08.86. Бюл. Р 30 (72) 10.M.Коптев и M.М.Овчинников (53) 681. 333 (088. 8) (56) Авторское свидетельство СССР

N- 748428, кл. G 06 F 7/122„ 1978.

Авторское свидетельство СССР

9 732898, кл. G 06 Г 7/122, 1977. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО ДЕРЕВА ГРАФА (57) Изобретение относится к области вычислительной техники и может быть использовано при решении на извешенных графах задач нахождения оптимального дерева. Целью изобретения является повышение быстродействия устройства. Устройство содержит

1251100 модули l ветвей графа. (на чертеже показан случай наличия у графа четырех ветвей), коммутатор ?, блок 3 управления, генератор 4 импульсов, формирователь 5 импульсов. Каждая модель ветви графа содержит коммутатор б, сумматор 7 по модулю два, счетИзобретение относится к вычислительной технике и может быть исполь." зовано при решении на взвешенных графах задач нахождения оптимального дерева. 5

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

Устройство содержит модели 1 ветвей графа например четыре, коммутатор 2, блок 3 управления, генератор 4 импульсов и формирователь 5 импульсов. Каждая модель 1 ветви

I5 графа содержит коммутатор 6, сумматор 7 по модулю два, счетчик 8, формирователь 9 импульсов, ключ 10 и элемент ll индикации, Блок 3 управления содержит регистр 12 сдвига, де20 шифратор 13, счетчик 14 и элемент

ИЛИ 15. Входные и выходные полюса - каждой модели ветви обозначены цифрами 16-21.

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

Первоначально обнуляются сумматор 7 и регистр 12, в счетчик 14 заносится количество импульсов

К-С+1, где К вЂ” емкость счетчика;

С вЂ” число вершин графа (в котором дерево образует С-1 ветвей); в каждый счетчик 8 заносится количество импульсов, равное К-В, (В, — вес 35

i-й ветви) при определении минимального дерева и равное В; при определении дерева максимального веса.

При поступлении пускового сигна- 4а ла на вход устройства генератор 4 начинает выдавать импульсы, которые через второй выход коммутатора 2 и чик 8. формирователь 9 импульсов, ключ 10, элемент ll индикации, Блок управления содержит регистр 12 сдвига, дешифратор 13, счетчик 14, эле— мент ИЛИ 15, Входные и выходные полю са каждой модели ветви обозначены цифрами 16-21 соответственно. 1 ил. полюса 17 моделей ветвей. инцидентных первой вершине графа, поступают на первые входы соответствующих сумматоров 7. На вторые входы сумматоров импульсы не поступают, поэтому с выходов сумматоров 7 импульсы проходят на счетный вход счетчика 8. При переполнении счетчика 8 модели ветви, имеющей наименьший вес (в данном случае рассматривается нахождение дерева минимального веса, в счет;иках 8 занесены количества импульсов К-В1,), сигнал переполнения с его выхода поступает, во-первых, через полюс 18 на соответствующий выход устройства и тем самым идентифицирует ветвь, вошедшую в формируемое минимальное дерево, во-вторых, на управляющий вход коммутатора 6, который соединяет свой информационный вход с выходом, в-третьих, на входы формирователя 9 импульсов, который, в свою очередь, выдает импульс на информационный вход ключа 10 и соответствующие входы регистра 12 (который запоминает единицу в ячейке памяти) и дешифратора 13. При наличии на всех входах дешифратора 13 только одного единичного сигнала он выдает сигнал по первому выходу на установочный вход регистра 12, который обнупяется,,и на вход. элемента ИЛИ 15. С выхода злеэлемента ИЛИ 15 сигнал поступает на счетный вход счетчика 14 который увеличивает свои показания на 1, и на установочные входы счетчиков 8 всех моделей ветвей. В результате все счетчики 8, которые начали счет импульсов, сбрасываются в исходное состояние К-В;, за исключением переполнившихся счетчиков 8, которые остаются в состоянии переполнения до конца работы устройства. С выхода счетчиз 1251 ка 14 на управляющие вхздь ключей 10 поступает нулевой сигнал, позтому выданные формирователями 9 импульсов сигналы на выходы кЛючей 10 не проходят. Интервал следования импуль. сов с выхода генератора 4 выбирается таким, чтобы вышеуказанные процессы, обусловленные переполнением какого-либо счетчика 8 при поступлении

j-го импульса генератора 4, закончи- 30 лись.к моменту поступления (j+1)-ro импульса.

При дальнейшей работе устройства импульсы с второго выхода коммутатора 2 проходят на первые входы сумма- 13 торов 7 не только моделей ветвей, ин цндентных первой вершине, но и Моделей ветвей, полюса 17, которых соеди-.

° иены с вторым выходом коммутатора 2 через коммутаторы 6, соединившие снои30 информационные входы и выходы при поступлении сигналов на их управляющие входы., Коммутатор 6 обеспечивает „ двухстороннее прохождение сигналов: не только с информационного входа иа 5 выход, но и наоборот (тогда выход его становится информационным входом).

В ходе работы устройства по мере переполнения счетчиков 8 в формирующее» ся дерево включаются все новые и 30 новые ветви„ кроме ветвей, образующих циклы,. так как в таких ветвях импульсы поступают на оба входа сумматора

7 и, следовательно, на вход счетчика

8 не проходят, 33

Если ветви в дерево включаются по одной, то после отсчета C""1 импуль сов счетчиком 14 он выдает сигнал пареполнения, который поступает на вход останона генератора 4,,прекращая ра- 40 боту устройства, и на управляющие входы ключей 10, которые соединяют свои информационные входы с выходами. В результате импульс, выданный формирователем 9 импульсов модели ветви, включенной в дерево графа последней, проходит на дход элемента 11 индикации, который идентифицирует эту нетвь и одновременно сигнализирует об окончании работы устройства»

Ветви оптимального дерева опрадаля" ют по наличию потенциалов перапол кения счетчиков на сООтнатСтнуЮщ33М выходах устройства.

В случае переполнения одноэрамен Ф но двух (или более) счетчиков 8 с эи ходов еоответствующего числа форинро вателей 9 импульсов сигналы посту33а

100 4 ют на информационные входы регистра 12, который запоминает соответствующее число единиц в ячейках памяти, и на входы дешифратора 13. При наличии на входах более одного еди- нияного сигнала дешифратор 13 выдает сигнал по второму выходу на вход формирователя 5 импульсов, который вьщает импульс на управляющий вход коммутатора 2, и последний переключает свой. информационный вход на первый выход. В результате импульсы генератора 4 проходят на вход сдвига регистра 12, поочередно опрашивают его ячейки и считывают иа выход соответствующее число единиц.

Единичные сигналы с выхода регист-< ра 12 через второй вход элемента

ИЛИ 15 проходят, во-первых, на счетный вход счетчика 14 который увели" чивает свои показания на соответствующее число единиц, во-вторьк, йа установочные входы счетчиков 8, кото« рые ло первому сигналу сбрасычаются в исходное состояние Е-В; (за исключением параПолниваихся счетчиков) .

Длите33ьность импульса, выдаваемого формироэаталам 5 ю3пульсоэ, эыби рается такой, чтобы импульсы гамаратора 4 опросили эса ячайкм регистра 12» По oкоичанмм импульса на управляющем входа коммутатор 2 эмоэь соеднняат сэой информационный эход с вторым выходом н работа устройства продолжается.

Если э процесса счнтыэання адн» миц нэ регистра 12 пронаоало пара33елнанна счетчика 14, то снгнал пара33ел» камня поступает на упраэлявщна энеди ключей 10 н открыэаат мн, э раэультата 3еа ульсы эсен фер33нр33эателай

9 нмпулъсоэ иедалай эатэай, э33лвчен них э дараэо на 33есладнеи йа3»а 13абе ты устройства, 33ронедят череэ нювчн 10 на энеди элеиентеэ 1 1 ккд33на

ЦНН3 Мотала ннднцнру36т Этк эатвк Н эт3е3 енгмалнэпрувт е налкчкн в Графе дэун (33лн белее икнниальник де13евь аэ3 каэ3дее на нете13ин е613аэевайе эатэяин> внлвчекнвэ3н в дереве де 33ее ладмеге ma3a 13абети уетрейМва1 н

Маидей едней ветвьв ке чкела ветвей» внлвченнин на 33ееледкеи @а3 е» 613ииаР= йий аоо 633»3»кма33ьйе3»е д613ева меФе% бить е33ределек еуимкреваккеи веееэ ветвей3 венед@к33 в де=

13еве»

1251100

Составитель Т.Сапунова

Редактор И.Рыбченко Техред М.уоданич

Корректор С.Черни .

Заказ 4413/47 Тираж б71

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

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

Подписное

Производственно-полиграфическое предприятие, r.Óæãoðoä, ул.Проектная, 4 формула изобретения

Устройство для определения оптимального дерева графа, содержащее группу моделей ветвей графа, соединенных согласно топологии исследуемого графа, генератор импульсов, формирователь импульсов, блок управления, содержащий счетчик, каждая модель ветви графа также содержит счетчик, о т л и ч а ю щ е е с я тем, J что, с целью повышения быстродействия, в него введены коммутатор, в блок управления введены регистр сдви- I5 га, дешифратор, элемент ИЛИ, в каждую модель ветви графа введены коммутатор, сумматор по модулю два формирователь импульсов, элемент индикации, вход запуска генератора импуль- ро сов является входом запуска устрой- ства, а выход генератора импульсов подключен к информационному входу коммутатора, управляющий вход которого подключен к выходу формирова- 25 теля импульсов, первый выход коммутатора подключен к входу сдвига регистра сдвига, выход которого подключен к первому входу элемента ИЛИ, второй вход элемента ИЛИ и установоч-ЗО ный вход регистра сдвига объединены подключены к входу формирователя импульсов, выход элемента ИЛИ подключен к счетному входу счетчика блока управления и к установочным входам счетчиков моделей ветвей графа, выход счетчика блока управления подключен к входу останова генератора импульсов и к управляющим входам ключей моделей ветвей графа, второй выход коммутатора подключен к первым входам сумматоров по модулю два моде- . лей ветвей графа., инцидентных первой вершине графа, информационный вхсд и выход коммутатора каждой модели ветви графа подключены соответственно к первбму и Второму входам сумматора по модулю два, выход которого подключен к счетному входу счетчика модели ветви графа„ выход счетчика модели ветви графа подключен к управляюще/ му входу коммутатора модели ветви графа, к входу формирователя импульсов модели ветви графа и является соответствующим выходом устройства, вы ход формирователя импульсов модели ветви графа через ключ подключен к входу элемента индикации, информационные входы регистра сдвига соединены с одноименными входами дешифратора и подключены к выходам формирователей импульсов соответствующих моделей ветвей графа.