Устройство определения и вывода на печать кратчайшего пути через сеть с переменными параметрами ветвей Советский патент 1978 года по МПК G06G7/122 

включенный между регистраицонным выходом блока моделей двунаправленных ветвей и входом блока регистрации, выход которого соединен со входом управления печатью блока моделей двунаправленных ветвей. Последний соединен с одноименными входами моделей двунаправленных ветвей. Модель двунаправленной ветви содержит узел запрета образования замкнутого контура, узел управляемых элементов временной задержки, узел управления печатью, узел индикации, узел разделения и узел обратной связи, выход которого соединен с первым полюсом модели двунаправленной ветви, который соединен с одним входом узла запрета образования замкнутого контура, другой вход которого подключен ко второму полюсу модели двунаправленной ветви, Выход узла запрета образования замкнутого контура соединен с одним входом узла управляемых элементов временной задержки, другой вход которого подключен ко входу задания временной задержки модели двунаправленной ветви, а выходы соединены со входами узла управления печатью, соответствующий вход которого подключен ко входу управления печатью модели, двунаправленной ветви Один выход узла управления печатью соединен с регистрационным выходом модели двунаправленной ветви и входом узла регистрации, а другой - со входами узла обратной связи и узла разделения, выход которого соединен со вто, рым полюсом модели двунаправленной ветви. На фиг.1 изображена структурная схема устройства для определения вывода на печать кратчайшего пути через сеть с переменными параметрами ветвей; на фиг.2 - структурная схема модели двунаправленной ветви; на фиг.Зфункциональная схема модели двунаправ ленной ветви; на фиг.4-фрагмент городской сети и ее кодировка. Устройство содержит программный задатчик 1 параметров ветвей блок моделей 2 двуна-правленных ветвей, блок 3 формирования знака указателя после довательности ветвей кратчайшего пути и блок регистрации 4. БЛОК моделей 2 двунаправленных вет вей содержит модели 5 двунаправленных ветвей, соединенные согласно топологии иесзтедуемой сети, вход б задания временнвй задержки, вход 7 управления печатью и регистрационный выход 8. Модель 5 двунаправленной ветви содержит нгЕод 6 задания временной задержки-,, вход 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, элемент НЕ 30, элемент ИЛИ 31 и элемент памяти 32. Узел индикации 12 содержит элемент индикации 33. Устройство работает следующим образом. В исходном состоянии с выхода блока регистра 4 . поступает на узел 11 сигнал разрешения печати в виде логической единицы, однако с приходом сигнала из блока формирования 3 на блок регистрации 4 на выходе последнего появляется сигнал запрета (инвертируется сигнал разрешения печати) лишь на время, регистрации знака-указателя. Поясним суть работы блока формирования 3 на примере фрагмента городской сети (фиг.4}. Последовательность кодов ветвей l - З , З - l , 2 - 4, 4 - 2 соответствует знаку-указателю (прямо), последовательность 1 - 2 , 2 -з, з - 4 4 - l- знаку указателю-в-(влево) , а последовательность 1 - 4, 4 - 3 . 3 - 2, 2 - 1 знаку указателю (вправо) . Следовательно, выделенный толстой линией путь между начальным (Н) и ком нечным (К) узлами сети l- З,з - 2, 2 - 3, 3 - 1 фиксируется в блоке регистрации 4 в виде знаков - указателей},- -о- , f , Допустим, требуется определить путь между узлами а и d (фиг.1). Для этого переключатель режима работы устройства (на чертеже не показан) ставим в положение решение и подаем в узел а запускающий сигнал Хи1 (сигнал решения). Этот сигнал поступает одновременно на входы моделей 6 и Sj и запускает их элементы временной задержки 21 и 22. Пусть временная задержка ветви аб, определяемая уровнем напряжения программного задатчика 1 к этому моменту времени ; и параметром ветви а b , больше задержка чем ветви ас, т.е. i j т-4. . Тогда по истечении времени ij срабатывает элемент временной задержки 21 ветви ас и на выходе модели 5j , т.е. в точке С появляется сигнал X I, который одновременно поступает на входы моделей 5 и Sg и модели 5. В этот момент времени по отношению к модели 5 действует условие исключения замкнутого контура ( и X 1), поэтому элементы временной задержки 21 и 22 модели 5j отключены. Допустим, время задержки ветви а 6 больше суммы времен задержки ветвей ас и с в,т,е. ti t -t-t3 су ма времен задержкисАи -6at больше че время Зёщержки ветви cd т.е.а-Нд;. Тогда срабатывают элементы временной задержки 21 и 22 моделей 5 и 5. По отношению к моделям Ь и 5 действует условие исключения замкнутого контура. Таким образом, срабатывающие модели 5 БЗ и 55 образуют дерево кратчайших путей из узла а ко всем осталь ; ным узлам. ; Для определения и вывода на печать i кратчайшего пути из -грева путей пере лючатель режима работы устройства переводим в положение печать и подаем в конечный узел d запускающий сигналпечати Х 1. Этот сигнал движется только через сработавшие модели 5 и только в направлении обратном движению сигнала решения. При это сигнал печати Х движется только через модель 55 в точку с, а из нее через модель 5j в точку а . Движение сигнала печати управляется узлами 11 управления печатью. Сигналы с моделей двунаправленных ветвей, принадлежащих только кратчайшему пути, поступают на блок 3 формирования знака-указателя. Модель работает сначала в ре.жиме решения задачи определения дерева кратчайших путей. В этом режиме элементы памяти 23, 24 и 32 уста навливаются кнопкой начальная уста новка ( на чертеже не показана) в . нулевое состояние и на элементы и 25 и 26 разрешения печати 29 подается с переключателя сигнал запрета(-Е)в вид логического нуля,который инвертируется элементом 29 и, поступает на элемент 28 и разрешает решение задачи. При поступлении сигнала (логической единицы) на один из полюсов модели срабатывает элемент И 18 и запускает управляемый элемент временной задерж ки 21, который срабатывает по истечении времени, пропорционального параметру ветви. При этом на выходе элемента 21 появляется сигнал в виде логической единицы, который поступает на элементы 23, 25 и 27. Под действием этого сигнала переводится в единич ное состояние элемент памяти 23, выхо ходной сигнал которого поступает на элемент И 26 обратного направления ветви и подготавливает его для режима Печати, а также срабатывает элемент ИЛИ 25, а затем элемент 28, выходной сигнал которого через элемент .ИЛИ 31 поступает на элемент памяти 32 и устанавливает его в единичное соетоянйе. Выходной сигнал элемента памяти 32 через узел 13 поступает на полюс 16, т.е. на прямые входы последующих моделей двунаправленных ветвей, подключенных к полюсу 16. Поскольку на по.гаосах 15 и 16 присутствует единичные сигналы, то срабатывает узел 9 запрета образования замкнутого контура, т.е. на выходе элемента И 18 появляется логический нуль, который возвращает элемент задержки 21 в исходное состояние (нулевое). В режиме печати и индикации краччайшего пути кнопкой сброс эле-1 мент памяти 32 сбрасывает в нулевое состояние (на полюсах 15 и 16 сигнал X JJ 0), а переключатель режима работы ставим в положение печать. При этомна элементы 26, 27 и 29 подается сигнал разрешения, который инвертирую ется и в виде запрета поступает на элемент 28. Запуск модели двунаправленной ветви в режиме печати производим подачей сигнала печати в виде логической един,цины на полюс 16 (сигнал на полюсе 16 равен нулю). Под действием этого сигнала срабатывает элемент И 20, затем элемент временной задержки 22 (задержка сигнала печати необходима для того, чтобы не срабатывал узел управления печатью 11 последующей модели двунаправленной ветви, принадлежащей кратчайшему пути, за время, прошедшее с момента появления сигнала на выходе элемента разрешения печати 29 до момента срабатывания блока регистрации 4. Сигнал с выхода элемента задержки 22 поступает на элемент И 26, на остальных входах которого имеются сигналы в виде логической единицы. Выходной сигнал сработавшего элемента И 26 через элемент ИЛИ 31 переводит элемент памяти 32 в единичное состояние. Под действие появившейся на выходе этого элемента 32 логической единицы срабатывает элемент разрешения печати 29 выходной сигнал которого поступает на блок формирования 3, а также на элемент индикации 33 ветви. Для возвращения модели двунаправленной ветви в начальное состояние кнопкой начальная установка и сброс устанавливают соответственно элементы 23, 24 и 32 в нулевое состояние, а переключатель в положение решение. Формула изобретения 1. Устройство для определения и вывода на печать кратчайшего пути через сеть с переменными параметрами ветвей, содержащее программный задатчик параметров ветвей, выход которого соединен со входом задания временной задержки блока моделей двунаправленных ветвей, в котором модели двунаправлен ных ветвей соединены между собой полю сами согласно топологии исследуемой сети, входы задания временной задержки моделей двунаправленных ветвей под ключены к одноименному входу блока моделей двунаправленных ветвей, регистрационный выход которого соединен с одноименными выходами моделей двунаправленных ветвей, и блок регистрации, отличаюи-еес я тем, что с целью расширения функциональных воз можностейустройства за счет оператив ного документирования последовательности ветвей кратчайшего пути, оно содержит блок формирования знака-указателя последовательности ветвей крат чайшего .пути, включенный между регист рационным выходом блока моделей двунаправленных ветвей и входом блока регистрации, выход которого соединен со входом управления печатью блока моделей двунаправ-ленных ветвей, который соединен с одноименными входами моделей двунаправленных ветвей. 2. Устройство по п.1, о т л и ч аю щ е е с я тем, что модель двунаправ ленной ветви содержит узел запрета образования замкнутого контура, узел управляемых элементов временной задержки, узел управления печатью, узел индикации, узел разделения и узел обратной связи, выход которого соединен с первым полюсом модели двунаправленной ветви, который соединен с одним входом узла запрета образования замкнутого контура, другой вход которого подключен ко второму полюсу модели двунаправленной ветви, а выход узла запрета образования замкнутого контура соединен с одним входом узла управляемых элементов временной задержки,другой вход которого подключен ко входу . задания временной задержки модели двунаправленной ветви, а выходы соединены со в ходами узла управления печатьк), соответствующий вход которого подключен ко входу управления печатью двунаправденной ветви, один выход узла управления печатью соединен с регистрационным выходом модели двунаправленной ветви и входом узла регистрации, а другой выход - со входами узла обратной связи и узла разделения, выход которого соединен со вторым полюсом модели двунаправленной ветви. Источники информации, принятые во внимание при экспертизе: 1.Васильев В.В. Гибридные модели задач оптимизации. К,, Наукова думка , 1974, с. 107-117. 2. Авторское свидетельство СССР № 407345 Мк.( 06 G, 7/48, 1973.

ir±J Ш 3-1 tf- 4| . 1 j -f