Модель дуги для определения экстремальныхпутей в сетях

 

ОП ИСА НИ Е

ИЗОБРЕТЕНИЯ

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

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

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

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

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

Дата опубликования описания 20.11.74 (51) М, Кл. G 06f 15/20

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

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

А. А. Илюхин, А. П. Киселев и А. М. Плахотишин (71) Заявитель

Московский ордена Трудового Красного Знамени инженернофизический институт (54) МОДЕЛЬ ДУГИ ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ

ПУТЕЙ В СЕТЯХ

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

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

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

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

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

На чертеже представлена функциональная схема модели дуги для определения экстремальных путей в сетях. Модель дуги содержит счетчик длины дуги 1, вход задания длины дуги 2, счетчик восстановления длины дуги 3, элемент «И» 4, элементы «ИЛИ» 5, 6, элементы задержки 7 — 11, элемент «НЕ» 12, элементы «И» 13 — 25, триггер знака 26, триг5 гер блокировки 27, индикатор 28, указывающий на принадлежность данной модели дуги экстремальному пути, полюсы модели дуги

29, 30, вход установки положительного знака длины дуги 31, вход установки отрицательно10 го знака длины дуги или признака неориентированности данной модели (в случае моделирования ребра) 32, вход блокировки дуги

33, вход разблокировки дуги 34, вход восстановления начальных условий 35, входы такто15 BbIx импульсов 36, 37, входы задания ориентации дуги 38 — 41.

Модель дуги для определения экстремальных путей в сетях работает следующим образом.

20 Перед началом процесса поиска экстремального (кратчайшего или критического) пути полюсы моделей дуг 29, 30 соединяют между собой в соответствии с топологией исследуемой сети, причем на длины дуг сети не на25 кладывается ограничение пх строгой положительности. Затем по входу задания длины каждой нз дуг 2 подают серию импульсов, число которых равно длине моделируемой дуги, триггер знака 26 устанавливают в состоя30 ние «1» в случае положительности длины дуги

432508

3 или в «О» в случае неориентированности либо отрицательности длины данной дуги. На входы задания ориентации 38 — 41 поступают комбинации постоянных напряжений, соотвегствую- щих уровням логических «О» и «1», причем если моделируется неориентированное ребро, то на входах задания ориентации 38, 39 устанавливают «1», а на входах задания ориентации

40, 41 — «О», если моделируется дуга, направленная от полюса модели дуги 29 к полюсу модели дуги 30, то на входах задания ориентации 39, 40 — «1», а на входах задания ориентации 38, 41 — «О» и, наконец, если моделируется дуга, направленная наоборот, то на входах задания ориентации 38, 41 †«1», а на входах задания ориентации 39, 40 †«О».

Процесс поиска кратчайшего пути на сети, составленной из таких моделей — дуг, осуществляется синхронной подачей сигналов по входам тактовых импульсов 37 и с удвоенной частотой — по входам тактовых импульсов 36 всех моделей дуг до тех пор, пока на четном такте во всех узлах исследуемой сети (на всех полюсах моделей дуг 30) одновременно не появятся тактовые импульсы, а на следующем нечетном такте ни в один узел сети тактовый импульс не придет. Перед моментом поступления сигнала по входу гактовых импульсов 36, т, е. перед каждым новым шагом процесса, по входу разблокировки дуги 34 также подается импульс, а через время переброса триггера блокировки 27 импульс поступает по входу блокировки дуги 33, в результате чего триггер блокировки 27 установится в состояние «1» только в том случае, когда данное ребро сети неориентировано и уже определилась на данном и последующих шагах его принадлежность дереву кр атчайших путей, которая в схеме модели дуги характеризуется нуЛевым содержимым счетчика длины дуги 1 и, следовательно, низким уровнем напряжения на выходе элемента «ИЛИ» 6, высоким — на выходе элемента «НЕ» 12 и загоранием индикатора 28. При этом сигналы, поступающие на входы тактовых импульсов 36, 37, не пройдут ни один из элементов «И» 19, 20 и 23, 24, а импульс, появившийся на каком-либо полюсе модели дуги 29 или 30, одновременно пройдет либо элемент «И» 21, либо элемент «И»

22, либо оба их, так что в рассмотренном случае модель неориентированного ребра как бы

«стягивается» в точку и не может изменить состояние инцидентных полюсов модели дуги

29, 30 аналогичных моделей.

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

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

При реализации нечетного шага (понижение) процесса определения кратчайшего пути импульс подается по входу тактовых импульсов 36, а при реализации четного шага (повышение) — по входам тактовых импульсов 36 и 37 одновременно. В узел сети, из которого имеются кратчайший путь, импульс на четных шагах вычислительного процесса подается всегда.

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

Функционирование модели дуги для определения экстремальных путей на каждом такте зависит от совокупности признаков, определяемых ориентацией дуги и содержимым счетчика длины дуги 1. Если на некотором шаге содержимое счетчика длины дуги 1 стало равным «О» для неориентированного ребра, то элементы «И» 15, 16, 19, 20, 23 и 24 закрыты, элемент «И» 25 открыт по всем управляющим входам, элементы «И» 21, 22 открываются по всем управляющим входам, после подачи импульсов по входам блокировки и разблокировки дуги ЗЗ, 34. При поступлении импульса на полюс модели дуги 29 (или полюс модели дуги 30) или на полюсы модели дуги 29 и 30 одновременно он проходит через элемент «И»

22 (или через элемент «И» 21) или через элементы «И» 21, 22 одновременно, попадает на вход элемента задержки 11 (время задержки равно длительности импульса Т„) и затем перебрасывает триггер блокировки 27 в состояние «О», вызывая запирание элементов «И»

21, 22. В любом случае единица прибавляется, а затем вычитается из содержимого счетчика длины дуги 1. Например, если импульс попа432508 дает только на вход модели дуги 29, то он проходит элемент «И» 22, устанавливает триггер знака 26 в состояние «1», независимо от

его предыдущего состояния, далее этот импульс попадает на вход модели дуги 30, затем, пройдя элемент задержки 10 (через время Т„), перебрасывает триггер знака 26 в состояние «О», и только после этого импульсы появятся на входах элементов задержки 7 и 8 (с временами задержки в 2Т,.,) и пройдут элементы 17, 18, открытые с нулевого выхода триггера знака 26. Поэтому единица сначала прибавится к содержимому счетчика длины дуги 1, а затем, после прохождения элемента задержки 9, вычтется из него. Аналогичное действие произведет импульс, появившийся вначале на входе модели дуги 30, или импульсы, попавшие на входы модели дуги 29, 30 одновременно.

Если моделируется неориентированное ребро, но содержимое счетчика длины дуги 1 не равно нулю, т. е. еще не достигнуто истинное распределение потенциалов узлов, то элементы «И» 15, 16, 19 — 25, закрыты и, в отличие от предыдущего случая, импульсы со входа модели дуги 29 не проходят на вход модели дуги 30 и наоборот, поэтому содержимое счетчика длины дуги 1 может изменяться. Если моделируется ориентированная дуга и содержимое счетчика длины дуги 1 не равно на данном шаге нулю, то элементы «И» 13, 14, 19 — 22, 25 закрыты, открыт либо элемент «И»

23, либо элемент «И» 24, в зависимости от ориентации дуги. Схема модели дуги для определения экстремальных путей и учетом указанных изменений работает аналогично предыдущему случаю.

При необходимости получить повторное решение, чтобы не задавать коды в счетчики длины дуг 1 по входам задания длины дуги 2 каждой из моделей дуг, достаточно подать серию импульсов по входам восстановления начальных условий 35 всех моделей дуг исследуемой сети одновременно. Элемент «И» 4 закроется под действием сигнала с элемента

«ИЛИ» 5 именно тогда, когда в счетчике длины дуги 1 будет получен заданный ранее код, а в счетчике восстановления длины дуги

3 — нулевой код.

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

Модель дуги для определения экстремальных путей в сетях, содержащая счетчик длины дуги, вход суммирования которого непосредственно соединен со входом задания длины дуги модели дуги и через последовательно включенныс первый элемент «И» и первый элемент задержки — с первым полюсом модели дуги, а вход вычитания через последовательно соединенные второй элемент задержки, второй элемент «И» и третий элемент задержки подключен ко второму полюсу модели дуги, выходы счетчика длины дуги через пер5

60 б5 вый элемент «ИЛИ» соединены со входом элемента «НЕ» и первыми входами третьего и четвертого элементов «И», вторые входы которых подключены к первому входу тактовых импульсов модели дуги, а выходы соединены соответственно с первым и вторым полюсом модели дуги, триггер знака, единичный и нулевой входы которого подключены к соответствующим входам установки знака длины дуги модели дуги непосредственно, а к выходу элемента «НЕ» через соответствующие пятый и шестой элементы «И», второй вход первого из которых подключен к первому полюсу модели дуги непосредственно, а второй вход второго подключен ко второму полюсу модели дуги через четвертый элемент задержки, нулевой выход триггера знака через седьмой элемент «И», подключенный вторым входом к выходу первого элемента задержки, соединен со входом второго элемента задержки через восьмой элемент «И», подключенный вторым входом к выходу третьего элемента задержки, соединен со входом суммирования счетчика длины дуги и непосредственно — с третьим входом третьего элемента «И», единичный выход триггера знака соединен со вторыми входами первого и второго элементов «И» и с третьим входом четвертого элемента «И», и индикатор подключенный к выходу элемента «НЕ», отличающийся тем, что, с целью расширения класса решаемых задач, она содержит триггер блокировки, нулевой вход которого подключен ко входу разблокировки дуги модели дуги, девятый элемент «И», первый и второй входы которого подключены к первому и второму входам задания ориентации дуги модели дуги, третий вход соединен со входом блокировки дуги модели дуги, четвертый вход подключен к выходу элемента «НЕ», а выход соединен с единичным входом триггера блокировки, первый и второй входы задания ориентации дуги модели дуги соединены соответственно с четвертыми входами третьего и четвертого элементов «И», десятый и одиннадцатый элементы

«И», первые входы которых подключены к единичному выходу триггера блокировки, вторые входы соединены с выходом элемента

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

32

Составитель А, Илюхин

Техред Л. богданова

Корректор Л. Орлова

Редактор Л. Цветкова

Заказ 3524/16 Изд. № 1738 Тираж 624 Подписное

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

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

Типография, пр. Сапунова, 2 ды суммирования и вычитания которого соединены соответственно со входами вычитания и суммирования счетчика длины дуги, второй элемент «ИЛИ», подключенный к выходам счетчика восстановления длины дуги, и четырнадцатый элемент «И», входь1 которого подключены к выходам второго элемента

«ИЛИ» и входу восстановления начальных условий модели дуги, а выход соединен со

5 входом суммирования счетчика длины дуги.