Устройство для выбора кратчайшего маршрута Советский патент 1987 года по МПК G06F15/173 

11

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

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

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

На чертеже представлена функциональная схема устройства для выбора кратчайшего маршрута движения.

Устройство для выбора кратчайшего маршрута содержит блок 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И-ИЛИ-НЕ, второй и третий входы которого соединены соответственно с прямым и инверсным выходами триггера t1.

Счетный вход счетчика связан с вы- ходом элемента 2И-ИЛИ- НЕ 13, Вход разрешения записи счетчика 2 связан с прямым выходом триггера 11, отку5

4

5 0

5

122

да на счетчик 2 поступает сигнал разрешения записи. Группа установочных входов счетчика 2 подключена к вторым выходам младших разрядов регистра 9, по которому считываются младшие разпяды, содержащие адрес ячейки, хранящей код станции отправления в кратчайшем маршруте. Выход сигнала переполнения счетчика 2 связан с входом установки в 1 триггера 11 и входом останова генератора 14 импульсов. Этот сигнал взводит триггер 11 и сбрасывает генератор 14 импульсов.

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

Первый выход блока 1 адресной памяти, по которому считываются данные из полей А (полей адреса маркера станции или разделителя), связан с первыми входами первого 3 и второго 4 блоков сравнения, а также с входом третьего 5 блока сравнения.

Второй выход блока 1 адресной памяти соединен с информационным входом сумматора 8, по этой шине идут данные из полей В памяти (полей веса) длины (соответствующего элемента трассы),

Выход блока 5 сравнения соединен с установочном входом сумматора 8 и с входом установки н О триггера 12, от него поступает сигнал, по которому происходит сброс этих элементов при обнаружении разделителя петель в памяти. Выход первого блока 3 сравн е- ния связан с входом установки в единицу триггера 12, а также с входом разрешения записи регистра 10, По сигналу в этой цепи взводится триггер 12 и в регистр 10 происходит запись адреса с выхода счетчика 2,

Выход Е торого блока 4 сравнения соединен с первым входом элемента И 7 и с входом установки в О триггера 11. При наличии сигнала в этой цепи происходит сброс триггера 11, Выход триггера 12 соединен с вторым входом элемента И 7, а также с синхронизирующим входом сумматора 8, По этой цепи передается сигнал разрешения суммирования,

Выход сумматора 8 соединен с информационным входом старших разрядов регистра 9 и первым входом четвертого блока 6 сравнения. На этой шине постоянно присутствуют сигналы, пред ставляющие текущее состояние сумматора 8, Второй вход блока 6 сравнения связан с выходом старших разрядов регистра 9. Сигналы на этой шине постоянно представляют состоя- ние старших разрядов регистра. Выход блока 6 сравнения связан с третьим входом элемента И 7. Сигнал в этой цепи присутствует лишь в случае, когда содержимое сумматора 8 меньше данных, поступающих в блок 6 сравнения из регистра 9.

Вход разрешения записи регистра 9 соединен с выходом элемента И 7. По этой цепи передается сигнал разреше- ния записи в регистр 9, по которому в его старшие разряды переписывается содержимое сумматора 8, в младшие - содержимое регистра 10. Третий вход регистра 9 соединен с выходом ре- гистра 10. Сигналы на этой шине постоянно представляют содержимое регистре. 10.

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

При описании транспортной сети принята сквозная адресация (кодирование) станций и ветвлений в пределах всей транспортной сети и описание последней совокупностью всех воз мйжных различаюш 1хся транспортных петель. Каждая транспортная петля описывается двухкратным последовательным перечислением адресов маркеров станций и ветвлений, проходимых при движении вдоль транспортной петли в разрешенном направлении,

В поле адресной памяти устройства описания транспортных петель располагаются в произвольном порядке не- посредственно друг за другом и отделяются специально закодированными словами-разделителями. Слова, хранимые в блоке 1 адресной памяти, представляются тремя полями: полем адре- са маркера станции или разделителя - А; полем веса (длины) соответствующего элемента трассы - В; и полем кода направления движения - С. Элементом трассы считается участок трассы в пределах одной транспортной петли от предьщутцего по ходу петли маркера до сассматриваемого. Код направлений

движения представляется уменьшенным на единицу номером элемента трассы, соответствующего рассматриваемому маркеру, среди других элементов трассы, исходяш 1х из предыдущего маркера (возможно развилки) в рассматриваемо транспортной петле и отсчитанных от предыдущего элемента однообразно для описания всех транспортных петель, например по часовой стрелке. При использовании описанной модели транспортной сети решение задачи выбора кратчайшего маршрута движения транспортного средства сводится к последовательному однократному просмотру в блоке 1 адресной памяти описаний всех транспортных петель, выявлении при этом маршрутов, связывающих заданные станции (маркеры), и последовательному отбору кратчайшего по длине маршрута. Факт наличия в какой либо транспортной петле маршрута, связывающего заданные станции устанавливается по наличию в соответствующем описании и адреса маркера станции отправления, и адреса маркера станции назначения транспортного средства.

В устройстве просмотр адресной памяти в блоке 1 обеспечивается по адресам, формируемым счетчиком 2, сигнал переполнения которого свидетельствует об окончании поиска и через первый триггер 11 останавливает работу устройства. Обнаружение разделителей описаний обеспечивает третий блок 5 сравнения слов с адресами станций отправления и назначения. Определение длины находимых маршрутов осуществляется суммированием дли перегонов при просмотре маршрутов с помощью сумматора 8, сравнение их с кратчайшим из ранее найденных маршрутов, длина которого запоминается в первом регистре 9, обеспечивается четвертым блоком 6 сравнения. Во втором регистре 10 записьшается адрес маркера станции отправления в описании данной петли. Если длина маршрута в данном описании меньше длины маршрута, записанной в первом регистре 9, то адрес маркера станции отправления вместе с новой длиной маршрута перезаписьшается в первьй регистр 9.

Работа устройства разбивается на 2 этапа - нахождение кратчайшего маршрута и выдача этого маршрута по

5

запросам от внешнего устройства (потребителя) .

Использованию устройства предшествует формирование адресной памяти в блоке 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, то на выходе блока 6 сравнения появится единичный сигнал.

Сигналы с выходов триггера 12, второго блока 4 сравнения и блока 6 сравнения поступают на вход элемен та И 7, При наличии всех трех сигналов, что означает существование в рассматриваемой петле маршрута между станциями отправления и назначения и имеющего длину меньшую, чем у всех предыдущих маршрутов, на выходе элемента И 7 появится сигнал разрешения записи в регистр 9 длины данного маршрута из сумматора 8 и адреса ячейки памяти из регистра 10.

Если в описании этой петли еще раз встретится данный маршрут, то он еще раз вычисляется, но перезаписи не

954126

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

5 выходе блока 5 сравнения появится сигнал, по которому происходит сброс сумматора 8 и триггера 12,

Если в описании петли раньше кода станции отправления (и до разделите0 ля, так как им оканчивается описание петли) встретится код станции назначения, то на выходе второго блока 4 сравнения появится сигнал, но так как триггер 12 не взведен, to на вы 5 ходе элемента И 7 нулевой сигнал и никаких действий не производится. Когда просмотрена вся адресная память, появляется сигнал переполнения на выходе счетчика 2. При наличии

0-этого сигнала триггер 11 взведен, а генератор импульсов 14 сброшен. В регистре 9 хранится длина кратчайшего маршрута и адрес ячейки памяти, в которой хранится код станции отправления, соответствующей этому маршруту. По сигналу на первом выходе триггера 11 произойдет запись в счетчик 2 из ре.гистра 9 адреса ячейки памяти начала маршрута, вьщача сигнала го товности к внешнему устройству, отклонение генератора 14 импульсов и подключение внешнего устройства через эл€;мент 13 к входу счетчика 2. По каждому запросу внешнего уст35 ройства через элемент 13 подается - импульс увеличения на единицу состояния счетчика 2, в результате чего адресуется следующая ячейка блока 1 памяти и с его третьего выхода выдает0 ся следуюш 1Й код направления движе-: ния, при достижении кода станции назначения на выходе блока 4 сравнения появляется сигнал, по которому происходит сброс триггера 11 и устрой5 ство пбфеходит в свое исходное состояние,

Формула изобретения

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

5 сумматор и первый регистр, информаци- онньш выход счетчика соединен с входом адресной памяти, вьпсод адреса маркерс1 станции которого подключен к первым входам первого, второго и третьего блоков сравнения, второй вход первого блока сравнения является входом кода станции назначения устройства, второй вход второго блока сравнения является входом кода станции отправления устройства, группа выходов накапливающего сумматора подключена к первой группе входов четвертого блока сравнения и к входам старших разрядов первого регистра, вторая группа входов четвертого блока сравнения подключена к выходам старших разрядов первого регистра, отличающееся тем, что, с целью упрощения устройства, в него введены второй регистр, первый и второй триггеры, элемент И и элемент 2И-ИЛИ-НЕ, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к первому входу элемента 2И-ИЛИ-НЕ, второй вход которого подключен к инверсному выходу первого триггера, третий вход элемента 2И-ИЛИ-НЕ подключен к прямому входу первого триггера, а четвер- тый вход элемента.2И-ИЛИ-НЕ является входом кода маршрута движения устройства, выход элемента 2И-ИЛИ-НЕ подключен к счетному входу счетчика, вход разрешения записи которого подключен к инверсному выходу первого триггера, группа установочных входов ,счетчика подключена соответственно к вь1ходам младших разрядов первого регистра, информационньй выход счетчиРедактор С.Патрушева Заказ 619/56

Составитель Т.Сапунова Техред И.Попович

Тираж 673 ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул. Проектная, 4

5

ка подключен к информационному входу второго регистра, выход сигнала переполнения счетчика подключен к входу останова генератора импульсов и к входу установки в t первого триггера, инверсный выход которого является выходом сигнала готовности устрой- . ства, выход кода веса элемента трассы блока адресной памяти подключен к входу накапливающего сумматора, вход установки в О которого объединен с входом установки в О второго триггера и подключен к выходу третьего блока сравнения, второй вход которого является входом кода промежуточных станций устройства, вход синхронизации накапливающего сумматора подключен к выходу второго триггера, вход установки в 1 которого подключен к выходу первого блока сравнения, выход первого блока сравнения подключен к входу разрешения записи второго регистра, выход которого подключен к входам младших разрядов первого регистра, выход второго блока сравнения подключен к входу установки в О первого триггера и к первому входу элемента И, выход второго триггера подключен к второму входу элемента И, выход четвертого блока сравнения подключен к третьему входу элемента И, выход которого подключен к входу разрешения записи первого регистра, выход кода направ- 5 ления движения блока адресной памяти является информационным выходом устройства.

0

5

0

Корректор М.Самборская Подписное

Изобретение- относится к области вычислительной техники и может быть применено в автоматизированных транспортных системах, например, внутрицехового назначения. Задача выбора кратчайшео-о маршрута движения транспортного средства заключается в идентификации соответствующей последовательности направлений движения транспортного средства относительно маркеров станций и ветвлений в транспортной сети с односторонними проездами, представляемой объединением транспортных петель. Целью изобретения является упрощение устройства выбора кратчайшего маршрута. Поставленная цель достигается тем, что устройство, содержаш,ее блок 1 адресной памяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блоки сравнения, сумматор 8, первый регистр 9, введены элемент И 7, второй регистр 10, первый и второй триггеры 11 и 12 и элемент 2И-ИЛИ-НЕ 13. Использойание устройства позволяет автоматизвдовать управлзние транспортными средствами в условиях частого измерения целевых установок. В частности, его можно использовать при реализации гибкого автоматического производства с его мелкосерийностью и частыми именами маршрутной технологии. 1 ил. 3CLntJClf I , (О го QD СП пкши