Устройство для определения кратчайших путей на графе

 

ОП ИСАНИ Е

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

+ .I1jpe.

gj

Зависимое от авт. свидетельства ¹â€”

Заявлено 24.1.1969 (№ 1300141у18-24) 1хл. 42гп", 7, 48 с присоединением заявки ¹â€”

Комитет по делам, ) 1!!К С) 06g 7/48

У3,К 681.333(088.8) Приоритет—

Опубликовано ОЗ.Х11.1970. Бюллетень X 36

Дата опубликования описания 26.111.19 1 изобретений и открытий при Совете Министров

СССР

Автор изобретения

П. М. Рыбаков

Таганрогский радиотехнический институт

Заявитель

УСТРОЙСТВО ДЛЯ ОП РЕДЕЛ ЕН ИЯ КРАТЧАЙ Ш ИХ

ПУТЕЙ НА ГРАФЕ

Изобретение .>тносится к аналоговой вычислительной тех;)и e.

Из вестно устройство для определения кратчайших путей на графе, содержащее мо..)ели узлов и ветзей с логическими схемами

«НЕТ», «ИЛИ» и а:)ержк)и.

Известное устр йство сложно ко:)структивно и в нем «I груднена перекоммутация графа из-за необходимости коммутаци; четь, рех проводггиков.

Предложенное устройство отличается тем, что IB нем в кажлуlI.I..!eæàùåé модели смежного "зла, со втсpt.l!1 Ilходом-вьгходом. Сигнальный вход четвертой схемы «НЕТ» соединен со вторым входом-вь ходом модели ветви. а выход — с запрсщ;.кипим входом третьей схемы

«НЕТ» и через цс lü задержки — со входом второй схемы «Н Е I », выход которой соединен со схемой упоряд) !i. )ной выборки номеров ветвей кратчайгп го пути, с запрещающим входом пемз,эй схемы «HFl » и через диод .)аспределенгиой схемы «1 IЛИ» — с первым

3xo3ом-выходом модели ветви. Это позволяет упростить устройство, улучшить помехозащищенность, по.ъ)сить скорость il надежность

BI)ЧИСЛЕИ)) й.

На фиг. 1 локазàl.à ."хема модели узла

;)редлагаемого устройства: на фиг. 2 — схема модели ветви.

Каждая модель узла !см. фиг, 1) содержит триггер 1 начального угла, схему «II» 2, триггер > консчного узла, часть распределенной схемы 4 «I IЛИ», другие элементы которой находятся в моделях ветвей, и наборное по15 ле т. Один ))з входов схемы «ИЛИ» 4 соединен с единичным выходом триггера 1. Последний устанавливается в;)улевое состояние го входу», 6 если узел не является начальных, и в единичное состояние (по входу 7), если

;)=комый узел —:.)ачальный Триггер > коне... Ого узла сл ж ит для воз оуждсния узл а в а- естве коне:1:-)ого. Сигналы по входам 8 и устанавливают его соответственно в нулевое и единичное состояние. Выход т!зиггера 3 согди te;1 с Од:-1:)м из входов схемы «И» 2, лругой вход которой соед)пиен со схемой 10, выраоатывающей сигналы выборки номеров ветвей кратчайшего пути. Выходы схемы «И» > соединен через конденсатор 11 с выходом распредел)ггельной схемы «ИЛИ» 4.

288424

10 (5

Каждая модель ветви может быть разбита ца две 1астп 12 и 18. Первая из них представляет собой схему для фиксации направления прохождения фронта волны, а вторая— схему для упорядоченной выборки ветвей кратчайшего пути, Модель имеет два входаHbIxoJà 14 и 15, каждый из которых в зависимости от условий может работать как вход илп как выход. Диоды 16 и 17 являются составными частями распределенных схем

«ИЛИ», находящихся в узлах. Схема для фиксации направления прохождения фронта волны (участка кратчайшего дерева) имеет на каждом входе-выходе IIQ две потенциальные схемы «НЕТ» 18, 19 и 20, 21, сигнальный вход одной из которых соединен со .входомвыходом 14 модели ветви, и вьвход — с запрещающим нходом другой, со входом схемь:

«ИЛИ» 22 и со входом одной 113 двуx схем

«И» 28,или 24. Сигнальный же вход другой схемы «НЕТ» соединен с выходом другой схемы «И», а выход — с запрещающим входом первой схемы «НЕТ» и со входом распределитель ной схемы «ИЛИ», часть которой находится в модели узла. Кроме того, выход сxe»bI «ИЛИ» 22 соединен со входом управляющей цепи задержки 25, выход которой соединен со входами схем «И» 28 H 24.

Схема упорядоченной выборки номеров ветвей кратчайшего пути состоит из четырех схем «И» 26 — 29, триггера 80 фиксации выборки, ветви, схемы «ИЛИ» 81 с дифферепцирующсй цепочкой и двух разделительных конденсаторов 32 и 88. Одни входы каждой пз двух схем «И» 26 и 27 соединены с выходами схем «НЕТ» 19 и 21, другие же входы— с выходом 84 схемы управления выборкой и с тр1 ггером 80 фиксации выбор ки, а BI!Ixoдь1 — через конденсаторы — co входамивыходами модели ветви. Одни входы другой пары схем «И» 28 и 29 соединены с выходами характеристик направления прохо>кдения фронта волны, другие — через конденсаторы

32 и 88 — со входами-выходами 14 и 15 модели ветви, а выходы — со входами схемы

:И. (И» 81 с дпфференцирующей цепочкой на выходе. Выход этой схемы соединен с единичным входом трпгтера 80, выдающего только один раз сигнал 85 наличия данной ветви в кратчайшем пути.

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

В набранном графе произвольной конфигурации называется, начальный узел. В результате триггер 1 этого узла перебрасывается в единичное со стояние, и иа выходе распределенной схемы «ИЛИ» 4 появляется сигнал «1». >тот сигнал поступает на один из входов смежной этому узлу ветви (например.

14) и проходит через схему «НЕТ» 18. Так как на управляющий вход этой схемы подается сигнал «0», то первая ха ра1ктеристика ветви равна нулю. Единичный сигнал с выхода схемы «НЕТ» 18 закрывает схему «HFT» 19.

Кроме того, оц поступает на вход схемы «И»

24 и проходит через схему «ИЛИ» 22 на вход управляющей цепи задержки 25. Задержанный единичный сигнал поступает на зходы схем «И» 28 и 24,,но нроходит только через схему «И» 24, так как эта схема была paIIee подготовлена по другому входу, и поступает ,на вход схемы «НЕТ» 21. Если со второго входа-выхода 15 единичный сигнал в это время не поступает, на выходе схемы «НЕТ» 21 появляется «1», Это значит, что вторая характеристика ветви в отличие от первой рав1а единице. С выхода этой схемы е пшичный сигнал поступает на вход распределенной схемы «ИЛИ» следующего узла и возбуждает его.

При поступлении е III«III«IIoI o сигнала нз вход-выход 15 модели ветви и отсутствии возоуждвния Ilo входу- IBIxo3% 14 происходя аналогичные дейст1вия, но характеристики ветви становятся обратными первым.

При появлении единичных сигналов на

o()o Ix входах-выходах со сдвигом,Bo времени, меньшим времени задержки управляющей цепи задержки, схемы «НЕТ» 19 и 21 закрь1ваются входными сигналами, и характеристика направления оказывается разной «О вЂ” 0». .Это значит, что данная ветвь 11е входит в кратчайшее дерево.

В результате такого процесс; возбужд;ются Всс узлы, и характеристики ветвей устанавлиBBIoòñÿ в соответствии с пpoxождениеA. сигнала по ветвям. Ветви, характеристик;1 прохождения сигнала по которым отлича1отся от «О — 0», образуют кратчайшее дсрево.

Основываясь на характеристиках IIpOxo>Kдеция сигнала через ветви, легко организовать индикацию направления прохо>кдения сигнала, а в итоге — индикацию кратчайшего дерева. Однако для решения ряда задач необходимо иметь номера ветвей, входящих в кратчайший путь. С этой целью возбу>кдают тр иггер 8 конечного узла, выходной сигнал которого готовит к открытию схему «И» 2.

Сигнал .выборки номера первой QT конечного узла ветви проходит только через схему «И»

2 конечного узла ца выход распределенной схем1. «ИЛИ» 4.

Так как сигнал выборки номеров ветвей кратчайшего .пути п редставляет собой импульс отрицательной полярности, то он проходит не через диоды раси(>еделенцой схемы

«ИЛИ» 4 и через схемы «НЕТ» ветви, а через конденсато р 82 или 88 — на вход схемы «И»

28 или 29. Если характеристика прохо>кдения сигнала равна единице, на выходе схемы «И»

28 или 29 появляется сигнал, который. пройдя через схему «ИЛИ» >1, устанавливает от заднего фронта импульса выоорки номера ветви триггеров 80 в единичное состояние, и с B Iхода этого триггера поступа ет сигнал о наличии этой ветви в кратчайшем пути. Если же характеристика прохождения сигнала равна нулю, на выходе схемы «И» единица не появляется, и тригге|р 80 остается,в состоянии

«0». Для подготовки к выоорке следующей

288424 )

50 ветви кратчайшего пути схемы «И» 26 и 27 готовятс51 к Открытию.

Очередной импульс выборки номера ветви, пройдя через олпу из схем «И» 26 и 27, lloступает через конденсатор на второй Вхо;1-выход ветви, выбранной на предыдущем шаге, на выход распределенной схемы «ИЛИ» 4 и на

Bxo;I-выход следующей ветви кратчайшего пути, выполняя там такие же действия, как и в рассмотренной. Если ветвь, выбранная на предыдущем шаге, является последней в кратчайшем .пути, То очередной импульс выборки llоступает через схему «И» 26 и 27 и конденсатор 82 или 88 на выход распределенной схемы

«ИЛИ» начального узла и далее в другие вст11и, но не может перебросить триггер 80, так как характеристики прохождения смежны:

11ачяльному узлу ветвей ра|вны «О — О».

Во время выборки номера и-ой ветви кратчайшего пути Во всех предыдущих ветвях импульсы выборки проходят через схемы «И» 23 и 29 на слиничные входы триггеров 30, но с выходов триггеров сигналы не поступают, тя., как они уже находятся в состоянии «1».

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

I-:овом конечном узле, Это значит, что при том же начальном узле незачем снова искать кратчайшее дерево — достаточно восстановить в начальное состояние схемы выборки номеров ветвей кратчайшего пути путем сброса в «О» по входу 86 всех триггеров 80 и осуществить упорялочеш1ую выборку номеров ветвей пр.. другом конечном узле, Это существенно ускоряет работу устройства, Если номер начального узла изменяет я поиск оптимального пути неоîxoäèмо на шнять с нахождения кратчайшего дерева.

Для этого триггер начаablloro узла устанавливают в нулевое состояние, Ня вь1хол распределенной схемы «ИЛИ» ня 1яльного узла появляется нулевой .потенциал, который

1ялеc практически мгновенно устанавливается во всех узлах и ветвях.

Схемы «И» 23 и 24 служат для ус!xopcIIIIB восстановления всего устройства в начальное состояние после установки «О» триггера начального узла.

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

В описанной схеме фиксации направления прохождения фронта волны имеется только одна цепь задержки, и поэтому модель отображает гриф с одинаковыми задержками В Обоllx направлениях ветви. Для моделирования графа с разными задержками в разных направления ветвей схему «ИЛИ» 22, выбрасывают, но вставляют вторую цепь задержки.

При этом выход схемы «НЕТ» 18 соединяют со входами схемы «II» 24 и второй цепи задержки, выход которой соединяют со вторым вхолом схемы «И» 24. Выход же схемы «И» соединяют со входом схемы «НЕТ» 21. ЛналоrlI lIIbl» образом включают первую цепь заJepiKI II II схем i «И» 28 Kleig jl вь1ходями cxebl

«Н Е Т» 21 «19.

Прс лмет изоор етения

Устройство для определения кратчайших путей ня графе, содержащее модели узлов ll ветвей с логическими схемами «НЕТ», «ИЛИ» и зялержки, оТ.ø÷àþùååñÿ тем, ITo, с целью упрощения устройства, увеличел1ия его возможностей, скорости и надежности вычислений, в нем в каждую из моделей ветви вклкчены потенциальные схемы «НЕТ», сигнальны I вход одной II3 которых соелинен с первым вхолом-выходом модели ветви, а выход — с запрещающим входом другой и через цепь за-,ержки — co входом третьей схемы «НЕТ», выход которои соединен со схемой упорядоченной выборки номеров ветвей кратчайшего пути, с запрещающим, входом четвертой схемы

«НЕТ» и через диод распределенной cxciil»I

«11ЛИ», принадлежащей модели смежного узла. — со вторым входом-выходом; кроме того, с11гняльный вход четвертой схемы «НЕТ» соединен со вторым входом-выходом модели ветви. а вь1ход — с запрещающим входом третьей схемы «НЕТ» и через цепь задержки — со вхолом второй схемы «НЕТ», выхол которой соединен со схемой упорядоченной выборки номеров ветвей кратчайшего пути, с запрещающим Bxолом первой схемы «НЕТ» и через диод распределенной схемы «ИЛИ» с первым входом-выходом молели ветви.

288424 и

75 юг 2

: и авитель E. ТимОхине

Тех р ед T. П. Курил ко

Корректс H. П. Бронскан

Редактор Б. Б. Федотов

:Заказ .Р2/282 Тираж 480 П дписно

LlIIIIl!HH Комитета по делам зоорстений и открытий при Совете Министров СССР

Москза, fK-35, Рауьвская aan... 4 5

Тип..ваньк фил. пред.;<.Пате нт»

Г

32

| !

1 !

| !

1 тз! !

I ! !

1 ! !