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

 

407345

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Респу6лик

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

Заявлено 02.Ч11,1971 (№ 1678308i18-24) с присоединением заявки № 1:685484/18-24

Приоритет

Опубликовано 21.XI 1973. Бюллетень № 46

Дата опубликования описания 28.1П.1974

М. Кл. G 06g 7/48

Государственный комитет

Совета Министров СССР ао делам иэооретвний и открытий

УДК 681.333:656.072 (088.8) Авторы изобретения

Л. В. Федотов и Л. В. Филиппович

Киевский автомобильно-дорожный институт

Заявитель

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

ЧЕРЕЗ СЕТЪ

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

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

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

В предложенном устройстве указанный недостаток исключен.

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

На фиг, 1 приведена блок-схема предлагаемого устройства для сети, представленной на фиг. 2.

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

Программные задатчики параметров узлов и дуг 1 и 2 представляют собой функциональные нелинейные преобразователи, формирующие заданные законы изменения параметров узлов и дуг моделируемой сети.

Блоки 3 и 4 элементов времени узлов и дуг

10 содержат управляемые элементы времени узлов и дуг с памятью 8,— 8,ь соответствующие узлам а — d фиг. 2, и 4, — 4,a, соответствующие дугам ab — cd фиг. 2, время задержки которых пропорционально величине парамет15 ров узлов и дуг сети.

Блок 5 моделей узлов содержит элементы

«ИЛИ» 5,— 5д, моделирующие узлы сети на фиг. 2.

Блок 6 моделей дуг содержит модели дуг

20 бай бои каждая из которых содержит элементы «НЕ» 7> и 72, элементы «ИЛИ» 8> и 82 и элемент «И» 9.

Устройство работает следующим образом, 25 Пусть выход элемента «ИЛИ» 5;, блока 5 моделей узлов обозначен буквой x;(i=a, b, с, d); выход управляемого элемента времени узлов 8,— у;(i=а, b, с, d); выход управляемого элемента времени дуг 4,; — z;; (i = ab, ac, 30 bc, bd, cd).

407345

В начальный момент времени х, = 1, у„= О, так как переход у в состояние «1» определяется выдержкой времени управляемого элемента 8, времени узла. При этом на выходе элементов «И» 9 в моделях дуг баь и б„„сохраняется значение О.

Через выдержку времени, соответствующую времени задержки в узле а, у, переходит в состояние «1». Произойдет запуск управляемых элементов времени дуг 4„q и 4„(«1» па выходе элементов «И» 9 соответствующих моделей дуг) .

Предположим, выдержка времени управляемого элемента времени дуги 4„ь дуги ab меньше, чем управляемого элемента времени дуги 4„дуги ас, т. е. z. =1 при яас=О.

В этом случае на выходе элемента «ИЛИ»

5„«1»: хь = 1, но у . = О

Рассмотрим два возможных в этом случае варианта.

1. хь=1; уь=О. х,=1; у,=1.

Такой вариант соответствует следующему соотношению временных задержек: 4п<4с, но 4) с и аь+4) ьас+ьс, Где аь, tàñ Выдержки времени управляемых элементов времени дуг 4,ь и 4„дуг ab и ас соответственно;

4, 4 — выдержки времени управляемых элементов времени узлов 5ь и 5, узлов b и с.

При таком состоянии выходов х и у управляемый элемент времени дуги 4ьс модели дуги бьс будет отключен (выход элемента «И»

9 модели дуги бьс равен О). Действительно движение по дуге bc в сторону узла с нецелесообразно, так как: аь + ь + ьа ас или в сторону узла b: ас + с + ьс аь при любых значениях 4,.

2. хь=1; уь=1. х.=О; у,=О.

Такое положение выходов возможно, когда: аь+ ь < ас+ с

На выходе элемента «И» 9 моделей дуг

5 бьс и бь появляется значение «1» и производится запуск управляемых элементов времени этих дуг 4ьс и 4ь, т. е. разрешение на движение в сторону узлов с и d.

Если в процессе движения к узлу с (d)

10 сигнал прибудет в эти узлы по любому другому пути, т. е.: уь:1; z„(züñ,): О при;сс(x„) 1, происходит процесс отключения модели дуги

15 бьс (бьл) аналогично описанному в первом варианте.

Таким образом, результатом работы устройства является срабатывание управляемых элементов времени узлов 3; моделируемой

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

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

Устройство для определения кратчайшего пути через сеть, содержащее соединенные

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

40 со входами блока моделей узлов, и программные задатчики параметров узлов и дуг, соединенные со вторыми группами входов блоков элементов времени узлов и дуг соответственно.

407345

Составитель Г. Сорокин

Техред Л. Богданова Корректор Л. Новожилова

Редактор Б. Нанкина

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

Заказ 667/!3 Изд. ¹ 2092 Тираж 647 Подписное

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

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