SU407345A1 - УСТРОЙСТВО дл ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ - Google Patents

Description

1

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

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

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

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

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

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

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

Блоки 3 и 4 элементов времени узлов и дуг содержат управл емые элементы времени узлов и дуг с пам тью За-3d, соответствующие узлам а-d фиг. 2, и 4аь-4cd, соответствующие дугам аЬ-cd фиг. 2, врем  задержки которых пропорционально величине нараметров узлов и дуг сети.

Блок 5 моделей узлов содержит элементы «ИЛИ 5а-5d, моделирующие узлы сети на фиг. 2.

Блок 6 моделей дуг содержит модели дуг баь-6cd, кажда  из которых содержит элементы «НЕ 7i и 72, элементы «ИЛИ 8i и 82 и элемент «И 9.

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

Пусть выход элемента «ИЛИ 5,-, блока 5 моделей узлов обозначен буквой Xi(i a, b, с, d); выход управл емого элемента времени узлов Зг-уг(1 - а, Ь, С, d) выход управл емого элемента времени дуг 4ij--Zij(ij ab, ас,

be, bd, cd). В начальный момент времени , /а 0, так как переход ija в состо ние «1 определ етс  выдержкой времени управл емого элемента 5а времени узла. При этом иа выходе элементов «И 9 в модел х дуг 6о.ъ и сохран етс  значение 0. Через выдержку времени, соответствующую времени задержки в узле а, уа переходит в состо ние «1. Произойдет запуск управл емых элементов времени дуг 4аь и 4ас («1 на выходе элементов «П 9 соответствуюн их моделей дуг). Предположим, выдержка времени унравл емого элемента времени дуги 4аь дуги аЬ меньше, чем управл емого элемента времени дуги 4ас дуги ас, т. е. при Zac 0В этом случае на выходе элемента 5й в модели узла но витс  , но г/й 0. Рассмотрим два возможных в этом случае2 варианта. 1. уь 0. Y 1 . ,/ 1 1, i/c- 1. Такой вариант соответствует следуюш;ему соотношению временных задержек: , 2 но и + tc, ГДе tab, ас - ВЫдержки времени управл емых элементов времени дуг 4аь и 4ас дуг йЬ И йс соответственно; tb, tt - выдержки времени управл емых элементов времени узлов 5ь и 5с узлов Ь и с. При таком состо нии выходов л и г/ управл емый элемент времени дуги 4ьс модели дуги бьс будет отключен (выход элемента «И 9 модели дуги бьс равен 0). Действительно движение по дуге be в сторону узла с нецеле- 3 сообразно, так как: 1 t или в сторону узла Ь: I f f f4 при любых значени х tbc2 . хь - . t/c 0. 3 Такое положение выходов возможно, когда: tab + tb tac + tc На выходе элемента «И 9 моделей дуг бъс и 6bd. по вл етс  значение «1 и производитс  запуск управл емых элементов времени этих дуг 4ъс и 4., т. е. разрешение на движение в сторону узлов end. Если в процессе движени  к узлу с (d) сигнал прибудет в эти узлы по любому другому нути, т. е.: 11 ( -, Q ри х, (х) 1, ьс ьа/ f с а/ происходит процесс отключени  модели дуги (6bd) аналогично описанному в первом варианте. Таким образом, результатом работы устройства  вл етс  срабатывание управл емых элементов времени узлов 5, моделируемой сети и управл емых элементов времени дуг 4ц, составл юших дерево кратчайших путей от начального узла сети до всех остальных . Предмет изобретени  Устройство дл  определени  кратчайшего пути через сеть, содержащее соединенные между собой блоки моделей узлов и дуг, отличающеес  тем, что, с целью расширени  класса решаемых задач, оно содержит блок элементов времени дуг, перва  группа входов которого подключена к первой группе выходов блока моделей узлов, а выходы соединены с первой группой входов блока моделей дуг, блок элементов времени дуг, перва  группа входов которого подключена к выходам блока моделей дуг, а выходы соединены со входами блока моделей узлов, и программные задатчики нараметров узлов и дуг, соединенные со вторыми группами входов блоков элементов времени узлов и дуг соот ветственно.