МОДЕЛЬ ДУГИ ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХПУТЕЙ В СЕТЯХ Советский патент 1974 года по МПК G06F15/173 

1

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

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

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

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

На чертеже представлена функциональная схема модели дуги для определения экстремальных путей в сетях. Модель дуги содержит счетчик длины дуги 1, вход задания длины дуги 2, счетчик восстановления длины дуги 3, элемент «И 4, элементы «ИЛИ 5, 6, элементы задержки 7-11, элемент «НЕ 12, элементы «И 13-25, триггер знака 26, триггер блокировки 27, индикатор 28, указывающий на принадлежность данной модели дуги экстремальному пути, полюсы модели дуги 29, 30, вход установки положительного знака длины дуги 31, вход установки отрнцательного знака длины дуги или признака неориентированности данной модели (в случае моделирования ребра) 32, вход блокировки дуги 33, вход разблокировки дуги 34, вход восстановления начальных условий 35, входы тактовых импульсов 36, 37, входы задания ориентации дуги 38-41.

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

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

или в «о в случае неориентированности либо отрицательности длины данной дуги. На входы задания ориентации 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 аналогичных моделей.

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

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

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

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

означает уменьшение его потенциала.

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

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

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

входам, элементы «И 21, 22 открываются по всем управляющим входам, после подачи импульсов по входам блокировки и разблокировки дуги 33, 34. При поступлении импульса на полюс модели дуги 29 (или полюс модели

дуги 30) или на полюсы модели дуги 29 и 30 одновременно он проходит через элемент «И 22 (или через элемент «И 21) или через элементы «И 21, 22 одновременно, попадает на вход элемента задержки 11 (время задержки

равно длительности импульса Гц) и затем перебрасывает триггер блокировки 27 в состояние «О, вызывая запирание элементов «И 21, 22. В любом случае единица прибавляется, а затем вычитается из содержимого счетчика

длины дуги 1. Например, если импульс попадает только на вход модели дуги 29, то он проходит элемент «И 22, устанавливает триггер знака 26 в состояние «1, независимо от его предыдущего состояния, далее этот импульс попадает на вход модели дуги 30, за-5 тем, пройдя элемент задержки 10 (через время Гц), перебрасывает триггер знака 26 в состояние «О, и только после этого импульсы появятся на входах элементов задержки 7 и 8 (с временами задержки в 2Ги) и пройдутю элементы 17, 18, открытые с нулевого выхода триггера знака 26. Поэтому единица сначала прибавится к содержимому счетчика длины дуги 1, а затем, после прохождения элемента задержки 9, вычтется из него. Аналогичное 15 действие произведет импульс, появившийся вначале на входе модели дуги 30, или импульсы, попавшие на входы модели дуги 29, 30 одновременно. Если моделируется неориентированное реб- 20 ро, но содержимое счетчика длины дуги 1 не равно нулю, т. е. еще не достигнуто истинное распределение потенциалов узлов, то элементы «И 15, 16, 19-25, закрыты и, в отличие от предыдущего случая, импульсы со входа 25 модели дуги 29 не проходят на вход модели дуги 30 и наоборот, поэтому содержимое счетчика длины дуги 1 может изменяться. Если моделируется ориентированная дуга и содержимое счетчика длины дуги 1 не равно на зо данном шаге нулю, то элементы «И 13, 14, 19-22, 25 закрыты, открыт либо элемент «И 23, либо элемент «И 24, в зависимости от ориентации дуги. Схема модели дуги для определения экстремальных путей и учетом ука- 35 занных изменений работает аналогично предыдущему случаю. При необходимости получить повторное решение, чтобы не задавать коды в счетчики длины дуг I по входам задания длины дуги 2 40 каждой из моделей дуг, достаточно подать серию импульсов по входам восстановления начальных условий 35 всех моделей дуг исследуемой сети одновременно. Эле.мент «И 4 закроется под действием сигнала с элемента 45 «ИЛИ 5 именно тогда, когда в счетчике длины дуги 1 будет получен заданный ранее код, а в счетчике восстановления длины дуги 3 - нулевой код. Предмет изобретения Модель дуги для определения экстремальпых путей в сетях, содержащая счетчик дли- 55 ны дуги, вход суммирования которого непосредственно соединен со входом задания длины дуги модели дуги и через последовательно включенные первый элемент «И и первый элемент задержки - с первым полюсом моде- 60 ли дуги, а вход вычитания через последовательно соединенные второй элемент задержки, второй элемент «И и третий элемент задерж«и иодключен ко второму полюсу модели дуги, выходы счетчика длины дуги через пер- 65 50 вый элемент «ИЛИ соединены со входом элемента «НЕ и первыми входами третьего и четвертого элементов «И, вторые входы которых подключены к первому входу тактовых импульсов модели дуги, а выходы соединены соответственно с первым и вторым полюсом модели дуги, триггер знака, единичный и нулевой входы которого подключены к соответствующим входам установки знака длины дуги модели дуги непосредственно, а к выходу элемента «НЕ через соответствующие пятый и шестой элементы «И, второй вход первого из которых подключен к первому полюсу модели дуги непосредственно, а второй вход второго подключен ко второму полюсу модели дуги через четвертый элемент задержки, нулевой выход триггера знака через седьмой элемент «И, подключенный вторым входом к выходу первого элемента задержки, соединен со входом второго элемента задержки через восьмой элемент «И, подключенный вторым входом к выходу третьего элемента задержки, соединен со входом суммирования счетчика длины дуги и непосредственно - с третьим входом третьего элемента «И, единичный выход триггера знака соединен со .вторыми входами первого и второго элементов «И и с третьим входом четвертого элемента «И, и индикатор подключенный к выходу элемента «НЕ, отличающийся тем, что, с целью расширения класса решаемых задач, она содержит триггер блокировки, нулевой вход которого подключен ко входу разблокировки дуги модели дуги, девятый элемент «И, первый и второй входы которого подключены к первому и второму входам задания ориентации дуги модели дуги, третий вход соединен со входом блокировки дуги модели дуги, четвертый вход подключен к выходу элемента «НЕ, а выход соединен с единичным входом триггера блокировки, первый и второй входы задания ориентации дуги модели дуги соединены соответственно с четвертыми входами третьего и четвертого элементов «И, десятый и одиннадцатый элементы «И, первые входы которых подключены к единичному выходу триггера блокировки, вторые входы соединены с выходом элемента «НЕ, третьи входы подключены соответственно к первому и второму полюсу модели дуги, а выходы соединены соответственно со вторым и первым полюсом модели дуги, пяTbiii элемент задержки, вход которого подключен к выходам десятого и одиннадцатого элементов «И, а выход соединен с нулевым входом триггера блокировки, двенадцатый и тринадцатый элементы «И, первые входы которых подключены ко второму входу тактовых импульсов модели дуги, вторые входы соединены с выходом элемента «НЕ, третьи входы подключены соответственно к третьему и четвертому входам задания ориентации дуги модели дуги, а выходы соединены соответственно с первым и вторым полюсом модели дуги, счетчик восстановления длины дуги, входы суммирования и вычитания которого соединены соответственно со входами вычитания и суммирования счетчика длины дуги, второй элемент «ИЛИ, подключенный к выходам счетчика восстановления длины дуги, 5

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