Устройство для моделирования сетевого графика

ОПИСАН И ЕИЗОБРЕТЕНИЯК ПАТЕНТУ Союз Советских Социалистицеских Республик,51268, Франция972, БюллетеньКомитет по делам зооретений и открыт при Совете Министре СССРДК 681.3,001.57(088,8 ата опубликования описания 2.111.1 Авторы изобретения Иност н, Жак Бертелем(Фра Иностранн аль дЭтюд э де Кранцыи и Пьер Жерменнция)ая фирмаонстрюксьон де Мция) к С не Б аявите отор дАвиасьон осьете Наси ТРОЙСТВО МОДЕЛИРОВАНИЯ СЕТЕ 1ится к аналоговой вычи двух дуг 14 и 15,узлов РА, РМ и Р В - конечный, а М Каждая модель 5 52 и 53 и три вхо имеет два выхода ветственно со вхо торый данная дуг схему ИЛИ 1 б 0 узла, из которого логическую схему Е 4, Е 5, Еб и Е 7.Входы Е 4 и Е 7 соединены соответственно с 15 выходами 51 и 52 модели узла, из которогодуга выходит, а входы Еб и Еб соединены соответственно с выходом 18 генератора импульсов 19 и с выходом 53 модели того жеузла.20 Кроме того, входы ЕЗ моделей узлов соединены со вторым выходом 20 генератора импульсов 19.В случае, когда пз узлов А, В и М выходяти другие дуги, пх модели подсоединяются к 25 моделям звеньев через дополнительные зажимы 21, 22 и 23.Модели дополнительных дуг, входящих вузлы А, В и М, соединяются своими выходами 54 с пх модслямп через входы 24 схем 30 ИЛИ 1 б. Изобретение относслительной технике.Известны устройства для нахождения оптимального пути, осуществляющие последовательное продвижение импульсов по сети, содержащей модели дуг и узлов, с фиксацией первого импульса, поступающего в модель узла от всех моделей входящих в него дуг и с индикацией кратчайшего пути,Однако эти устройства не позволяют определить минимальную траекторию пути в сетевом графике.Предложенное устройство в отличие от известных устройств для моделирования сетевого графика позволяет решать более широкий круг задач, т. е. позволяет находить оптимальные пути для случая нескольких исходных и нескольких конечных пунктов, одного исходного и одного конечного, решать задачу нахождения пар оптимально связанных исходных и конечных пунктов, а также производить индикацию найденных оптимальных путей по заданной программе.На фиг. 1 показан вариант сетевого графика с узлами Л 1 - У 10 и направленными дугами 1 - 13, соединяющими их.Устройство для моделирования сетевого графика содержит модели узлов и модели дуг, в которые входит и схема индикации.На фиг. 2 дана схема соединения моделей соединяющих модели трех В, где А - исходный узел, - промежуточный,узла имеет три выхода 51,да Е 1, Е 2, ЕЗ. Модель дуги54 и 55, соединенных соотдом Е 1 модели узла, в ковходит через логическую и со входом Е 2 моделиданная дуга выходит через ИЛИ 17 и четыре входа50 55 60 65 На фиг. 3 дана схема модели узла, Модель содержит двустабильный элемент 25, с выходом 53 и входом, соединенным с логической схемой И 26 с двумя входами Е 2 и ЕЗ, и усилитель 27 со входом Е 1 и выходом Ь 1. Выход двустабильного элемента 25 имеет ответвление 52.На фиг. 4 и о дана схема модели дуги. Причем на фиг. 4 показаны схема модели дуги с длиной (весом) 1 и схема индикации дуги, Схема содержит двустабильный элемент 28 с выходом 56, вход которой соединен с логической схемой И 29 на пять входов (два из которых обозначены Е 5 и Еб), инвертор 30, усилитель 31, вход 32 которого соединен со схемой, изображенной на фиг. 5 (когда длина дуги отлична от 1), и усилитель 33 со входом 34, по выходу соединенный с одним из входов вентильной схемы 29. Схема И 35 с выходом 54, три входа которой соединены соответственпо с выходом двустабильного элемента 28, со входом Е 4 и с входным зажимом 36 через усилитель 37, представляет схему индикации дуги.Схема, изображенная на фиг. 5, включает в себя двоичный счетчик 38, вход которого соединен со схемой И 39. Два входа, 40 и 41, последней могут быть соединены с выходом 53 модели узла, в который дуга входит, и с выходом 18 генератора импульсов 19. Выход счетчика 38 соединен с и входами схемы декодирования 42, выход 43 которой может быть соединен со входом 32 модели дуги, длина которой отлична от единицы. Устройство работает следующим образом.Допустим, что,в схеме, показанной на фиг. 2, длины обеих дуг равны 1, т. е.на вхо.ды 32 и 34 моделей дуг подаются сигналы разрешения. Путь, ведущий из исходной точ.ки А в конечную точку В, является искомым .путем и проходит через промежуточную точку М,Исходный узел фиксируется путем приложения постоянного разрешающего сигнала на вход Е 1 модели узла РА, а фиксация конечной точки производится путем приложения постоянного разрешающего сигнала ко -входу Е 2 модели узла РВ.В течение всего времени работы генератор .импульсов 19 выдает попеременно два сигнала; Т 1=.,на выход 20 и Т 2 - на выход 18. В исходный момент с выходов 52 моделей узлов и с выходов 55 моделей дуг снимается сигнал запрета,. При пуске устройства к моделям узлов подходит первый сигнал Т 1. Этот сигнал проходит на выход схемы И 26 лишь модели узла. РВ, так как на входы Е 2 других моделей узлов поступает сигнал запрета от двустабильных элементов 28.Двустабильный элемент 25 модели РВ переходит в противоположное состояние и выдает сигнал разрешения на один из входов схемы 29 модели дуги 15 по входу Еб. 5 10 15 20 25 30 35 40 45 11 ри поступлении сигнала Т 2 на схемы 29 моделей дуг лишь схема 29 модели дуги 15 пропускает его на выход, так как на входы Еб остальных моделей дуг поступает сигнал запрета от элементов 25. Двустабильный элемент 26 модели 15 таким образом переводится первым сигналом Т 2 в противоположное состояние: с выхода 55 через вход Е 2 на схему 26 модели узла РМ поступает сигнал разрешения.При поступлении второго сигнала Т 1 схема 26 модели РМ оказывается открытой и переводит элемент 25 модели РМ в противоположное состояние: на выход 53, а следовательно, и на вход Еб схемы 29 модели дуги 14 поступает сигнал разрешения.Последовательность операций при прохождении от узла М к узлу А та же, что и при прохождении от узла В к узлу М.При,появлении сигнала разрешения на выходе 55 модели 14 схема И 35 этой модели оказывается открытой (при условии, что на вход 36 модели поступает сигнал разрешения) для сигнала фиксации начального узла, который подается на вход Е 1 модели РА и проходит на вход Е 4 схемы 35 модели 14 через усилитель 27 модели РА.На выходе схемы 35 модели 14 появляется сигнал разрешения, который проходит по усилителям 27 и схемам 35 моделей всех узлов и дуг, оказавшихся на отмеченном (оптимальном) пути (например, на фиг. 2 - моделей РА, 14, РМ, 15, РВ), и ипдицирует этот путь.В некоторых случаях целесообразно обозначить этот путь постепенно, шаг за шагом, или в заданном ритме, или после последовательных заданий, вводимых в устройство,На фиг. б дана схема индикации, состоящая из схемы И 44 с двумя входами 45, 4 Ь, управляющая первым двустабильным элементом 47, выход которого соединен с одним из двух входов 48 и 49 второй схемы И 50, и второго двустабильного элемента 51, вход которого соединен с выходом схемы 50, а выход подсоединен к выходу 51. Сигналы, подаваемые последовательно по заданной программе на входы с 11, О 2 и 36, позволяют получить последовательное продвижение сигнала индикации по найденному оптимальному пути от исходного узла к конечному.В случае если длина (вес) дуги не равна 1, ко входу 32 модели дуги подсоединяется выходом 43 схема, показанная на фиг, 5.В этом случае на выходе схемы И 29 соответствующей модели дуги появляется сигнал лишь после того числа импульсов Т 2, которое закодировано вентильной схемой 42, входами соединенной с разрядами счетчика 38, на вход которого поступают импульсы Т 2 через схему И 39 при наличии сигнала разрешения на входе 40, т. е. при фиксации сигнала разрешения на входе 53 модели узла, в который данная дуга входит, 326788Предмет изобретения 1. Устройство для моделирования сетевого графика, содержащее модели узлов и модели дуг графика, а также схему индикации оптп мального пути, состоящее из логических схем И, ИЛИ, двустабильных элементов, двоичных счетчиков, схем декодирования, усилителей, инвертора и генератора импульсов, отличаюиееся тем, что, с целью расширения 10 класса решаемых задач, в нем выход двухвходовой схемы И модели узла соединен со входом двустабильного элемента этой же модели, выход которого подсоединен к одному из входов пятивходовой схемы И модели, 15 входящей в данный узел дуги, причем другой вход пятивходовой схемы И соединен с выходом инвертора этой модели дуги, ее трет:и вход соединен с выходом усилителя сигнала удаления дуги из сетевого графика, четвер тый вход - с выходом усилителя, вход которого соединен через схему декодирования со счетчиком данной модели дуги, а пятый вход так же, как и пятые входы соответствующих схем И всех моделей дуг, соединен с одним 25 выходом генератора импульсов устройства, второй выход которого соединен с одним из входов двухвходовых схем И всех моделей узлов, выход пятивходовой схемы И соединен со входом двустабильного элемента этой 30 же модели дуги, выход которого соединен со вторым входом двухвходовой схсмы И модели узла, из которого дачная дуга выходит, вход пнвертора модели дуги соединен с выходом двустабильного элемента модели узла, из которого данная дуга выходит, выход двустабильного элемента модели дуги сосд.шен со вторым входом двухвходовоп схемы И модели узла, из которого данная дуга выходит.2. Устройство по п. 1, огличаицеесл тем, что схема индикации узла содержит двухвходовые схемы И и двустабпльныс схемы, причем выход первой схемы И соединен со входом первой двустабильпой схемы, выход которой соединен с одним пз входов второй схемы И, выход последней соединен со входом второй двустабильпой схемы, а схема индикации дуги состоит пз усилителя и трехвходовой схемы И, трп входа которой соединены соответственно с выходом двустабильного элемента модели данной дуги с выходом второго двустабпльного элемента схемы индикации узла, пз которого данная дуга выходит, и с выходом усилителя данной схемы индикации, а выход трехвходовой схемы И соединен с одним из входов первой двухвходовой схемы И, входящей в состав схемы индикации узла, в который данная дуга входит.326788 Е 7 52 34 иг 5 Л. Утехина да аказ 527/16 Изд.115 Тираж 448 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5 ипография пунова, 2 ставитель Л Дмитриевхред Л, Богданова б 5 Корректоры; Т, Бабакина и Н. Шевченко