Модель дуги транспортной сети

 

363983

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик

Зависимое от авт. свидетельства _#_o

М, Кл. G 06f 15/56

Заявлено 27Х11.1970 (№ 1466395 18-24) с присоединением заявки ¹

П риор и,тет

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

СССР

Опубликовано 25.Х11.1972. Бюллетень М 4 за 1973

Дата опубликования описания 22.11.1973

УДК 681.325.6(088.8) Авторы изобретения

А. А. Илюхин и В. В. Чернчев

Московский ордена Трудового Красного Знамени инженернофизический институт

Заявитель

МОДЕЛЬ ДУГИ ТРАНСПОРТНОЙ СЕТИ

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

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

Цель изобретения — упрощение модели транспортной сети со случайными пропускными способностями дуг.

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

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

20 обратно включенный диод соединен с входом модели дуги и через десятый и одиннадцатый вентили, подключенные другими входами к блоку управления, — с нулевым входом входного триггера и соответственно суммирующим входом счетчика потока через дугу.

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

«НЕ» связан с четвертым входом второго

30 вентиля. Пятые входы второго и третьего вен363983

3 тилей, нулевой вход входного и единичный вход выходного триггера и вход датчика случайных временных интервалов подключены к блоку управления.

На чертеже приведена схема модели дуги тр а нсп ортн ой сети.

Модель дуги содержит вентили 1 — 11, схемы «НЕ» 12 и 13, триггеры 14 и 15, диоды

16 — 19, линии 20 и 21 задержки, схему 22 совпадения, счетчики потока через дугу 28 и памяти пропускной способности дуги 24, датчик 25 случайных временных интервалов, индикатор 26, олок управления (па чертеже не показан).

Модель дуги транспортной сети работает следующим образом.

Импульс, возникающий в узле сети, например на входе моделируемой дуги, через вентиль 1, линию 20 задержки устанавливает триггер 14 в единичное состояние, тем самым перекрывая вентили 1 и 2. Аналогично происходит в том случае, когда дуги кончаются в данной вершине, т. е. импульс через вентиль 2, линию 21 задержки устанавливает триггер 15 в нулевое состояние, тем самым перекрывая вентили 2 и 1. Таким образом, во-первых, фиксируются просмотренные дуги (в том числе и вершины), т. е. блокируются все подходы к ним, а во-вторых, — направление просмотра, так как триггер 14 (единичное состояние) соответствует положительному направлению просмотра, триггер 15 — отрицательному.

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

Для статистического анализа сетей со случайными пропускными способностями необходимо в счетчик 24 памяти пропускной способности дуги записывать новую пропускную способность дуги для каждого шага набора статистики. Это достигается измерением длительности потенциала на потенциальном выходе датчика 25 случайных временных интервалов, импульсами стандартной частоты из блока управления через вентиль 11. Задание новых кодов определяется подачей разрешающего потенциала по шине 27, запрещающего — по шинам 28 и 29 для блокировки остальных элементов сети и подачей единичного импульса по шине 80.

Блокировка прохождения импульса в том или ином направлении осуществляется следующим образом. Нулевое состояние счетчика 23 потока через дугу, через схему «НЕ»

13 является управляющим потенциалом для вентиля 2 и разрешает просмотр в обратном

4 направлении (присвоение знака « — ») в случае f(U) ) О. Выход схемы 22 совпадения счетчика 24 памяти пропускной способности дуги и счетчика 28 потока через дугу (через схему «НЕ» 12) является управляющим входом вентиля 1 и запрещает просмотр дуг (присвоение знака «+») в случае f(U) =c(U).

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

Процедура перераспределения и изменения потока через сеть осуществляется следующим образом. В результате описанных выше действий в сети (если поток еще можно увеличить) выделяется единственная цепь дуг, соединяющих источник со стоком. По шине 29 подается запрещающий потенциал, а по шинам 31, 82 — разрешающий, тем самым давая возможность обратного просмотра дуг, начиная со стока. Импульс, возникающий, например, на выходе дуги, если дуга имеет пометку «+», а триггер 14 находится в единичном состоянии, проходит через диод 16 на вход сети и через вентиль 9 на вход сложения счетчика 23 потока через дугу. Аналогично при обратном просмотре дуги (триггер 15 в нулевом состоянии) импульс с входа дуги через вентиль 7 и диод 19 поступает на выход дуги, а через вентиль 10 — на вход вычитания счетчика потока через дугу.

Вентили 9 и 10 блокируют входы счетчика потока через дугу при выполнении процедуры выделения единственной цепи дуг, соединяющих источник со стоком. Выходы вентилей 8 и 9 через вентили б и 5 с управлением по шине 88 соединены соответственно с нулевым и единичными входами триггеров 14 и 15, т. е. первоначально импульс обратного просмотра фиксирует выделенные дуги (вновь открывает их) для повторного, а если необходимо, многократного поиска единственной цепи. Исходное состояние устанавливается по шине 84..

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

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

27 од

Составитель Е. Тимохина

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

Корректоры: М. Коробова и Л. Корогод

Редактор И. Грузова

Заказ 257/11 Изд. № 1046 Тираж 404 Подписное

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

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

Типография, пр. Сапунова, ных интервалов, импульсньш выход которого через четвертый и пятый вентили, подключенные вторыми входами к блоку управления, и обратно включенные диоды соединен с входом и cîîòâåòñòâåííî выходом модели дуги, третьи входы четвертого и пятого вентилей подключены к нулевому выходу выходного триггера и единичному выходу входного триггера, нулевой выход входного и единичный выход выходного триггера соединены с вторыми и третьими входами второго и третьего вентилей, вход модели дуги соединен с входом шестого вентиля, второй и третий входы которого подключены к блоку управления и нулевому выходу выходного триггера, выход шестого вентиля через обратно включенный диод соединен с выходом модели дуги и через седьмой и восьмой вентили, подключенные другими входами к шинам управления, соединен с единичным входом выходного триггера и соответственно вычитающим входом счетчика потока через дугу, нулевой выход которого через схему

«НЕ» подключен к четвертому входу третьего вентиля, выход модели дуги соединен с входом девятого вентиля, второй и третий входы которого подключены к шине управления и

- единичному выходу входного триггера, выход девятого вентиля через обратно включенный диод соединен с входом модели дуги и через десятый и одиннадцатый вентили, подключенные другими входами к блоку управления, соединен с нулевым входом входного триггера и соответственно суммирующим входом счетчика потока через дугу, выход схемы совпадения, подключенной к счетчику пото15 ка через дугу и счетчику памяти пропускной способности дуги, через схему «НЕ» соединен с четвертым входом второго вентиля, пятые входы второго и третьего вентилей, нулевой вход входного и единичный вход выходного триггера и вход датчика случайных временных интервалов подключены к блоку управления.