Устройство для выбора кратчайшего маршрута

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 4 С 06 Р 15 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОБРЕТЕНИЕПЬСТВУ(71) Ленинградский институт авиционного приборостроения(56) Авторское свидетельство ССУ 851411, кл. С 06 Р 15/20, 197Авторское свидетельство СССРВ 1206792, кл. С 06 Р 15/20, 19(57) Изобретение. относится к вычислительной техники и може применено в автоматизированнь спортных системах, например, цехового назначения. Задача в кратчайшего маршрута движения портного средства заключается тификации соответствующей пос бласти х тран триа тран маршрутцои технологии ледоваОПИСАНИЕ ИН АВТОРСИОМУ СВИ 54) УСТРОЙСТВО ДЛЯ ВЫБОРО МАРШРУТА 801295412 тельности направлеции движения транспортного средства относительно маркеров станций и ветвлений в транспортной сети с односторонними проездами, представляемой объединением транспортных петель, Целью изобретения является упрощение устройства выбора кратчайшего маршрута. Поставленная цель достигается тем, что устройство, содержащее блок 1 адресной памяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блоки сравнения, сумматор 8, первый регистр 9, введены элемент И 7, второй регистр 10, первый и второй триггеры 11 и 12 .и элемент 2 И-ИЛИ-НЕ 13. Использование устройства позволяет автоматизировать Я управление транспортными средствами в условиях частого измерения целевых установок, В частности, его можно ( " использовать при реализации гибкого автоматического производства с его мелкосерийностью и частыми Сменами1 12Изобретение относится к вычислительной технике и может быть применено в автоматизированных транспортных системах, например внутрицехового назначения,Выбор кратчайшего маршрута движения транспортного средства заключается в идентификации соответствующейпоследовательности направлений движения транспортного средства относительно маркеров станций и ветвленийв транспортной сети с одностороннимипроездами, представляемой объединением транспортных петель,Цель изобретения - упрощение устройства выбора кратчайшего маршрута.На чертеже представлена функциональная схема устройства для выборакратчайшего маршрута движения.Устройство для выбора кратчайшегомаршрута содержит блок 1 адреснойпамяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блокисравнения, элемент И 7, сумматор 8,первый регистр 9, второй регистр 10,первый 11 и второй 12 триггеры, элемент 2 И-ИЛИ-НЕ 13 и генератор 14 импульсов. Информационными входами устройства, предназначенными для вводасоответственно кода станции отправления и станции назначения, являютсявторые входы блоков 3 и 4 сравнения,шина запуска устройства соединена свходом запуска генератора 14 импульсов, Информационным выходом устройства, предназначенным для вывода результатов работы устройства в видекода направления движения транспортного средства, является третий выход блока 1 адресной памяти. Осведомительным выходом устройства, предназначенным для вывода сигнала готовности к внешнему устройству, яв"ляется первый выход триггера 11, Входом устройства для запросов выдачикодов маршрута движения служит четвертый вход элемента 2 И-ИЛИ-НЕ 13.Выход генератора 14 импульсов связан с первым входом элемента 2 И-ИЛИНЕ 13, например один из двух элементов микросхемы 2 И-ИЛИ-НЕ, второй итретий входы которого соединены соответственно с прямым и инверсным выходами триггера 11,Счетный вход счетчика связан с выходом элемента 2 И-ИЛИ-НЕ 13. Входразрешения записи счетчика 2 связанс прямым выходом триггера 11, отку 95412 2 35 45 разрешения записи регистра 10, По сигналу в этой цепи взводится триггер 12 и в регистр 10 происходит запись адреса с выхода счетчика 2. Выход второго блока 4 сравнения50 соединен с первым входом элемента И 7 происходит сброс триггера 11, Выход триггера 12 соединен с вторым входом55 элемента И 7, а также с синхронизи 5 Ю 15 гс 25 30 да на счетчик 2 поступает сигнал разрешения записи. Группа установочныхвходов счетчика 2 подключена к вторым выходам младших разрядов регистра 9, по которому считываются младшиеразяды, содержащие адрес ячейки,хранящей код станции отправления вкратчайшем маршруте. Выход сигналапереполнения счетчика 2 связан свходом установки в "1" триггера 11и входом останова генератора 14 импульсов. Этот сигнал взводит триггер 11 и сбрасывает генератор 14 импульсов,Информационный выход счетчика 2связан с входом блока 1 адресной памяти. С помощью этой связи коды состояний счетчика 2 используются в качестве задающих адресов для блока 1адресной памяти, Информационный выход счетчика 2 также связан с информационным входом регистра 10.Первый выход блока 1 адресной памяти, по которому считываются данныеиз полей А (полей адреса маркера станции или разделителя), связан с первыми входами первого 3 и второго 4блоков сравнения, а также с входомтретьего 5 блока сравнения.Второй выход блока 1 адресной памяти соединен с информационным входом сумматора 8, по этой шине идутданные из полей В памяти (полей веса)длины (соответствующего элементатрассы).Выход блока 5 сравнения соединенс установочном входом сумматора 8 и свходом установки в "0" триггера 12,от него поступает сигнал, по которому происходи г сброс этих элементов приобнаружении разделителя петель в памяти, Выход первого блока 3 сравнения связан с входом установки в единицу триггера 12, а также с входом и с входом установки в "0" триггера 11. При наличии сигнала в этой цепи рующим входом сумматора 8. По этойцепи передается сигнал разрешениясуммирования, з 1295Выход сумматора 8 соединен с информационным входом старших разрядоврегистра 9 и первым входом четвертого блока 6 сравнения, На этой шинепостоянно присутствуют сигналы, пред вставляющие текущее состояние сум -матора 8, Второй вход блока 6 сравнения связан с выходом старших разрядов регистра 9. Сигналы на этойшине постоянно представляют состоя Оние старших разрядов регистра, Выходблока 6 сравнения связан с третьимвходом элемента И 7, Сигнал в этойцепи присутствует лишь в случае,когда содержимое сумматора 8 меньше 15данных, поступающих в блок 6 сравнения из регистра 9,Вход разрешения записи регистра 9соединен с выходом элемента И 7, Поэтой цепи передается сигнал разрешения записи в регистр 9, по которомув его старшие разряды переписываетсясодержимое сумматора 8, в младшие -содержимое регистра 10, Третий входрегистра 9 соединен с выходом регистра 10, Сигналы на этой шине постоянно представляют содержимое регистра 10,Устройство работает следующим образом, 30При описании транспортной сетипринята сквозная адресация (кодирование) станций и ветвлений в пределах всей транспортной сети и описание последней совокупностью всех возмбжных различающихся транспортных петель, Каждая транспортная петля описывается двухкратным последовательным перечислением адресов маркеровстанций и ветвлений, проходимых при 40движении вдоль транспортной петли вразрешенном направлении,В поле адресной памяти устройстваописания транспортных петель располагаются в произвольном порядке непосредственно друг за другом и отде-ляются специально закодированнымисловами-разделителями, Слова, хранимые в блоке 1 адресной памяти, представляются тремя полями: полем адреса маркера станции или разделителя -А; полем веса (длины) соответствующего элемента трассы - В; и полем коданаправления движения - С, Элементомтрассы считается участок трассы впределах одной транспортной петлиот предыдущего по ходу петли маркерадо вассматриваемого, Код направления 412движения представляется уменьшеннымна единицу номером элемента трассы,соответствующего рассматриваемомумаркеру, среди других элементов трассы, исходящих из предыдущего маркера(возможно развилки) в рассматриваемойтранспортной петле и отсчитанных отпредыдущего элемента однообразно дляописания всех транспортных петель,например по часовой стрелке, При использовании описанной модели транспортной сети решение задачи выборакратчайшего маршрута движения транспортного средства сводится к последовательному однократному просмотрув блоке 1 адресной памяти описанийвсех транспортных петель, выявлениипри этом маршрутов, связывающих заданные станции (маркеры), и последовательному отбору кратчайшего подлине маршрута, Факт наличия в какойлибо транспортной петле маршрута,связывающего заданные станции, устанавливается по наличию в соответствующем описании и адреса маркера станции отправления, и адреса маркерастанции назначения транспортногосредства.В устройстве просмотр адресной памяти в блоке 1 обеспечивается по адресам, формируемым счетчиком 2, сигнал переполнения которого свидетельствует об окончании поиска и черезпервый триггер 11 останавливает работу устройства, Обнаружение разделителей описаний обеспечивает третийблок 5 сравнения слов с адресамистанций отправления и назначения,Определение длины находимых маршрутов осуществляется суммированием длинперегонов при просмотре маршрутовс помощью сумматора 8, сравнениеих с кратчайшим из ранее найденныхмаршрутов, длина которого запоминается в первом регистре 9, обеспечивается четвертым блоком 6 сравнения.Во втором регистре 10 записываетсяадрес маркера станции отправления вописании данной петли. Если длинамаршрута в данном описании меньшедлины маршрута, записанной в первомрегистре 9, то адрес маркера станцииотправления вместе с новой длииоймаршрута перезаписывается в первыйрегистр 9,Работа устройства разбивается на2 этапа - нахождение кратчайшего маршрута и выдача этого маршрута по295412 6 51015 45 5 1запросам от внешнего устройства (потребителя).Использованию устройства предшествует формирование адресной памяти вблоке 1, сброс в нулевое состояниесчетчика 2, сумматора 8, регистра 10регистров 11 и 12, заполнение единицами всех разрядов регистра 9 и подача на вторые входы первого 3 и второго 4 блоков сравнения адресов соответственно станции отправления истанции назначения,При появлении сигнала на шине запуска начинает работать генератор 14импульсов. Импульсы от него проходятчерез элемент 13, так как триггер 11сброшен. Под действием этих сигналовсчетчик 2 начинает просматривать адресную память 1, Как только в описании встретится адрес станции отправления, на выходе первого блока 3сравнения появится сигнал, По этомусигналу взводится триггер 12 и адресячейки памяти, в которой хранитсякод станции отправления, записываетсяиз счетчика 2 в регистр 10. С выхода триггера 12 на сумматор 8 поступает сигнал разрешения накапливания. Продолжается просмотр адресной памяти, в сумматоре 8 накапливается длина маршрута путем суммирования длин перегонов между маркерами,Если обнаруживается код станцииназначения в описании данной петли,то на выходе второго блока 4 сравнения появляется единичный сигнал.Если при сравнении длины данногомаршрута, находящегося в сумматоре 8,с содержимым регистра 9 (старшие разряды) окажется, что она меньше длинымаршрута, хранимого в регистре 9 тона выходе блока б сравнения появитсяединичный сигнал,Сигналы с выходов триггера 12второго блока 4 сравнения и блока бсравнения поступают на вход элемента И 7, При наличии всех трех сигналов, что означает существование врассматриваемои петле маршрута междустанциями отправления и назначенияи имеющего длину меньшую, чем у всехпредыдущих маршрутов, на выходе элемента И 7 появится сигнал разрешениязаписи в регистр 9 длины данного маршрута из сумматора 8 и адреса ячейкипамяти из регистра 10.Если в описании этой петли еще развстретится данный маршрут, то он ещераз вычисляется, но перезаписи не будет, так как он будет не меньше предыдущего, Если в описании петли не встретится код станции назначения, то при обнаружении разделителя на выходе блока 5 сравнения появится сигнал, по которому происходит сброс сумматора 8 и триггера 12.Если в описании петли раньше кода станции отправления (и до разделителя, так как им оканчивается описание петли) встретится код станции назначения, то на выходе второго блока 4 сравнения появится сигнал, но так как триггер 12 не взведен, то на выходе элемента И 7 нулевой сигнал и никаких действий не производится,Когда просмотрена вся адресная память, появляется сигнал переполненияна. выходе счетчика 2, При наличии 20 этого сигнала триггер 11 взведен, агенератор импульсов 14 сброшен, Врегистре 9 хранится длина кратчайшегомаршрута и адрес ячейки памяти, вкоторой хранится код станции отправления, соответствующей этому маршруту, По сигналу на первом выходе триггера 11 произойдет запись в счетчик2 из регистра 9 адреса ячейки памятиначала маршрута, выдача сигнала готовности к внешнему устройству, отклонение генератора 14 импульсов и подключение:внешнего устройства через элемент 13 к входу счетчика 2.По каждому запросу внешнего устройства через элемент 13 подаетсяимпульс увеличения на единицу состояния счетчика 2, в результате чего адресуется слецующая ячейка блока 1 памяти и с его третьего выхода выдается следующий код направления движения, При достижении кода станции назначения на выходе блока 4 сравненияпоявляется сигнал, по которому происходит сброс триггера 11 и устройство переходит в свое исходное состояние,Формула изобретения 50 Устройство для выбора кратчайшегомаршрута, соцержащее генератор им"пульсов, счетчик, блок адресной памяти, первый, второй, третий и четвертый блоки сравнения, накапливающий 55 сумматор и первый регистр, информационный выход счетчика соединен с входом адресной памяти, выход адресамаркера станции которого подключен кпервым входам первого, второго и треСоставитель Т.Сапунова Техред И,Попович Корректор М,Самборская Редактор С.Патрушева Тираж 673 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5Подписное Заказ 619/56 Производственно-полиграфическое предприятие, г,ужгород, ул. Проектная, 4 7 12954 тьего блоков сравнения, второй вход первого блока сравнения является входом кода станции назначения устройства, второй вход второго блока сравнения является входом кода станции отправления устройства, группа выходов накапливающего сумматора подключена к первой группе входов четвертого блока сравнения и к входам старших разрядов первого регистра, 10 вторая группа входов четвертого блока сравнения подключена к выходам старших разрядов первого регистра, отличающееся тем, что, с целью упрощения устройства, в него введены второй регистр, первый и второй триггеры, элемент И и элемент 2 И-ИЛИ-НЕ, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к первому входу элемента 2 И-ИЛИ-НЕ, второй вход которого подключен к инверсному выходу первого триггера, третий вход элемента 2 И-ИЛИ-НЕ подключен к прямому входу первого триггера, а четвертый вход элемента 2 И-ИЛИ-НЕ является входом кода маршрута движения устройства, выход элемента 2 И-ИЛИ-НЕ подключен к счетному входу счетчика, вход разрешения записи которого подключен к инверсному выходу первого триггера, группа установочных входов ,счетчика подключена соответственно к выходам младших разрядов первого ре гистра, информационный выход счетчи 12 8ка подключен к информационному входувторого регистра, выход сигнала переполнения счетчика подключен к входуостанова генератора импульсов и квходу установки в " 1 первого триггера, инверсный выход которого являетсявыходом сигнала готовности устройства, выход кода веса элемента трассы блока адресной памяти подключен квходу накапливающего сумматора, входустановки в "0" которого объединенс входом установки в 0 второготриггера и подключен к выходу третьего блока сравнения, второй вход которого является входом кода промежуточньж станций устройства, вход синхронизации накапливающего сумматора подключен к выходу второго триггера,вход установки в "1" которого подключен к выходу первого блока сравнения, выход первого блока сравненияподключен к входу разрешения записивторого регистра, выход которогоподключен к входам младших разрядовпервого регистра, выход второгоблока сравнения подключен к входуустановки в "0" первого триггера и кпервому входу элемента И, выход второго триггера подключен к второмувходу элемента И, выход четвертогоблока сравнения подключен к третьемувходу элемента И, выход которогоподключен к входу разрешения записипервого регистра, выкод кода направления движения блока адресной памятиявляется информационным выходом устройства,