УСТРОЙСТВО для ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ Советский патент 1971 года по МПК G06G7/122 

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

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

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

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

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

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

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

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

примера взята сеть, состоящая из четырех узлов и пяти ветвей; на фиг. 2 - функциональная схема узла модели сети; на фиг. 3 - функциональная схема ветви сети. Устройство содержит ЭВМ 1, блок 2 возбуждения пар узлов, блок 3 формирования кодов ветвей оптимального пути, блок 4 управления, триггерный регистр 5 с ключами на входе, дешифратор 6 кодов начального и конечного узлов с ключами на выходе, триггертор о номеров ветвей, модель сети 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 возбуждения naj узлов и выходы блока 3 формирования кода ветвей соединяются с ЭВМ 1. Выходы регистра 5 соединены с дешифратором 6 кодов начальных и конечных узлов. Кроме того, блок 2 возбуждения пар узлов соединен с блоком 4 управления, который производит прием числа из ЭВМ, запись его в регистр 5 и выдает импульс на возбуждение пары узлов. Выходы начальных и конечных узлов блока 2 возбуждения пар узлов соединяются с соответствуюш;ими узлами модели сети 9. Выходы же ветвей модели сети соединяются со входами шифратора 8.

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

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

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

Схема (см. фиг. 2) состоит из четырех блокирующих триггеров 44-47 по числу направлений с данного узла, удерживающего триггера 34, фиксирующего триггера 57, дифференцирующих цепочек 48-51 и схем «И 52- 56 и «ИЛИ 35-43. Модель ветви (см. фиг. 3) состоит из схемы «ИЛИ 60, триггера 61 и четырех шин, две из которых содержат линии задержки.

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

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

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

5 управления вырабатывает импульс, задерл анный относительно начала команды /Ci на время t, который поступает на все ключи дешифратора 6. Этот имнульс поступает на запуск соответствующих начального и конечного уз0 лов 25-28. КОДечный узел фиксируется перебросом в единичное состояние триггера 57. В начальном узле запускающий импульс перебрасывает удерживающий триггер и через схемы «ИЛИ поступает на все инцидентные

5 данному узлу ветви (из числа ветвей 29-33). С этого момента по линиям задержки ветвей распространяются импульсы напряжения к смежным узлам сети. Импульс, дощедший первым до какого-либо узла, перебрасывает

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

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

команд ЭВМ / в блок 4 приставки поступает перепад напряжения, из которого формируются и разносятся по времени импульсы сброса регистра 7, импульс выборки ветви - выход 19 и импульс ввода в ЭВМ кода ветви. Импульс сброса подается на шину «сброс регистра 7 и сбрасывает его в нуль. Вторым вырабатывается импульс выборки ветви - выход 19, который поступает на схемы «И 56 всех узлов. На конечном узле эта схема была подготовлена к открытию фиксирующим триггером 57. Импульс выборки ветви через схему «И 56 и одну из схем «И 52-55 поступает на шину 62 или 63 ветви 29 (или подобные им в других ветвях) и на первом от конечного узла промежуточном узле перебрасывает в единичное состояние фиксирующий триггер 57. Шины 62 и 63 ветви связаны через схему «ИЛИ 60 с триггером ветви 61. Импульс выборки перебрасывает его в единичное состояние, С перебросом триггера ветви в дещифратор 8 с одного из выходов 20-24 поступает сигнал о том, что данная ветвь вошла в оптимальный путь, и вырабатывается код этой ветви, который записывается в регистр 7 и ло команде блока управления вводится в ЭВМ. Анализируя поступивший код, ЭВМ сравнивает его с нулевым (поступивший нулевой код означает конец выборки ветвей оптимального пути). Следующая за командой сравнения команда условной передачи управлеЕия .передает управление ла повторение команды К, если пОСледний код вет1ви был не нулевым, л продолжение программы, если указанный код оказался .нулевым. Следующая ко,манда K.z произведет аналогич,ные действия в очередной ветви, считая от конца оптимального пути.

На начальном узле (см. фиг. 2) все схемы «И 52-55 закрыты, поскольку открывающие их триггеры 44-47 удерживаются в нулевом состоянии триггером 34. Поэтому импульсы,

идущие через схемы «И 56 в шины 62 и 63, далее начального узла не распространяются, и при очередной команде R в ЭВМ поступает нулевой код, что свидетельствует об окончаНИН выборки ветвей оптимального пути.

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

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

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

узла, второй вход которых соединен с соответствующими выходами триггеров модели узла.

-ТШНТ- -TFFFF

lonnatiHsie)

га гггзг

ifk/IV

ЮS5

67