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

 

-47Щ; . ". -=. библ)соте кц )). ) „, .

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

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

Республик (») 61()gag

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 040176 (21) 2312462 24 с присоединением заявки № (23) Приоритет (43) Опубликовано 0506.78.Бюллетень №21

2 (51) М. Кл.

Я 06 ст 7/122

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

Сааата Мнннстроа ССВр оо делам нэобретеннй н отнрытнй (®) УДК 681. 335 (088. 8) (45) Дата опубликования описания 110578 (72) Авторы и 3 р 6 p e ) Q ) ) и я Л . В . Ф е д о о в и И . М . С е p r е и ч у к (71) Заявитель

Киевский автомобильно-дорожный институт (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ И ВЫВОДА НА ПЕЧАТЬ

КРАТЧАЙШЕГО ПУТИ ЧЕРЕЗ СЕТЬ С IIEPEMEHHbIMH

ПАРАМЕТРАМИ ВЕТВЕЙ

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

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

Однако это устройство не позволяет моделировать сетевые графики с переменными длительностями работ и оперативно получать информацию о результа- 25 тах моделирования в виде документа.

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

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

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

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

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

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

На фиг.l изображена структурная схема устройства для определения вывода на печать кратчайшего пути через 40 сеть с переменными параметрами ветвей; на фиг.2 - структурная схема модели двунаправленной ветви; на фиг.3функциональная схема модели двунаправленной ветви; на фиг.4-фрагмент город- 45 ской сети и ее кодировка.

Устройство содержит программный задатчик 1 параметров ветвей блок моделей 2 двуна".равленных ветвей, блок

3 формирования знака указателя после- 50 довательности ветвей кратчайшего пути и блок регистрации 4.

Блок моделей 2 двунаправленных ветвей содержит модели 5 двунаправленных ветвей, соединенные согласно топологии ис:".ледуемой сетя, вход б задания временной задержки, вход 7 управлении печатью и регистрационный выход 8.

Модель 5 двунаправленной ветви содержит вход б задания временной задержки„ вход 7 управления печатью,регистрационный вход 8, узел запрета 9 образования замкнутого контура, узел

10 управляемых элементов временной за" держки, узел 11 управления печать!о, узел индикации 12, узел. разделения 13, !

)б узел обратной связи 14 и полюсы 15 и

16.

Узел запрета образования замкнутого контура содержит элемент НЕ 17, элемент И 18, элемент НЕ 19 и элемент

И 20.

Узел 10 управляемых элементов Временной задержки содержит управляемые элементы временной задержки 21 и 22, элементы памяти 23 и 24 и элемент

ИЛИ 25.

Узел управления печатью 11 содержит элементы И 26 и 27, элемент запрета решения 28, элемент разрешения печати 29, элемент HE 30, элемент ИЛИ 31 и элемент памяти 32.

Узел индикации 12 содержит элемент индикации 33.

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

В исходном состоянии с выхода блока регистра 4 . поступает на узел 11 сигнал разрешения печати в виде логической единицы, однако с приходом сигнала иэ блока формирования 3 на блок регистрации 4 на выходе последнего появляется сигнал запрета (инвертируется сигнал разрешения печати) лишь на время. регистрации знака-указателя.

Поясним суть работы блока формирования 3 на примере фрагмента городской сети (фиг.4). Последовательность коI I I 1 1 дов ветвей 1 - 3, 3 — 1, 2 - 4

4 — 2 соответствует знаку-указателю4

I (прямэ), последовательность 1 — 2

2 -3, 3 — 4, 4 - 1 — знаку указа! ! I телю -(влево), а последовательность

1 — 4, 4 — 3 . 3 - 2, 2 — 1 ! ! I I 1 знаку указателю - » (вправо) .

Следовательно, выделенный толстой линией путь между начальным (Н) и ком нечным (К) узлами сети 1 — 3,3 - 2, 2 — 3, 3 — 1 фиксируется в блоке ! ! I регистрации 4 в виде знаков — указателей!,Допустим, требуется определить путь между узлами а и d (фиг.1) . Для этого переключатель режима работы устройства (на чертеже не показан) ставим в положение решение и подаем в узел а запускающий сигнал Х 1 (сигнал решения). этот си!.нал поступает одновременно на входы моделей н 5 и запускает их элементы временной задержки 21 и 22. Пусть временная задержка ветви а6, ойределяемая уровнем напряжения программного задатчика 1 к этому моменту времени;и параметром ветви а Ь, больше задержка чем ветви ас, т.е. 1 < 4 <.Тогда по истечении времени 11 срабатывает элемент временной задержки 21 ветви ас и на выходе модели 5<, т.е. в точке C появляется сигнал !(1, который одновременно поступает на входы моделей 5> и 5б и модели 5 . В этот момент времени по отношенйю к модели 51 действу"

610126. ет условие исключения замкнутого кон= тура (Хд--1 и Х 1), поэтому элеменс ты временной задержки 21 и 22 модели

5 отключены. Допустим, время задержки ветви а В больше суммы времен задержки ветвейас и + 6,т,е. 1 >Ф,+1з,а сумма времен задержки C 6 и 4Й больше чем время задержки ветви cd т.еЯвi+д g, Тогда срабатывают элементы временной задержки 21 и 22 моделей 5 и 5я. По .отношению к моделям 5 и 54 действует условие исключения замкнутого контура. Таким образом, срабатывающие модели 51 5 и 5я образуют дерево кратчайших путей из узла а ко всем осталь. 15 ным узлам.

Для определения и вывода на печать кратчайшего пути из z ðåâà путей перек- лючатель режима работы устройства переводим в положение печать и по- 20 даем в конечный узел d запускающий сигнал печати Х 1. Этот сигнал движется только через сработавшие модели 5 и только в направлении обратном движению сигнала решения. При этом95 сигнал печати Х движется только через модель 56 в точку с, а иэ нее через модель 51 в точку a . Движение сигнала печати управляется узлами 11 управления печатью. 30

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

Модель работает сначала в ре.жиме решения задачи определения дерева кратчайших путей. В этом режиме элементы памяти 23, 24 и 32 устанавливаются кнопкой начальная установка (на чертеже не показана) в 40 нулевое состояние и на элементы И 25 и 26 разрешения печати 29 подается с переключателя сигнал запрета(-Е)в виде логического нуля, который инвертируется элементом 29 н, поступает на эле- 45 мент 28 и разрешает решение задачи.

При-поступлении сигнала (логической единицы) на один иэ полюсов модели срабатывает элемент И 18 и запускает управляемый элемент временной задерж-50 ки 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 (сигнал на полюсе lб равен нулю). Под действием этого сиг нала срабатывает элемент И 20, затем элемент временной задержки 22 (задержка сигнала печати необходима для того, чтобы не срабатызал узел управления печатью 11 последующей модели двунаправленной ветви, принадлежащей кратчайшему пути, за время, прошедшее с момента появления сигнала на выходе элемента разрешения печати 29 до момента срабатывания блока регистрации 4.

Сигнал с выхода элемента задержки 22 поступает на элемент И 26, на остальных входах которого имеются сигналы в виде логической единицы. Выходной сигнал сработавшего элемента И 26 через элемент ИЛИ 31 переводит элемент памяти 32 в единичное состояние. Под действие появившейся на выходе этого элемента 32 логической единицы срабатывает элемент разрешения печати 29 выходной сигнал которого поступает на блок формирования 3, а также на элемент индикации 33 ветви.

Для возвращения модели двунаправленной ветви в начальное состояние кнопкой начальная установка и сброс устанавливают соответственно элементы 23, 24 и 32 в нулевое состояние, а переключатель в положение решение .

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

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

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

Источники информации, принятые во внимание при экспертизе:

1.Васильев В.В. Гибридные модели задач оптимизации, К., Наукова думка, 1974, с. 107-117.

2. Авторское свидетельство СССР

Р 407345, Мк.Я Об С 7/48, 1973.

610126

Фиг. 4

Составитель Г.Сорокин

Техред Н. Бабурка КорректоР Н.Яцемирская

Редактор л.утехина

Заказ 3013/39 Тираж 826 Подписное

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

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

Филиал ППП Патент, г. Ужгород, ул, Проектная, 4