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

 

;, т "г

О и й- с A" - Й е

ИЗОБРЕТЕНИЯ

301718

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

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

Респтспик

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

Зависимое от авт. свидетельства №

МПК 6 06р 7/48

Заявлено 02Л!.1968 (№ 1214237/18-24) с присоединением заявки ¹

Приоритет

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

СССР

Опубликовано 21ЛЧЛ971. Бюллетень № 14

Дата опубликования описания 24Л 1.1971

УДК 681.333(088.8) Авторы изобретения А. А. Нерсесянц, П. М. Рыбаков, А. А. Тимохин и В. М. Слащев

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

Заявитель

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

ПУТЕЙ HA ГРАФЕ

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

Известны устройства для определения кратчайших путей на графе с помощью ЭВМ.

Для небольших сетей решение задач на

ЭВМ не представляет принципиальной трудности и широко используется в современной практике.

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

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

«И», на второй вход которой подключен выход

I0 блока управления, а выход схемы «И» подключен к двухвходовым схемам «И», число которых также равно числу ветвей данного узла, второй вход которых соединен с соответствующими выходами триггеров модели узла.

15 На фиг. 1 изображена функциональная схема соединения ЭВМ, блока возбуждения пар узлов, блока формирования кодов ветвей оптимального пути, блока управления, модели сети и узла модели сети, причем в качестве

20 примера взята сеть, состоящая из четырех узлов и пяти ветвеи; на фиг. 2 — функциональная схема узла модели сети; на фиг. 3— функциональная схема ветви сети.

Устройство содержит ЭВМ 1, блок 2 воз25 буждения пар узлов, блок 3 формирования кодов ветвей оптимального пути, блок 4 управления, триггерный регистр 5 с ключами на входе, дешифратор б кодов начального и конечного узлов с ключами на выходе, триггер30 ный регистр 7 с ключами на выходе, шифра3017tH

3 тор 8 номеров ветвей, модель сети 9, соотвегственно выходы 10 — 13 дешифратора для возбуждения узлов модели сети при работе их в качестве начальных, соответственно выходы

14 — 17 дешифратора для возбуждения узлов модели сети при работе их в качестве конечных, шину 18 установки модели в исходное состояние (сброс), выход 19 блока управления для выборки ветвей оптимального пути, соответственно, выходы 20 — 24 ветвей модели сети (появление на них сигнала указывает на наличие соответствующей ветви в кратчайшем пути), узлы 25 — 28 модели сети, ветви 29 — 33 модели сети, удерживающий триггер 34, схемы «ИЛИ» 35 43, блокирующие триггеры

44 — 47, дифференцирующие цепочки 48 — 51, схемы «И» 52 — 56, фиксирующий триггер 57, регулируемые (секционированные) линии задержки 58 и 59, схему «ИЛИ» 60, триггер 61, шины 62 и 63 сигналов индикации ребер кратчайшего пути, эмиттерные повторители 64 67, выход 68 переменной линии задержки и вход

69 переменной линии задержки.

Функциональная схема устройства состоит из четырех основных блоков. блока 2 возбуждения пар узлов, блока 3 формирования кода ветвей, блока 4 управления и модели сети 9.

При этом входы блока 2 возбуждения пау узлов и выходы блока 3 формирования кода ветвей соединяются с ЭВМ 1. Выходы регистра 5 соединены с дешифратором 6 кодов начальных и конечных узлов. Кроме того, блок

2 возбуждения пар узлов соединен с блоком 4 управления, который производит прием числа из ЭВМ, запись его в регистр 5 и выдает импульс на возбуждение пары узлов. Выходы начальных и конечных узлов блока 2 возбуждения пар узлов соединяются с соответствующими узлами модели сети 9. Выходы же ветвей модели сети соединяются со входами шифратора 8.

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

Блок управления представляет собой схему, состоящую из формирователей импульсов, линий задержки и усилителей, преобразующую потенциалы, поступающие из дешифратора команд ЭВМ l, в импульсы и формирующую потенциалы и импульсы в соответствующей временной последовательности для сброса модели сети и регистра 5, записи числа в регистр

5, возбуждения .пар узлов,,сброса регистра 7, выборки очередной ветви и ввода номера ветви в ЭВМ i.

Модель сети состоит из типовых схем моделей узлов (см. фиг, 2) и моделей ветвей (см. фиг, 3) . На передней панели приставки из этих элементов с помощью штепсельных раз.ьемов устанавливается заданная конфигурация сети, а с помощью секционированных линий задержек — заданные веса всех ветвей, 5

25 зо

Схема (см. фиг. 2) состоит из четырех блокирующих триггеров 44 — 47 по числу направлений с данного узла, удерживающего триггера 34, фиксирующего триггера 57, дифференцирующих цепочек 48 — 51 и схем «И» 52—

56 и «ИЛИ» 35 43. Модель ветви (см, фиг.

3) состоит из схемы «ИЛИ» 60, триггера 61 и четырех шин, две из которых содержат линии задержки.

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

При появлении в программе работы ЭВМ команды 1(, которая не используется в конкретной программе, с дешифратора команд

ЭВМ в блок 4 поступает перепад напряжения. Блок 4 управления формирует из этого перепада импульс сброса модели сети 9 и регистра 5, который устанавливает их в начальное состояние.

Через некоторое время из ЭВМ поступает код, который, проходя через блок 4 управления, записывается в регистр 5. Выведенный код содержит номера начального и конечного узлов и соответственно этим номерам возбуждаются две шины дешифраторов. Далее, блок управления вырабатывает импульс, задержанный относительно начала команды К на время t, который поступает на все ключи дешифратора 6. Этот импульс поступает на запуск соответствующих начального и конечного узлов 25 — 28. Конечный узел фиксируется перебросом в единичное состояние триггера 57.

В начальном узле запускающий импульс перебрасывает удерживающий триггер и через схемы «ИЛИ» поступает на все инцидентные данному узлу ветви (из числа ветвей 29 — 33), С этого момента по линиям задержки ветвей распространяются импульсы напряжения к смежным узлам сети. Импульс, дошедший первым до какого-либо узла, перебрасывает в единичное состояние соответствующий своей ветви блокирующий триггер 44 — 47, в функции которого входят: блокировка данного узла от сигналов других направлений (осуществляется подачей постоянного запрещающего потенциала на входы «0» всех остальных триггеров), «запоминание» кратчайшего направления к исходному узлу (подается единичный потенциал на одну из схем «И» 52 — 55 и посылка импульсов по ветвям всех других направлений, кроме своего) осуществляется подачей дифференцированного перепада напряжения с выхода триггера на шины с линиями задержки в соответствующих ветвях через схемы «ИЛИ» 39 — 42 и эмиттерные повторители

64 — 67. Таким образом, от исходного узла чо все стороны распространяются импульсы напряжения, пути которых образуют прадерево, не имеющее замкнутых контуров, Время прохождения импульсов по каждой ветви определяется задержкой, устанавливаемой в линиях задержек 58 и 59.

Выдача в ЭМВ 1 кодов ветвей оптимального пути производится по команде К ЭВМ, также не использующейся в программе работы ЭВМ.

Как и в случае команды К>, с дешифратора

3(l1718 команд ЭВМ 1 в блок 4 приставки поступает перепад напряжения, из которого формируются и разносятся по времени импульсы сброса регистра 7, импульс выборки ветви — выход 19 и импульс ввода в ЭВМ кода ветви. Импульс сброса подается на шину «сброс» регистра 7 и сбрасывает его в нуль. Вторым вырабатывается импульс выборки ветви — выход 19, который поступает на схемы «И» 5б всех узлов. На конечном узле эта схема была подготовлена к открытию фиксирующим триггером 57. Импульс выборки ветви через схему

«И» 56 и одну из схем «И» 52 — 55 поступает на шину б2 или бЗ ветви 29 (или подобные им в других ветвях) и на первом от конечного узла промежуточном узле перебрасывает в единичное состояние фиксирующий триггер 57.

Шины б2 и бЗ ветви связаны через схему

«ИЛИ» бО с триггером ветви б1. Импульс выборки перебрасывает его в единичное состояние, С перебросом триггера ветви в дешифратор 8 с одного из выходов 20 — 24 поступает сигнал о том, что данная ветвь вошла в оптимальный путь, и вырабатывается код этой ветви, который записывается в регистр 7 и по команде блока управления вводится в ЭВМ.

Анализируя поступивший код, ЭВМ сравнивает его с нулевым (поступивший нулевой код означает конец выборки ветвей оптимального пути). Следующая за командой сравнения ,команда условной передачи управления, передает управление на повторение команды К, если последний код;ветви был не нулевым, .и продолжение программы, всли указанный код оказался .нулевым. Следующая команда К произведет аналогичные действия в очередной ветви, считая от конца оптимального пути.

На начальном узле (см. фиг. 2) все схемы

«И» 52 — 55 закрыты, поскольку открывающие их триггеры 44 — 47 удерживаются в нулевом состоянии триггером З4. Поэтому импульсы, 5 о

15 го г5 зо

40 б идущие через схемы «И» 5б в шины б2 и бЗ, далее начального узла не распространяются, и при очередной команде К в ЭВМ поступает нулевой код, что свидетельствует об окончании выборки ветвей оптимального пути.

Предмет изобретения

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

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

Редактор Е. В. Семанова Техред Jl. Я. Левина Корректор Л. А. Царькова

Заказ 1424/7 Изд. № 641 Тираж 473 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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

Типография, пр. Сапунова, 2