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

 

ОПИСАН И Е

ИЗОБРЕТЕНИЯ

К ПАТЕНТУ

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

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

Республик

Зависимый от патента №

М. Кл. G 06g 7, 48

Заявлено 25.11.1967 (№ 1136712/18-24) Приоритет 26.II.1966, N 51268, Франция

Опубликовано 19Л.1972. Бюллетень ¹ 4

Комитет по делам изобретений H открытий при Совете Министров

СССР

УДК 681.3.001.57(088.8) Дата опубликования описания 2.111 1972

Авторы изобретения

Иностранцы

Жак Сован, Жак Бертелеми и Пьер Жермен Рене Буе (Франция) Иностранная фирма

«Сосьете Насиональ д Этюд э де Констрюксьон де Мотор д Авиасьонэ (Франция) Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА

Изобретение относится к аналоговой вычислительной технике.

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

Однако эти устройства не позволяют определить минимальную траекторию пути в сетевом графике.

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

На фиг. 1 показан вариант сетевого графика с узлами A 1 — IV10 и направленными дугами 1 — 13, соединяющими их.

Устройство для моделирования сетевого графика содержит модели узлов и модели дуг, в которые входит и схема индикации.

На фиг. 2 дана схема соединения моделей двух дуг 14» 15, соединяющих модели трех узлов РА, РМ и РВ, где А — исходный узел,  — конечный, а М вЂ” промежуточный, Каждая модель узла имеет три выхода Sl, 5 52 и S8 и три входа Еl, Е2, Е3. Модель дуги имеет два выхода 54 и 55, соединенных соответственно со входом Еl модели узла, в который данная дуга входит через логическую схему «ИЛИ» lб, и со входом Е2 модели

10 узла, из которого данная дуга выходит через логическую схему «ИЛИ» 17 и четыре входа

Е4, Еб, Еб и Е7.

Входы Е4 и Е7 соединены соответственно с

15 выходами Sl и 52 модели узла, из которого дуга выходит, а входы Еб и Еб соединены соответственно с выходом 18 генератора импульсов 19 и с выходом S8 модели того же узла.

20 Кроме того, входы Е8 моделей узлов соединены со вторым выходом 20 генератора импульсов 19.

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

25 моделям звеньев через дополнительные зажимы 21, 22 и 28.

Модели дополнительных дуг, входящих в узлы А, В и М, соединяются своими выходами 54 с пх модслямп через входы 24 схем

З0 «ИЛИ» lб.

326788

На фиг. 3 дана схема модели узла. Модель содержит двустабильный элемент 25, с выходом 58 и входом, соединенным с логической схемой «И» 26 с двумя входами Е2 и ЕЗ, и усилитель 27 со входом Еl и выходом Sl. Выход двустабильного элемента 25 имеет ответвление 52.

1-1а фиг. 4 и 5 дана схема модели дуги. Причем на фиг. 4 показаны схема модели дуги с длиной (весом) 1 и схема индикации дуги.

Схема содержит двустабильный элемент 28 с выходом S5, вход которой соединен с логической схемой «И» 29 на .пять входов (два из которых обозначены Е5 и Еб), инвертор 80, усилитель 81, вход 82 которого соединен со схемой, изображенной на фиг. 5 (когда длина дуги отлична от 1), и усилитель 38 со входом 84, по выходу соединенный с одним из входов вентильной схемы 29. Схема «И» 85 с выходом 54, три входа которой соединены соответственно с выходом двустабильного элемента 28, со входом Е4 и с входным зажимом 36 через усилитель 87, представляет схему индикации дуги.

Схема, изображенная на фиг. 5, включает в себя двоичный счетчик 38, вход которого соединен со схемой «И» 39. Два входа, 40 и 41, последней могут быть соединены с выходом

58 модели узла, в который дуга входит, и с выходом 18 генератора импульсов 19. Выход счетчика 88 соединен с и входами схемы декодирования 42, выход 48 которой может быть соединен со входом 82 модели дуги, длина которой отлична от единицы.

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

Допустим, что,в схеме, показанной на фиг. 2, длины обеих дуг равны 1, т. е. на входы 82 и 84 моделей дуг подаются сигналы разрешения. Путь, ведущий из исходной точ.ки А в конечную точку В, является искомым путем и проходит через промежуточную точку М, Исходный узел фиксируется путем приложения постоянного разрешающего сигнала на вход Fl модели узла РА, а фиксация конечной точки производится путем приложения постоянного разрешающего сигнала ко

-входу Е2 модели узла PB.

В течение всего времени работы генератор .импульсов 19 выдает попеременно два сигнала; Tl =.на выход 20 и T2 — на выход 18.

В исходный момент с выходов 52 моделей узлов и с выходов 55 моделей дуг снимается сигнал запрета. . При пуске устройства к моделям узлов подходит первый сигнал Тl. Этот сигнал проходит на выход схемы «И» 26 лишь модели

-узла РВ, так как на входы Е2 других моделей узлов поступает сигнал запрета от двустабильных элементов 28.

Двустабильный элемент 25 модели PB переходит в противоположное состояние и выдает сигнал разрешения на один из входов схемы 29 модели дуги 15 по входу L6.

11ри поступлении сигнала Т2 на схемы 29 моделей дуг лишь схема 29 модели дуги 15 пропу.скает его на выход, так как на входы

Еб остальных моделей дуг поступает сигнал запрета от элементов 25. Двустабильный элемент 26 модели 15 таким образом переводится первым сигналом Т2 в противоположное состояние: с выхода S5 через вход Е2 на схему 26 модели узла РМ поступает сигнал разрешения.

При поступлении второго сигнала Т1 схема 26 модели РМ оказывается открытой и переводит элемент 25 модели РМ в противоположное состояние: на выход S8, а следовательно, и на вход Еб схемы 29 модели дуги 14 поступает сигнал разрешения.

Последовательность операций при прохождении от узла М к узлу А та же, что и при прохождении от узла В к узлу М.

При,появлении сигнала разрешения на выходе 55 модели 14 схема «И» 35 этой модели оказывается открытой (при условии, что на вход 86 модели поступает сигнал разрешения) для сигнала фиксации начального узла, который подается на вход Еl модели РА и проходит на вход Е4 схемы 85 модели 14 через усилитель 27 модели РА.

На .выходе схемы 35 модели 14 появляется сигнал разрешения, который проходит по усилителям 27 и схемам 85 моделей всех узлов и дуг, оказавшихся на отмеченном (оптимальном) пути (например, на фиг. 2 — моделей

РА, 14, РМ, 15, PB), и индицирует этот путь.

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

На фиг. б дана схема индикации, состоящая из схемы «И» 44 с двумя входами 45, 4Ь, управляющая первым двустабильным элементом 47, выход которого соединен с одним из двух входов 48 и 49 второй схемы «И» 50, и второго двустабильного элемента 51, вход которого соединен с выходом схемы 50, а выход подсоединен к выходу Sl.

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

В случае если длина (вес) дуги не равна 1, ко входу 82 модели дуги подсоединяется выходом 43 схема, показанная на фиг, 5.

В этом случае на выходе схемы «И» 29 соответствующей модели дуги появляется сигнал лишь после того числа импульсов Т2, которое закодировано вентильной схемой 42, входами соединенной с разрядами счетчика 88, на вход которого поступают импульсы Т2 через схему «И» 89 при наличии сигнала разрешения на входе 40, т. е. при фиксации сигнала разрешения на входе SÇ модели узла, в который данная дуга входит.

326788

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

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

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

«удаления» дуги из сетевого графика, четвер- 20 тый вход — с выходом усилителя, вход которого соединен через схему декодирования со счетчиком данной модели дуги, а пятый вход так же, как и пятые входы соответствующих схем «И» всех моделей дуг, соединен с одним 25 выходом генератора импульсов устройства, второй выход которого соединен с одним из входов двухвходовых схем «И» всех моделей узлов, выход пятивходовой схемы «И» соединен со входом двустабильного элемента этой 30 же модели дуги, выход которого соединен со вторым входом двухвходовой схсмы «И» модели узла, из которого дачная дуга выходит, вход пнвертора модели дуги соединен с выходом двустабильного элемента модели узла, из которого данная дуга выходит, выход двустабильного элемента модели дуг.i сосд шен со вторым входом двухвходовоп схемы «И» модели узла, из которого д",øèÿ дуга ьыходит.

2. Устройство по п. 1, огни!o îöñåñë тем, что схема индикации узла годер>кит двухвходовые схемы «Н» и двустабпльныс схемы, причем выход первой схемы «И» соединен со входом первой двустабильпой схемы, выход которой соединен с одним пз входов второй схемы «И», выход последней соединен со входом второй двустабильпой схемы, а схема индикации дуги состоит пз усилителя и трехвходовой схемы «И», трп входа которой соединены соответственно с выходом двустабильного элемента модели данной дуги с выходом второго двустабпльного элемента схемы индикации узла, пз которого данная дуга выходит, и с выходом усилителя данной схемы индикации, а выход трехвходовой схемы

«И» соединен с одним из входов первой двухвходовой схемы «И», входящей в состав схемы индикации узла, в который данная дуга входит.

326788

Е7

Е4

52 54

Фи 4

5б

Е!

Корректоры.. T. Бабакина и Н. Шевченко

Редактор Л. Утехина

Заказ 527/16 Изд. № 115 Тираж 448 Подписное

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

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

Типография, пр. Сапунова, 2

Dd

Фиг. 6;

Составитель Л. Дмитриева

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

Еб

Е5

Е3