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

(51) М. Кл. Я 06 С 1 7/122 присоединением заявкиГосударственный комнтет Совета Мнннстроа СССР по делам нэобретеннй н отнрытнй(45) Дата опубликования описани 2) Авторы изобретения л.В.федотов и и.м.сергейч(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ И ВЫВОДА НА ПЕЧАТКРАТЧАЙШЕГО ПУТИ ЧЕРЕЗ СЕТЬ С ПЕРЕМЕННЫМИПАРАМЕТРАМИ ВЕТВЕЙ Изобретение относится к области автоматики и вычислительной техники и может быть использовано для решения экономических, транспортньж и других задач, моделируемых на сетях, в частности для информационного обслуживания автотранспортных потоков.Известно устройство для отделения критического пути на сетевом графике, которое содержит модель сетевого графика,состоящую из соединенных между собой моделей работ (моделей однонаправленных ветвей) в соответствии с технологией сетевого графика, и генератора импульсов 11 . Модель работы содержит элемент временной задержки на счетчике импульсов со схемой регенерации, схему выделения на индикацию сигнала принадлежности работы критическому пути и диод, являющийся частью 20 схемы совпадения (модели события).Однако это устройство не позволяет моделировать сетевые графики с переменными длительностями работ и оперативно получать информацию о результа тах моделирования в виде документа.Наиболее близким техническим решением к изобретению является устройство для определения кратчайшего пути через сеть, содержащее программный 30 задатчик параметров ветвей, выход которого соединен со входом задания временной задержки блока моделей двунаправленных ветвей и блок регистрации 21, Модели двунаправленных ветвей соединены между собой полюсами согласно топологии исследуемой сети. Входы задания временной задержки моделей двунаправленных ветвей подключены к одноименному входу блока моделей двунаправленных ветвей, регистрационный выход которого соединен с одноименными выходами моделей двунаправленных ветвей.Однако это устройство определяет лишь дерево кратчайших путей и не поз" воляет получить оперативные док)(менты (информацию) о последовательности ветвей кратчайшего пути между заданными узлами сети, например, для информационного обслуживания автотранспортных потоков..Целью изобретения является расширение функциональных воэможностей устройства за .счет обеспечения оперативного документирования последовательности ветвей кратчайшего пути.Эта цель достигается тем, что предложенное устройство содержит блок ФОР- мирования знака-указателя последовательности ветвей кратчайшею пути,включенный между регистраицонным выхо-( дом блока моделей двунаправленных ветвей и входом блока регистрации, выход которого соединен со входом управления печатью блока моделей двунаправ" ленных ветвей. Последний соединен с одноименными входами моделей двунап равленных ветвей.Модель двунаправленной ветви содержит узел запрета образования замкнуто- )1) го контура, узел управляемых элементов временной задержки, узел управления пеЧатью, узелиндикации, узел разделения и узел обратной связи, выход которого соединен с первым полюсом модели двунаправленной ветви, который соединен с одним входом узла запрета образования замкнутого контура, другой вход которого подключен ко второму полюсу модели двунаправленной ветви, Выход узла запрета образования замкнутого контура соединен с одним входом узла управляемых элементов временной задержки, другой вход которого подключен ко входу задания временной задерж ки модели двунаправленной ветви, а выходы соединены со входами узла управления печатью, соответствующий вход которого подключен ко входу управления печатью модели, двунаправленной ветви. 3 Один выход узла управления печатью соединен с регистрационным выходом модели двунаправленной ветви и входом узла регистрации, а другой - со входами узла обратной связи и узла разделения, выход которого соединен со вто.35 рым полюсом модели двунаправленной ветви.На фиг.1 изображена структурная схема устройства для определения вывода на печать кратчайшего пути через 40 сеть с переменными параметрами ветвей; на фиг.2 - структурная схема модели двунаправленной ветви; на фиг.3- функциональная схема модели двунаправленной ветви; на фиг.4-фрагмент город ской сети и ее кодировка.Устройство содержит программный задатчик 1 параметров ветвей блок мо" делей 2 двунар-вленных ветвей, блок 3 формирования знака указателя после довательности ветвей кратчайшего пути и блок регистрации 4.Блок моделей 2 двунаправленных ветвей содержит модели 5 двунаправленных ветвей, соединенные согласно топологии ис:".ледуемой сетя, вход б задания временной задержки, вход 7 управлении печать 8 и регистрационный выход 8.Модель 5 двунаправленной ветви содержит вход б задания временной задержки вход 7 управления печатью,регистрационный вход 8, узел запрета 9 образования замкнутого контура узел 10 управляемых элементов временной за" держки, узел 11 управления печатьо, узел индикации 12, узел разделения 13,)б узел обратной связи 14 и полюсы 15 и1 б.Узел запрета образования замкнутого контура содержит элементНЕ 17,элемент И 18, элемент НЕ 19 и элементИ 20.Узел 10 управляемых элементов Временной задержки содержит управляемыеэлементы временной задержки 21 и 22,элементы памяти 23 и 24 и элементИЛИ 25,Узел управления печатью 11 содержит элементы И 2 б и 27, элемент запрета решения 28, элемент разрешения печати 29, элемент НЕ 30, элемент ИЛИ 31и элемент памяти 32.Узел индикации 12 содержит элементиндикации 33.Устройство работает следующим образом,В исходном состоянии с выхода блока регистра 4 . поступает на узел 11сигнал разрешения печати в виде логической единицы, однако с приходом сиг.нала иэ блока формирования 3 на блокрегистрации 4 на выходе последнегопоявляется сигнал запрета (инвертируется сигнал разрешения печати) лишьна время. регистрации знака-указателя.Поясним суть работы блока формирования 3 на примере фрагмента городскойсети (фиг.4). Последовательность ко 1 1 1 1 1дов ветвей 1 - 3 , 3 - 1 , 2 - 44 - 2 соответствует знаку-указателю1(прямэ), последовательность 1 - 22 -3 , 3 - 4, 4 - 1 - знаку указателю-(влево), а последовательность1-4,4 - 3.3-2,2-11знаку указателю - (вправо) .Следовательно, выделенный толстойлинией путь между начальным (Н) и коннечным (К) узлами сети 1 - 3,3 - 2,2 - 3, 3 - 1 фиксируется в блоке1 1регистрации 4 в виде знаков - указатЕЛЕй 1,-1-Допустим, требуется определитьпуть между узлами а и д (фиг.1) . Дляэтого переключатель режима работы устройства (на чертеже не показан) ставим в положение решение и подаемв узел а запускающий сигнал Х 1(сигнал решения), этот си.нал поступает одновременно на входы моделей 51н 5 и запускает их элементы временной задержки 21 и 22. Пусть временнаязадержка ветви а 6, ойределяемая уровнем напряжения программного задатчика 1 к этому моменту времени;и параметром ветви д Ь, больше задержка чемВЕТВИ аС, т.Е. 1 11.ТОГДа ПО ИстЕчении времени 11 срабатывает элементвременной задержки 21 ветви ас и навыходе модели 5, т.е. в точке С появляется сигнал (1, который одновременно поступает на входы моделей 5 эи 5 б и модели 5 . В этот момент времени по отношенйю к модели 51 действу".ет условие исключения замкнутого кон= тура (Х:1 и Х 1), поэтому элеменсты временной задержки 21 и 22 модели 5 отключены. Допустим, время задержки ветви а В больше суммы времен задержки ветвейас и е 6,т,е. 1 Ф,+1 з,а сумма времен задержки сби 4 Й больше чем время задержки ветви сц т.еЯв 4+д, Тогда срабатывают элементы временной задержки 21 и 22 моделей 5 и 5 б, По 10 .отношению к моделям Б и 54 действует условие исключения замкнутого контура. Таким образом, срабатывающие модели 51 5 э и 5 я образуют дерево кратчайших путей из узла а ко всем осталь ным узлам.Для определения и вывода на печать кратчайшего пути из г .рева путей перек- лючатель режима работы устройства пе" реводим в положение печать и по даем в конечный узел д запускающий сигнал печати Х- 1, Этот сигнал движется только через сработавшие модели 5 и только в направлении обратном движению сигнала решения. При этому сигнал печати Х движется только через модель 55 в точку с, а иэ нее через модель 51 в точку а . Движение сигнала печати управляется узлами 11 управления печатью, 30Сигналы с моделей двунаправленных ветвей, принадлежащих только кратчайшему пути, поступают на блок 3 формирования знака-указателя.Модель работает сначала в ре.жиме решения задачи определения дерева кратчайших путей. В этом режиме элементы памяти 23, 24 и 32 устанавливаются кнопкой начальная установка ( на чертеже не показана) в 40 нулевое состояние и на элементы И 25 и 26 разрешения печати 29 подается с переключателя сигнал запрета(-Е)в виде логического нуля, который инвертируется элементом 29 и, поступает на эле мент 28 и разрешает решение задачи. При.поступлении сигнала (логической единицы) на один иэ полюсов модели срабатывает элемент И 18 и запускаетуправляемый элемент временной задержки 21, который срабатывает по истечении времени, пропорционального параметру ветви. При этом на выходе элемента 21 появляется сигнал в виде логической единицы, который поступает на элементы 23, 25 и 27. Под действием этого сигнала переводится в единичное состояние элемент памяти 23, выходходной сигнал которого поступает на элемент И 26 обратного направления ветви и подготавливает его для режима печати, а также срабатывает элемент ИЛИ 25, а затем элемент 28, выходной сигнал которого через элемент ИЛИ 31 поступает на элемент памяти 32 и устанавливает его в единичное сос-, 65 тояийе. Выходной сигнал элемента памяти 32 через узел 13 поступает наполюс 16, т.е. на прямые входы последующих моделей двунаправленных ветвей, подключенных к полюсу 16. Поскольку на полюсах 15 и 16 присутствует единичные сигналы, то срабатывает узел 9 запрета образования замкнутого контура, т.е. на выходе элемента И 18 появляется логический нуль,который возвращает элемент задержки21 в исходное состояние (нулевое) .В режиме печати и индикации краччайшего пути кнопкой сброс эле-мент памяти 32 сбрасывает в нулевоесостояние ( на полюсах 15 и 16 сигналК = О) а переключатель режима рабоХ фты ставим в положение печать, Приэтом на элементы 26, 27 и 29 подаетсясигнал разрешения, который инвертируется и в виде запрета поступает наэлемент 28,Запуск модели двунаправленной ветви в режиме печати производим подачейсигнала печати в виде логической един;.цины на полюс 16 (сигнал на полюсе 16равен нулю). Под действием этого сигнала срабатывает элемент И 20, затемэлемент временной задержки 22 (задержка сигнала печати необходима для того,чтобы не срабатызал узел управленияпечатью 11 последующей модели двунаправленной ветви, принадлежащей кратчайшему пути, за время, прошедшее смомента появления сигнала на выходеэлемента разрешения печати 29 до момента срабатывания блока регистрации 4.Сигнал с выхода элемента задержки 22поступает на элемент И 26, на остальных входах которого имеются сигналыв виде логической единицы, Выходнойсигнал сработавшего элемента И 26 через элемент ИЛИ 31 переводит элементпамяти 32 в единичное состояние. Поддействие появившейся на выходе этого элемента 32 логической единицы срабатывает элемент разрешения печати 29выходяой сигнал которого поступает наблок формирования 3, а также на элемент индикации 33 ветви,Для возвращения модели двунаправленной ветви в начальное состояниекнопкой начальная установка исброс устанавливают соответственно элементы 23, 24 и 32 в нулевое состояние, а переключатель в положениерешение.формула изобретения1. Устройство для определения и вывода на печать кратчайшего пути через сеть с переменными параметрами ветвей, содержащее программный задатчик параметров ветвей выход которого соединен со входом задания временной задвржки блока моделей двунаправленных ветвей., в котором модели двунаправлен-. ных ветвей соединены между собой полю сами согласно топологии исследуемой сети, входы задания временной задержки моделей двунаправленных ветвей подключены к одноименному входу блока моделей двунаправленных ветвей, регистрационный выход которого соединен с одноименными выходами моделей дву- р направленных ветвей, и блок регистрации, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воз. можностейустройства за счет оператив. ного документирования последовательности ветвей кратчайшего пути, оно содержит блок формирования знака-указателя последовательности ветвей кратчайшего пути, включенный между регистрационным выходом блока моделей двунаправленных ветвей и входом блока регистрации, выход которого соединен со входом управления печатью блока моделей двунаправленных ветвей, который соединен с одноименными входами моделей двунаправленных ветвей. 252, Устройство по п.1, о т л и ч аю щ е е с я тем, что модель двунаправленной ветви содержит узел запрета образования замкнутого контура, узел управляемых элементов временной эа- ЗО держки, узел управления печатью, узел индикации, узел разделения и узел обратной связи, выход которого соединен с первым полюсом модели двунаправленной ветви, который соединен с одним входом узла запрета образования замкнутого контура, другой вход которого подключен ко второму полюсу модели двунаправленной ветви, а выход узла запрета образования замкнутого контура соединен с одним входом узла управляв. мых элементов временной задержки,другой вход которого подключен ко входу задания временной задержки модели двунаправленной ветви, а выходы соединены со входами узла управления печатьк соответствующий вход которого подключен ко входу управления печатью двунаправденной ветви, один выход узла управления печатью соединен с регистрационным выходом модели двунаправленной ветви и входом узла регистрации, а другой выход - со входами узла обратной связи и узла разделения, выход которого соединен со вторым полюсом модели двунаправленной ветви.Источники информации, принятые во внимание при экспертизе:1.Васильев В.В. Гибридные модели задач оптимизации, К., Наукова думка, 1974, с. 107-117.2. Авторское свидетельство СССР Р 407345, Мк.Я Об С 7/48, 1973.610126 ставитель Г.Сорокинхред Н, Бабурка Корректор Н.яцемнрск Ред Л,Утехин 3013/39 ЦНИИПИ Г Тираж 826 Подписное дарственного комитета Совета Министро по делам изобретений и открытий Москва, Ж, Раушская наб., д.45