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

г-,ПИСАКИЗОБРЕТЕН ИЯ 1446078 оюз ГаветскициалистическРеспублик АВТОРСКОМУ СВИДЕТЕЛЬС) Заявлено 21,02,72 (21) 1750111/1851) М. Кл. б 06 я 748 присоединением заявк Государственный квмите Совета Министров СССР(32) ПриоритетОпубликовано 05,10.74. Бюллетень3 Дата опубликования описания 04,07.7 81.33.001.588.8) 3 по делам изобретении и открытий(71) Заявител СТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ М ЕНИЯ, МИНИМИЗИРУЮЩЕГО ВРЕМЕН ШРУТА СТРЕЧИ ДВИ еже приведена блок-схема устрой к области вычисли. На чертстройство содержит программный задатчикпараметров ду 1, программныи задатчик пара.петров узлов л, олок моделей дуг,5, олокмоделеи узлов 4, олок разрешения встречи о,олок индикации маршрута о и олок индикации,уи встречи (.программные задатчики параметров дуг иузлови 2 представляют сооои функциональные преооразователи, формирующие заданныизакон изменения параметров дуг и узлов моделируемои сети,волоки моделей дуг и узлов 3 и 4 содержатуправляемые элементы времени дуг и узловс памятью, время задержки которых пропорционально величине параметров ду и узлов се.ти, логические элементы и, ИЛИ и Н.Назначением блоков моделей дуг и узлов является поиск возможных маршрутов движениядля каждого корреспондента в условиях непрерывно изменяющихся параметров сети, чтоооуславливает наличие взаимосвязи междублоками. ее опредеь, содержантервалов,нныи тригБлок разрешения наружения на сети д тов и с этой целью э.д,с, и логические рых равно числу дуИзобретение относитсятельнои техники.известно устройство, позволяю лить экстремальные пути через се щее датчик случайных временных реверсивный счетчик и индикаци известное устройство не позволяет моделировать маршрут движения, минимизирующий время встречи двух корреспондентов, на сети с заданным детерминированным законом изменения параметров дуг и узлов.В предложенном устройстве этот недостаток исключен.Предложенное устройство отличается от известного тем, что оно содержит блок моделей дуг, блок моделей узлов, задатчик параметров дуг, задатчик параметров узлов, блок разрешения встречи, блок индикации маршрута и блок индикации дуги встречи. Одни вход и выход моделей дуг соединены с соответствующими входом и выходом блока моделей узлов, вторые - со входом и выходом блока разрешения встречи, третий и четвертый выходы - со входами блока индикации маршрута и блока индикации дуги встречи соответственно. Выход задатчика параметров дуг соединен со входом блока моделей дуг, а выход задатчика параметров узлов - со входом блока моделей узлов. встречи 5 служит для об. уги встречи корреспонденсодержит два источника лементы И, число кото- сети.3Блоки индикации маршрута б и дуги встречи ( служат для индикации оптимальногомаршрута движения и дуги встречи соответственно.Устройство работает следующим образом,Пусть Л;, Л, - состояние выхода моделей узловиблока моделей узлов 2;у - состояние выхода модели дуги11 блока моделей дуг 1,Л - состояние выхода модели дуги 11 блока разрешения встречи 5.В моменты времени т и тг, соответствующиеначалу движения из корреспондирующих узлов Н 1 и 1-12, состояние выходов моделей этихузлов Лы=1 и Хнг -- 1, 11 ри этом на времяначала движения никаких ограничений не накладывается, т. е. т=т лиоо ст 2. Запускпрограммных задатчиков параметров дуг иузлов 1 и 2 осуществляется одновременно вмомент т начала решения: т=т=т 2 либот=ть если т(т 2, либо т=тг, если т 2(т,Для каждого корреспондента определяютсякратчайшие по времени движения маршрутык возможному месту их встречи. Процесс поиска кратчайших маршрутов исключает возможность образования циклов на сети, что достигается условиеми=-О, если х,= - 1 и х, =1,Переход Х; и Х; в состояние 1 определяется переходом в 1 выхода модели любойиз дуг, входящих в 1-й и (-й узел соответственно, и выдержкой времени элемента времени1-го и 1-го узлов.Переход в единичное состояние выхода модели дуги Й определяется условием Х;=1 иХ;=1 и выдержкой времени элемента времени дуги 11,Задача нахождения на сети маршрута, минимизирующего время встречи, предполагаетдля дуги встречи выполнение условияи =.1, если х,=1 и х, =1,что противоречит лежащему в основе решения задачи алгоритму поиска кратчайших маршрутов, С целью исключения такого противоречия в схему устройства введен специальный блок разрешения встречи 5, в котором дублируются маршруты движения, но при этом потенциалам, иммитирующим движение корреспондентов присваиваются различные признаки (различные величины источников э.д.с. блока 5). Вдиничное состояние выход модели дуги ц Л блока разрешения встречи 5 5 принимает при наличии в -ом и 1-ом узлах потенциалов с различными признаками.Для каждой дуги 11 сети характерны тривозможных состояния.101. х,=1, х - О, г, =О.В этом случае Х;, через выдержку времени,определяющую время проезда по дуге 11 принимает значение 1 и процесс поиска маршрутов продолжается.2. х, =- 1, х - 1, г, = О.Такое соотношение выходов приводит к образованию циклов на сети при поиске маршрута какого-либо корреспондента и запуска 20 элемента времени дуги 1 не произойдет,,1=О.3. х, = 1, х - 1, г, -- 1.Переход Л в состояние 1 свидетельству ет оо обнаружении оптимальной дуги встречи.В этом случае 1 принимает значение 1, дуга встречи индицируется блоком индикации дуги 7, а маршрут движения к месту встречи фиксируется блоком индикации маршрута как З 0 последовательность сработавших дуг и узлов.Предмет изобретенияУстройство для моделирования маршрутадвижения, минимизирующего время встречи, содержащее блок моделей дуг и блок моделей узлов, отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит задатчик параметров дуг, задатчик параметров узлов, блок разрешения встречи, блок индикации маршрута и блок индикации дуги встречи, причем одни вход и выход блока моделей дуг соединены с соответствующими входом и выходом блока моделей узлов, другие - с входом и выходом блока разрешения 45 встречи, третий и четвертый выходы подключены соответственно ко входу блока индикации маршрута и блока индикации дуги встречи, выход задатчика параметров дуг соединен со входом блока моделей дуг, а выход задат чика параметров узлов подключен ко входблока моделей узлов.Корректор Н. Учакина Редактор Л. Утехина Типография, пр. Сапунова, 2 Заказ 1341/13 Изд.457 Тираж 624 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5