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

407345 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик. Кл. 6 06 д 7/48 Гооудврственный комитет Совета Министров СССР ио делам иэооретвний и открытийДК 681,333:656.072 (088.8) Дата опубликован описания 28.П 1.1974 вторыобретен Л. В. Федотов и Л, В. Филиппович Киевский автомобильно-дорожный инстит аявитель ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ ЧЕРЕЗ СЕТЪ СТРОЙСТ чик 2 параметров дуг, блок 3 элементов времени узлов, блок 4 элементов времени дуг, блок 5 моделей узлов, блок 6 моделей дуг,Программные задатчики параметров узлов 5 и дуг 1 и 2 представляют собой функциональные нелинейные преобразователи, формирующие заданные законы изменения параметров узлов и дуг моделируемой сети.Блоки 3 и 4 элементов времени узлов и дуг 0 содержат управляемые элементы времени узлов и дуг с памятью 3, - Зь соответствующие узлам а - Ы фиг. 2, и 4 и - 4 м, соответствующие дугам аб - сд фиг. 2, время задержки которых пропорционально величине парамет ров узлов и дуг сети.Блок 5 моделей узлов содержит элементыИЛИ б - б, моделирующие узлы сети на Изобретение отностельной техники.Известны устройстчайшего пути черезпенные между собо ся к области вычислиа для определения кратеть, содержащие соедиблоки моделей узлов фиг. 2.Блок 6 моделей дуг содержит модели дуг 20 би - бы, каждая из которых содержит элементы НЕ 71 и 72, элементы ИЛИ 81 и 82 и элемент И 9,Устройство работа25 Пусть выход элеммоделей узлов обозс, с); выход управляузлов 3, - у;(=а, 6,мого элемента време30 бс, Ы, сд). и дуг.Все известные устройства не позволяют решать задачу определения кратчайшего пути через сеть с переменными параметрами дуг и узлов.В предложенном устройстве указанный недостаток исключен.Устройство отличается от известных тем, что оно содержит блок элементов времени дуг, первая группа входов которого подключена к первой группе выходов блока моделей узлов, а выходы соединены с первой группой входов блока моделей дуг, блок элементов времени дуг, первая группа входов которого подключена к выходам блока моделей дуг, а выходы соединены со входами блока моделей узлов, и программные задатчики параметров узлов и дуг, соединенные со вторыми группами входов блоков элементов времени узлов и дуг соответственно.На фиг, 1 приведена блок-схема предлагаемого устройства для сети, представленной на фиг. 2.Устройство содержит программный задатчик 1 параметров узлов, программный задатет следующим образом, ента ИЛИ б;, блока 5 начен буквой х;(=а, О, емого элемента времени с, д); выход управляени дуг 4 - гц(я=аб, ас,В начальный момент времени хп = 1, уа = О, так как переход у, в состояние 1 определяется выдержкой времени управляемого элемента 3, времени узла. При этом на выходе элементов 1 Л 9 в моделях дуг бь и бсохраняется значение О.Через выдержку времени, соответствующую времени задержки в узле а, упереходит в состояние 1. Произойдет запуск управляемых элементов времени дуг 4,ь и 4, (1 на выходе элементов И 9 соответствующих моделей дуг).Предположим, выдержка времени управляемого элемента времени дуги 4 ы дуги аб меньше, чем управляемого элемента времени дуги 4, дуги ас, т. е. г.ь=1 при г,=О,В этом случае на выходе элемента ИЛИ 5 ь в модели узла появится 1: хь=1, но у,=о.Рассмотрим два возможных в этом случае варианта.1. хь=1; уь=О.х,=1; ус=1.Такой вариант соответствует следующему соотношению временных задержек: 1 и(ас, но Ь)с и аь+ь)ас+с, Где аь, ас - Выдержки времени управляемых элементов времени дуг 4 ь и 4, дуг аа и ас соответственно; ь, с - выдержки времени управляемых элементов времени узлов 5 ь и 5, узлов О и с.При таком состоянии выходов х и у управляемый элемент времени дуги 4 ь, модели дуги бь, будет отключен (выход элемента И 9 модели дуги бьс равен О). Действительно движение по дуге ас в сторону узла с нецелесообразно, так как:аь + ь + ьс)асили в сторону узла О:ас+ с+ ьсаьпри любых значениях 1 ь2. хь=1; Уь=1х,=О; У,=О. Такое положение выходов возможно, когда: 1,+1 (1,+1,На выходе элемента И 9 моделей дуг 5 бь и бы появляется значение 1 и производится запуск управляемых элементов времени этих дуг 4 ь и 4 и, т. е. разрешение на движение в сторону узлов с и д.Если в процессе движения к узлу с (И) 10 сигнал прибудет в эти узлы по любому другому пути, т. е.:Уь = 11 ьс (ьд) = О при "с, (х) = 1,происходит процесс отключения модели дуги 15 б (бы) аналогично описанному в первомварианте.Таким образом, результатом работы устройства является срабатывание управляемых элементов времени узлов 3; моделируемой 20 сети и управляемых элементов временидуг 4,составляющих дерево кратчайших путей от начального узла сети до всех остальных.25Предмет изобретенияУстройство для определения кратчайшегопути через сеть, содержащее соединенные 30 между собой блоки моделей узлов и дуг,отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит блок элементов времени дуг, первая группа входов которого подключена к первой группе выхо дов блока моделей узлов, а выходы соединены с первой группой входов блока моделей дуг, блок элементов времени дуг, первая группа входов которого подключена к выходам блока моделей дуг, а выходы соединены 40 со входами блока моделей узлов, и программные задатчики параметров узлов и дуг, соединенные со вторыми группами входов блоков элементов времени узлов и дуг соответственно.407345 Составитель Г. СорокинТехред Л. Богданова Корректор Л. Новожилова Редактор Б. Нанкина Типография, пр. Сапунова, 2 Заказ 667/3 Изд. ЛЪ 2092 Тираж 647 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5