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

ОП ИСАНИ ЕИЗОБРЕТЕН ИЯК АВв ОРСКОМУ СВИДНЕЛЬСТВУ Союз Советских Социалистических РеспубликЭ1/ Зависимое от авт. свидетельства хе -1300141)18-24 Заявлено 241 хсл. 42 тп",с присоединением заявки Ъ Комитет по делам забретений и открытий при Совете Министров СССР1 НК С) 06 о 7/48 риори летець х:с 36 Опубликовано ОЗ.Х 11.1970 681.333(088.8 а опубликования описания 26.11.197 Авторизобретения Рыбако анрогский радиотехнический институт Заявитель УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕопрелелецис ержашее мо ими схемам) ОКсЗЗацс 1 СХЕМ Вмст 1 О)ствс); на Изобретение,тцосится к аналоговой Вы.числительной тех;ике,Известно устс нйство дл я1кратчайших путей ца графе, содлели узлов и ветзей с логическНЕТ, ИЛИ и а:ержк)и.Известное устр йство сложно ко;)структивно и В нем знгруднена перекохмутацияграфа из-за необходимости коммутанц; четьрех проводников.Предложенное устройство отличается тем,что в нем в кажлуи из моделей ветви включены потенциаль ье схемы НЕТ, сигнальный вход одной гз которых соедине:1 " первым входом-выходок модели Ветви, а выхол -с запрещаОших )ходом другой и через цепьзадержки - со входом третьей схемы НЕТ,выхол которой соединен со схемой упорядоченной выборк)1;1;еров ветвей кратчайшегопути, с запрешачц)Нм входом чствертой схеМЫ НЕТ И Чсреэ ЛИОд раСПрЕдЕЛЕННОй СХЕмы ИЛИ, лри:)нлчежащей молели смежного "зла, со втс ры и входом-вьгходом. Сц;1 альцый вход четвертой схемы НЕТ соелн ен совторым вхолох)-Вь холов модели ветви, а выход - с запрсшнОН)м входом третьей схемыНЕТ и через )с ь задержки - со входомвторой схемы НЕТ, выход которой соелиненсо схемой упоря )очс )ной выборки номеровВЕтВЕй КРатс)аИ;) ГО ПУТИ, С ЗаПРЕШаЮЩИМ вхолох НерзО 1 схемы НЕТ и через лцол )аспределенцоц схемы 11 ЛИ - с первым вхолом-выходом модели ветви. Это позволяет упростить устройство, улучшить помехозащи щенность, повысить скорость и належностьВЬ)ЧЦСЛЕЦ) й.На фцг. 1 л х)оз,сл и зл а;реллагаемого фцг, 2 - схема модели ветви.Каждая модель узла (сч. фиг, 1) содержиттриггер 1 начального угла, схему 1 2, триггер О конечного узла, часть распределенной схемы 4 11 ЛИ, лругие элементы которой нахолятся в моделях ветвец, ц наборное поле О. Олин )3 вколов схемы ИЛИ 4 соединен с единичным выходом триггера 1. Послелний устанавливается в;улевое состояние ГО ВХОДУ, 6 ЕСЛИ УЗЕЛ НЕ ЯВЛЯЕТСЯ НаЧВЛЬНЫ с, и в единичное состояние (по входу 7), если 20;1:комый узел - :ачальцый. Триггерконе.- Огэ узла служит лля Возоужлсння уз,1 а В ка)естВе 1,Оне:1:1 ОГО. Сигналы по Входах) 8 цустанавливают его соответственно в нулевое и единичное состояние. Выход триггерасоглинец с Ол:1:м цз вколов схемы И 2, другой вход которой соелцнен со схемой 10, вырабатывающей сигналы выбора номеров ветвей кратчайшего пути. Выхолы схемы Исоединен через конденсатор 11 с выхолом зо 1 аспрелелнтельно) схемы 1 Лс 4.5 10 15 20 25 30 35 40 45 50 55 60 65 Каждая модель ветви может быть разбита ца две части 12 и 13, Первая из них представляет собой схему для фиксации направления прохождения фронта волны, а вторая - схему для упорядоченной выборки ветвей кратчайшего пути, Модель имеет два входа- выхода 14 и 15, каждый из которых в зависимости от условий может работать как вход илп как выход. Диоды 16 и 17 являются составными частями распределенных схем ИЛИ, находящихся в узлах. Схема для фиксации направления прохождения фронта волны (участка кратчайшего дерева) имеет на каждом входе-выходе по две потенциальные схемы НЕТ 18, 19 и 20, 21, сигнальный вход одной из которых соединен со входом- выходом 14 модели ветви, и выход - с запрещающим нходом другой, со входом схемь; ИЛИ 22 и со входом одной нз двух схем И 23,илп 24. Сигнальный же вход другой схемы НЕТ соединен с выходом другой схемы И, а выход - с запрещающим входом первой схемы НЕТ и со входом распределительной схемы ИЛИ, часть которой находится в модели узла. Кроме того, выход схемы ИЛИ 22 соединен со входом управляющей цепи задержки 25, выход которой соединен со входами схем И 23 и 24.Схема упорядоченной выборки номеров ветвей кратчайшего пути состоит из четырех схем И 26 - 29, триггера 30 фиксации выборки, ветви, схемы ИЛИ 31 с диффереццирующсй цепочкой и двух разделительных конденсаторов 32 и 33. Одни входы каждой пз двух схем И 26 и 27 соединены с выходами схем НЕТ 19 и 21, другие же входы - с выходом 34 схемы управления выборкой и с триггером Ю фиксации выборки, а выходы - через конденсаторы - со входами- выходами модели ветви. Одни входы другой пары схем И 28 и 29 соединены с выхо амп характеристик направления прохождения фронта волны, другие - через конденсаторы 32 и 33 - со входами-выходами 14 и 15 модели ветви, а выходы - со входами схемыИ;1 И 31 с дпфференцирующей цепочкой на выходе. Выход этой схемы соединен с единичным входом триггера 30, выдающего только олин раз сигнал 35 наличия данной ветви в кратчайшем пути.Устройство работает следующим образом В цабранном графе произвольной конфигурации называется, начальный узел, В результате триггер 1 этого узла перебрасывается в единичное состояние, и иа выходе распределенной схемы ИЛИ 4 появляется сигнал 1, Этот сигнал поступает на один из вколов смежной этому узлу ветви 1 цапример.14) и проходит через схему НЕТ 18. Так как на управляющий вход этой схемы подается сигнал 0, то первая характеристика ветви равна нулю. Единичный сигнал с выхода схемы НЕТ 18 закрывает схему НЕТ 19. Кроме того, оц поступает на вход схемы И 24 и проходит через схему ИЛИ 22 на вход управляющей цепи задержки 25. Задержанный единичный сигнал поступает ца зходы схем И 23 и 24 но нроходит только через схему И 24, так как эта схема была ранее подготовлена по другому входу, и поступает ,на вход схемы НЕТ 21. Если со второго входа-выхода 15 единичный сигнал в это время не поступает, на выходе схемы НЕТ 21 появляемся 1. Это значит, что вторая характеристика ветви в отличие от первой рав и единице, С выхода этой схемы е пшичный сигнал поступает на вход распределенной схемы ИЛИ следующего узла и возбуждает его.При поступлении единичного сигнала цз вход-выход 15 модели ветви и отсутствии возбуждения по входу-выходу 14 происходят аналогичные дейспвия, но характеристики ветви становятся обратными первым.При появлении единичных сигналов ца оооцх входах-выходах со сдвигом,во времени, меньшим времени задержки управляющей цепи задержки, схемы НЕТ 19 и 21 закрываются входными сигналами, и характеристика направления оказывается разной О - 0. .Это значит, что данная ветвь це входит в кратчайшее дерево.В результате такого процесс; возбужд;- ются все узлы, и характеристики ветвей устанавливаются в соответствии с прохождением сигнала по ветвям. Ветви, характеристики прохождения сигнала по которым отличаются от О - 0, образуют кратчайшее дерево,Основываясь на характеристиках прохождения сигнала через ветви, легко организовать индикацию направления прохождения сигнала, а в итоге - индикацию кратчайшего дерева. Однако для решения ряда задач необходимо иметь номера ветвей, входящих в кратчайший путь. С этой целью возбуждают триггер 3 конечного узла, выходной сигнал которого готовит к открытию схему И 2. Сигнал выборки номера первой от конечного узла ветви проходит только через схему И 2 конечного узла на выход распределенной схемы ИЛИ 4.Так как сигнал выборки номеров ветвей кратчайшего, пути представляет собой импульс отрицательной полярности, то оц проходит не через диоды распределенной схемь ИЛИ 4 и через схемы НЕТ ветви, а через коцдецсатор 32 или 33 - на вход схемы И 28 или 29. Если характеристика прохождения сигнала равна единице, на выходе схемы И 28 или 29 появляется сигнал, который, пройдя через схему ИЛИ И, устанавливает от заднего фронта импульса выоорки номера ветви триггеров 30 в единичное состояние, и с выхода этого триггера поступает сигнал о наличии этой ветви в кратчайшем пути. Если же характеристика прохождения сигнала равна нулю, на выходе схемы И единица не появ. ляется, и триггер 30 остается,в состоянии 0. Для подготовкц к выоорке следующец10 15 20 30 35 40 45 50 ветви кратчайшего пути схемы И 26 и 27 готовятся к открытию.Очередной импульс выборки номера ветви, пройдя через одну из схем И 26 и 27, поступает через конденсатор на второй вход-выход ветви, выбранной на предыдущем шаге, на выход распределенной схемы ИЛИ 4 и ца вход-выход следующей ветви кратчайшего пути, выполняя там такие же действия, как и в рассмотренной. Если ветвь, выбранная на предыдущем шаге, является последней в кратчайшем пути, то очередной импульс выборки поступает через схему И 26 и 27 и конденс- тор 32 или 33 на выход распределенной схемы ИЛИ начального узла и далее в другие ветви, но не может перебросить триггер 30, так как характеристики прохождения смежных начальному узлу ветвей равны О - О.Во время выборки номера ц-ой ветви кратчайшего пути во всех предыдуших ветвях импульсы выборки проходят через схемы И 23 ц 29 на единичные входы триггеров 30, но с выходов триггеров сигналы не поступают, тя., как они уже находятся в состоянии 1.Если надо найти кратчайший путь между тем жс начальным узлом и другим конечным, сбрасывают триггер конечного узла, все триггеры в моделях ветвей, устанавливают новый конечный узел и выбирают номера ветвей прц новом конечном узле, Это значит, что при том же начальнохг узле незачем снова искать кратчайшее дерево - достаточно восстановить в начальное состояние схемы выборки номеров ветвей кратчайшего пути путем сброса в О по входу 36 всех триггеров 30 и осупгествить упорядочешгую выборку номеров ветвец цр другом конечном узле. Это существенно ускоряет работу устройства,Если номер начального узла изменяется поиск оптимального пути неооходимо начинать с нахождения кратчайшего дерева.Для этого триггер начального узла устанавливают в нулевое состояние, На вьгход распределенной схемы ИЛИ начального уз. ла появляется нулевой потенциал, который далее практически хггновецно устанавливается во всех узлах и ветвях,Схемы И 23 и 24 служат для ускорения восстановления всего устройства в начальное состояние после устаиовки О триггера цачальцого узла.Предложенное устройство может находить кратчайший путь не только между парой узлов, цо ц между группой узлов, объединенных в начальный узел, и группой узлов, оо.ьедцненных в конечный узел. Укрупненный узел получают путем электрического соединения выходов распределительных схем 1 ПИ входягцих в него узлов, Для возоуждецця укрупненного узла достаточно возя дить однц цз его сост а вля ющих.В описанной схеме фиксации направления прохождения фронта волны имеется только одна цепь задержки, ц поэтому модель отображает гриф с одцнаковымп задержками в обоих направлениях ветви. Для моделирования графа с рязнымп задержками в разных направления ветвей схему ИЛИ 22, выбрасывают, но вставляют вторую цепь задержки. Прц этом выход схемы НЕТ 18 соединяют со входами схемы И 24 и второй цепи задержки, выход которой соединяют со вторым входом схемы И 24. Выход же схемы И соединяют со входом схемы НЕТ 21. Аналогичным образом включают первую цепь задержки и схехг И 23 гежд вггходамц схем НЕТ 21 ц 19. Прс дмет изоор етенця Устройство для определения кратчайших гутей ня графе, содержащее модели узлов и ветвей с логическими схемами НЕТ, ИЛИ и задержки, от.гггчающееся тем, что, с целью упрощения устройства, увеличедгия его возможностей, скорости и надежности вычислений, в цем в каждую из моделей ветви вклкчены потенциальные схемы НЕТ, сигцальныц вход одноц из которых соединен с первым входом-выходом модели ветви, а выход - с запрещающим входом другой и через цепь задержки - со входом третьей схемы НЕТ, выход которой соединен со схемой упорядоченной выборки номеров ветвей кратчайшего пути, с запрещающим, входом четвертой схемы НЕТ и через диод распределенной схемы 11 ЛИ, принадлежащей модели смежного узла. - со вторым входом-выходом; кроме того, сцгняльныц вход четвертой схемы НЕТ соединен со вторым входом-выходом модели ветви. а выход - с запрещающим входом третьей схемы НЕТ ц через цепь задержки - со входом второй схемы НЕТ, выход которой соединен со схемой упорядоченагой выборки номеров ветвей кратчайшего пути, с запрещающим входом первой схемы НЕТ ц через диод распределенной схемы ИЛИ с первым входом-выходом модели ветви.288424 г 2 С:с авптель Е. Тимохинааедактор Б. Б. Федотов Тсхред Т. П, Курилко Корректор Н. П, Бронскаи Заказ 42/28ЦПИ 11 ПИ К митета Тппваньк фил. пред. П1Тираж 480 делам п 30013 стенпй и открытии .11 оскза, Ж.35, Рау 1 пская ваб., 1 П дппсное Совете Министров с ССР и