Устройство для моделирования маршрута движения, минимизирующего время встречи

Устройство для моделирования маршрута движения, минимизирующего время встречи

Иллюстрации

Показать все

Реферат

 

. (;

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (ii) 446078

Союз Саветскик

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

Республик (61) Зависимое от авт. свидетельства (22) Заявлено 21.02.72 (21) 1750111/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 05.10.74. Бюллетень № 37

Дата опубликования описания 04,07.75 (51) М. Кл. G 06я 7/48

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

Совета Министров СССР (53) УДК 681.33.001.57 (088.8) по делам изобретений и открытий (72) Авторы изобретения

Л. В. Федотов и Л. В. Филиппович (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ МАРШРУТА

ДВИЖЕНИЯ, МИНИМИЗИРУЮЩЕГО ВРЕМЕНИ ВСТРЕЧИ

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

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

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

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

На чертеже приведена блок-схема устройства. стройство содержит программный задатчик параметров ду! l, нрограммныи задатчик lldpa.петров узлов х, олок моделей дуг 6, олок моделеи узлов 4, олок разрешения встречи v, олок индикации маршрута о и олок индикации, у и встречи (. программные задатчики параметров дуг и узлов и 2 представляют сооои функциональные преооразователи, формирующие заданныи закон изменения параметров дуг и узлов моделируемои сети.

uëîêè моделей дуг и узлов 3 и 4 содержат управляемые элементы времени дуг и узлов с памятью, время задержки которых пропорционально величине параметров ду и узлов сети, логические элементы «и», «l ËÈ» и «Н ».

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

Блок разрешения встречи 5 служит для обнаружения на сети дуги встречи корреспондентов и с этой целью содержит два источника э.д.с. и логические элементы «И», число кото3р рых равно числу дуг сети.

446078

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

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

Пусть Л;, Л,— состояние выхода моделей узлов и блока моделей узлов 2;

Y," — состояние выхода модели дуги

ij блока моделей дуг 1.

Л,; — состояние выхода модели дуги ij блока разрешения встречи 5.

В моменты времени т и т, соответствующие началу движения из корреспондирующих узлов Н1 и -12, состояние выходов моделей этих узлов Лн — — 1 и Хн = — 1. 11ри этом на время начала движения никаких ограничений не накладывается, т. е. xi — — т лиоо .с т . Запуск программных задатчиков параметров дуг и узлов 1 и 2 осуществляется одновременно в момент т начала решения: т=-. =т2 либо т=.сь если <1(<2> либо т=т, если т2(т.

Для каждого корреспондента определяются кратчайшие по времени движения маршруты к возможному месту их встречи. Процесс поиска кратчайших маршрутов исключает возможность образования циклов на сети, что достигается условием и,, =- О, если х, = — 1 и х, = 1.

Переход Х; и Х; в состояние «1» определяется переходом в «1» выхода модели любой из дуг, входящих в 1-й и I-й узел соответственно, и выдержкой времени элемента времени

i-го и j-го узлов.

Переход в единичное состояние выхода модели дуги Й определяется условием Х;=1 и

Х;=1 и выдержкой времени элемента времени дуги ij.

Задача нахождения на сети маршрута, минимизирующего время встречи, предполагает для дуги встречи выполнение условия и,,- =- 1, если х, = 1 и х,. = 1, что противоречит лежащему в основе решения задачи алгоритму поиска кратчайших маршрутов. С целью исключения такого противоречия в схему устройства введен специальный блок разрешения встречи 5, в котором дублируются маршруты движения, но при этом потенциалам, иммитирующим движение корреспондентов присваиваются различные признаки (различные величины источников э.д.с. блока 5). Вдиничное состояние выход модели дуги ij 4,, блока разрешения встречи 5 принимает при наличии в i-ом и j-ом узлах потенциалов с различными признаками.

Для каждой дуги 11 сети характерны три возможных состояния.

1. х — 1, х — — О, z>J — — О.

В этом случае У;, через выдержку времени, определяющую время проезда по дуге ij принимает значение «1» и процесс поиска маршрутов продолжается.

2;=-1,. — 1, г, -O.

Такое соотношение выходов приводит к образованию циклов на сети при поиске маршрута какого-либо корреспондента и запуска

20 элемента времени дуги i1 не произойдет,,У,, =О.

3.

Переход Z, в состояние «1» свидетельствует оо обнаружении оптимальной дуги встречи.

В этом случае У;; принимает значение «1», дуга встречи индицируется блоком индикации дуги 7, а маршрут движения к месту встречи фиксируется блоком индикации маршрута как

30 последовательность сработавших дуг и узлов.

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

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

45 встречи, третий и четвертый выходы подключены соответственно ко входу блока индикации маршрута и блока индикации дуги встречи, выход задатчика параметров дуг соединен со входом блока моделей дуг, а выход задат50 чика параметров узлов подключен ко вход1 блока моделей узлов.

446078

СоставительЛ. Филиппова

Техред В. Рыбакова

Корректор Н. Учакина

Редактор Л. Утехина

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

Заказ 1341/13 Изд. № 457 Тираж 624 Подписное

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

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