Устройство для анализа параметров сетей Советский патент 1990 года по МПК G06F15/173 

ел

00

ел

оо оо

Изобретение относится к вычислительной технике и может быть использовано для исследования потоков в сетях. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи оптимизации двух взаимосвязанных потоков между заданной парой вершин сети. Устройство содержит блок 1 сравнения, блок 2 задания матрицы инцидентности, блок 3 определения концевых вершин ребер, блок 4 определения маршрута, блок 5 выбора ребер с оптимальной пропускной способностью, блок 6 синхронизации, входы 7 задания веса ребер по первичному потоку устройства, входы 8 задания веса ребер по вторичному потоку устройства, вход 9 задания критического веса по вторичному потоку устройства, вход 10 пуска устройства, выходы 11, 12 блока 6 синхронизации, выходы 13 признаков принадлежности дуг маршруту устройства. После подачи сигнала уровня логической единицы на вход 10 пуска устройства блок 6 синхронизации формирует последовательность сигналов уровня единицы на выходах 11, 12, предусмотренную временной диаграммой его работы. При этом на выходах 13 устройства формируется множество ребер в пути между начальной и конечной вершинами сети, у которого пропускная способность по первичному потоку максимальна, а пропускная способность по вторичному потоку не больше максимально допустимой величины, 1 з.п. ф-лы, 7 ил.

ю

ФиаЛ

1587533

рует последовательность сигналов УРОВНЯ единицы на выходах 11, 12, предусмотренную временной диаграммой его работы. При этом на выходах

13 устройства формируется множество ребер в пути между начальной и ко.ч

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

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

На фиг.1 представлена ф нкциональ ная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации; на фиг.З - функциональная схема блока выбора ребер с оптимальной пропускной способностью;на фиг.4 временная диаграмма работы его узла синхронизации; на фиг.5 - пример модульной реализации устройства; на фиг.6 - блок управления; на фиг.7 - иллюстративный пример решения зада- чи оптимизации двух взаимосвязанных потоков.

Устройство содержит (фиг.1) блок 1 сравнения, блок 2 задания матрицы инцидентности, блок 3 определения концевых вершин ребер, блок 4 определения, маршрута, блок 5 выбора ребер с оптимальной пропускной спо- а собностью, блок 6 синхронизации,вход 7 задания веса ребер по первичному потоку устройства, входы 8 задания веса ребер по вторичному потоку устройства, вход 9 задания критического веса по вторичному потоку устройства, вход Ю пуска устройства, выходы 11 и 12 блока 6 синхронизации, выходы 13 признаков принадлежности дуг маршруту устройства.

Блок 5 ребер с оптимальной пропускной способностью содержит узел 14 стягивания ребер, узел 15 определения иницидентных ребер, узел 16 выбора максимума, накапливающий узел 17 сравнения, регистр 18, узел 19 синхронизации, тактовый вход 20 блока 5, входы 21 задания веса ребер, входы 22 признаков ин

нечной вершинами сети, у которого пропускная способность по первичному потоку максимальна, а пропускная способность по вторичному потоку не больше максимально допустимой вели- .чины. 1 з.п. ф-лы, 7 ил.

цвдентности ребер вершинам сети блока 5, вход 23 начальной установки блока 5, с первого по третий выходы 24-26 узла 19 синхронизации и выходы 27 признаков принадлежности ребер множеству оптимальных.

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

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

Г max

Х;

(q.-j)l

е k J

b,-,)

При b ,.

J

b

где b.

величина в.торичного потока по ребру (K.,XJ ) ; заданная максимальная допустимая величина вториного потока для каждого ребра сети;

величина первичного потока по ребру (х. , X .); любой (S-t) разрез в множестве сети;

соответственно начальная и конечная вершины сети. Перед началом работы в блок 2 задания матрицы инцидентности заносят информацию о топологии сети. На входы 7 и 8 устройства подают информаци о весе (пропускной способности) ребер по первичному и вторичному потоку соответственно. На вхоД 9 подают информацию о максимально допустимой (критической) величине вторич J Ь. и

k и t НОГО 1. о

ет из тег: которых п

э. При этом блок 2 исключа логии графа все ребра, вес

вторичному потоку превышает допустимую (критическую) величину.

На вход 10 пуска устройства подал ют импульс уровня логической едини- цы. При этом блок 6 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы.Сигнал уровня логической единицы появляется на первом выходе 11 блока 6. При этом блок

5выбора ребер с оптимальной пропускной способностью накапливает на свои выходах 27 состав ребер, вес которых не меньше веса ребер с максимальной пропускной способностью среди всех ребер инцидентных начальной вершине, и стягивает эти ребра. Через время,достаточное для окончания указанных процессов, блок 6 синхронизации снимает сигнал уровня логической единицы с выхода 11 и формирует сигнал уровня логической единищ, на выходе 12. При этом блок 3 определения концевых вершин ребер проверяет принадлежность конечной вершины составу концевых (т.е. производит проверку наличия пути из начальной :

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

6синхронизации, а блок 4 выдает на выходы 13 устройства множество ребер, принадлежащих оптимальному маршруту.

Блок выбора ребер с оптимальной пропускной способностью работает следующим образом.

Перед началом работы обнуляют накапливающий узел 17 сравнения. На входы 20 подают информацию о весе ребер сети, на входы 22 информацию о ее топологии. На вход 20 пуска подают сигнал уровня логической единицы. При этом узел 19 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой ьго работы (фиг.4). Сигнал уровня логической единицы появляется на выходе 26 узла 19. При этом узел

10

15 формирз ет на своих выходах массив ребер, инцидентных начальной вершине сети, а узел 16 выбора максимума выбирает вес максимального из них и выдает его (вес) на свой информа- ционный выход. Через время, достаточное для определения веса максимального из ребер, на выходе 25 узла 19 появляется, сигнал уровня логической единицы. При этом информация с выхода узла 16 заносится в регистр 18, Через время, достаточное для записи, узел 19 снимает сигналы уровня логи- 15 ческой единицы с выхлдов 25 и 26 и формирует сигнал уровня логической единицы на выходе- 24. При этом узел 17 сравнивает веса ребер сети с весом, записанным в регистр 18, и На- 20 .капливает (по ИЛИ) результаты сравнения (не меньше) дпя каждого информационного направления. При этом стягивает все ребра, вес которых превосходит значение, записан- 5 ное в регистре 18. Через время, достаточное для окончания операции, сравнения, узел 19 снимает сигнал уровня логической единицы с выхода 24. При поступлении на вход 20 очередного тактового импульса работа блока 5 повторяется.

Устройство может быть выполнено в виде моделей 28 ребер (фиг.5) и блока 29 управления (фиг.6).

Модель 28 ребра содержит элементы И 30-44, элементы ИЛ1 45-50, триггеры 51-56, счетчики 57 и 58, элемент НЕ 59 и элемент 60 индикации.

Блок 29 управления содержит счетчики 61 и 62, элементы И 63-74, элементы ИЛИ 75-78, элемент НЕ 79,триг- 80-85, генератор 86 импульсов, элемент ИЛИ 87. Устройство имеет полюса 88-101, среди которых 88 и 89 5 у моделей 28 ребер служат для коммутации их между собой, согласно конфигурации моделируемой сети. Полюса 90-99 в моделях 28 ребер служат для подключения к блоку управления, что 0 обеспечивает их синхронную работу. Полюсами 100 и 101 блок 29 управления подключается соответственно к полюсам 88 и 89 тех моделей ребер, между которыми отыскивается оптимальный путь.

Задание исходных данных задачи оптимизации двух взаимосвязанных потоков осуществляется с помощью коммутации моделей 28 ребер посредст0

5

0

5

1

BOM полюсов 88 и 89 между собой в соответствии с конфигурацией моделируемой сети, подключением полюсом 1 и 101 блока 29 управления к полюсам тех моделей 28 ребер, между которыми отыскивается путь, занесения (N - q,-;) (N - bjj) и (N - bj) хшсла импульсов соответственно в счетчики 5V, 68 моделей 28 ребер и счетчик 62 блока 29 управления,где ГГ - емкость счетчиков.

Процесс нахождения пути можно представить в виде трех этапов.

Первьй этап содержит циклически повторяклциеся шаги: нахождение разрза Сх;, Xj) из множества разрезов К выделение ребра разреза (х ;, х:) с

max q - ; выбор ребер, у которых величина первичных потоков больше или равна величине первичного потока, выбранного ребра разреза. Второй и третий шаги первого этапа вьшолняют- ся устройством одновременно. Выполнение третьего шага состоит в зако- рачивании полюсов 88 и 89 моделей 28 что приводит к исключению их из дальнейшего рассмотрения на этом этапе.

Второй этап заключается в проверке выполнения ограничений на вели- чину вторичного потока Ь ;j для каждого ребра, выбранного на первом, этапе, с заданной максимальной допустимой величиной Ъ. В результате проверки может оказаться, что ребра удовлетворяют или не удовлетворяют ограничению. В этом случае эти ребра исключаются из процесса решения задачи. Исключение ребер представляет собой блокирование в додели 28 цепи прохождения сигнала от полюса 88 к полюсу 89, и наоборот. Кроме того, на этом этапе одновременно производится проверка наличия пути межд заданными вершинами, проходящего по ребрам. Если такого пути нет, устройство переходит к выполнению операций первого этапа, при .наличии ггути - к выполнению третьего этапа. Третий этап .заключается в выделении ребер этого пути и его индикации.

Перед на.чалом работы устройства триггеры 51-56 всех моделей 28 и триггеры 80-85 и счетчик 61 блока 29 управления устанавливаются в нулевое состояние. Цепи установки и занесения исходных данных не показаны.

8

10

20

25

Работа устройства начинается с момента установки триггера 80 в единичное .состояние. Единичное состояние триггера 80 выдает разрешение на вход элемента И 64. При этом импульсы генератора 86 проходят через элемент И 64 и поступают на входы элементов И 66 и 67. Через элемент И 67 импульсы поступают на вход элемента ИЛИ 75 и далее на полюс 100 блока 29 управления.

Импульсы с полюса 100 блока 29 управления поступают на полюса 88 или 15 89 моделей 28, которые в результате коммутации этими полюсами между собой образуют вершину сети, из которой отыскивается путь. Б указанных моделях 28 импульсы с полюса 88 поступают на вход элементов 32-35. На всех входах элемента И 34 есть разрешения и поэтому импульсы пройдут через него и поступят на единичный вход триггера 51. По первому импульсу из всей серии импульсов, поступивших в модель 28 на полюс 88,триггер 51 установится в единичное состояние. Все последующие импульсы подтверждают это состояние триггера 51.

Аналогично, если импульсы поступят на полюс 89 модели 28, они пройдут через элемент И 36 и установят триггер 52 в единичное состояние. Единичное состояние триггеров 51 или 52 выдает разрешение на вход элемента И 38. Разрешение поступает на полюс 95 модели 28.

С полюса 95 модели 28 разрешение поступает на соответствующий этой модели вход многовходового элемента ИЛИ 87. На входы элемента ИЛИ 87 поступают разрешения только от тех моделей 28, которые своим полюсом 88 45 или 89 связаны с полюсом 100 блока 29 управления. Единичное состояние триггеров 51 или 52 свидетельствует о том, что данная модель 28 принадлежит выбранному разрезу (х;, х ,) . из множества разрезов К. Это соответствует первому шагу первого этапа решения задачи.

Выбор ветви разреза (х., х j) с max q ,j и выбор ребер сети, величи- на первичных потоков через которые больше или равна величине потока выбранного ребра разреза. Что соответствует выполнению второго и третьего шагов первого этапа, происхо35

40

0

дит следующим образом. Разрешение с выхода многовходового элемента ИЛИ 87 поступает на вход элемента НЕ 79 и одновременно, через элемент И 65 на единичный вход триггера 81. В результате элемент НЕ 79 снимет разрешение с полюса 94 блока 29 управления и, следовательно, с полюсов 9А всех моделей 28, что блокирует вход элемента И 39 в каждой модели 28.

Разрешение, поступившее на единичный вход триггера 81, устанавливает его в единичное состояние, что запретит прохождение импульсов генератора 86 на полюс 100 блока 29 управления и разрешит прохождение импульсов на вход счетчика 61 и полюс 90. Единичное состояние триггера 81 свидетельствует о том, что устройство начинает выполнять второй и третий шаги первого этапа.

В моделях 28 импульсы с полюса 90 поступают через элемент И 43 на вход счетчика 57 до его переполнения.

Импульс переполнения счетчика 57 модели 28 поступает на единичный вход триггера 53 и одновреме нно чере элемент ИЛИ 43 на нулевые входы триггеров 51 и 52. В результате триггеры 51 и 52 установятся в нулевое состояние, если ранее они были установлены в единичное состояние импульсами, посгупившими на полюса 88 и

89 моделей 28.

Триггер 53, установленный в единичное состояние поступившим на его вход импульсом переполнения счетчика 57, установится в нулевое состояние очередным импульсом, который поступит на полюс 90. Это происходит потому, что триггер 54 находится в нулевом состоянии и он вьщает ра зре- шение на вход элемента И 39. В результате очередной импульс, который поступает на полюс 90, пройдет через элементы И 39 и ИЛИ 48 на нулевой вход триггера 53.

В результате установки триггеров 51 и 52 в модели 28 происходит снятие разрешения с полюса 95 и, следовательно, с соответствующего входа многовходового элемента ИЛИ 87. В тот момент, когда будет снято последнее разрешение с полюса 95 многовходового элемента ИЛИ 87, блок 29 управления вьдаст разрешение на по

58753310

люс У4 моделей 28. При этом в моде- , ли 28 выбранного разреза с наибольшей пропускной способностью по первичному потоку триггер 54 установит- ся в единичное состояние. Единичное состояние триггера 54 запретит установку триггера 53 в нулевое состояние очередным импульсом, который Q поступит на полюс 90 модели 28, Это происходит потому, что -на нулевом выходе триггера 54 будет снято разрешение, которое заблокирует элемент И 39 и очередной импульс с полюса 90 J5 не пройдет через элементы И 39 и ИЛИ 48.на нулевой вход триггера 53.

Таким образом, в процессе поступления импульсов на полюс 90 всех моделей 28 устанавливаются триггеры 20 53 и 54 в единичное состояние у тех моделей, у которых величина первичного потока равна или больше величины первичного потока выбранного ребра разреза. Единичное состояние триг- 25 геров 53 и 54 свидетельствует о том, что пропускная способность этих моделей по первичному потоку удовлетво-, ряет условию. Кроме того, единичное состояние триггера 54 в каждой моде- 30 ли 28 выдает.разрешение на входа элементов И 30 и 32, что обеспечивает закорачивание полюсов 88 и 89 и исклйчение таких моделей 28 из дальнейшего рассмотрения на первом этапе .

Конец выполнения второго и третьего шагов первого этапа устройством определяется моментом появления импульса переполнения счетчика 61 блока 29 управления. К.этому моменту в счетчиках 57 всех моделей 28 вое- . становится информация о величинах их первичных потоков, т.е. произойдет регенерация. Роль регенерационного счетчика для счетчиков 57 всех мо- делей 28 выполняет счетчик 61 блока 29 управления. Он начинает свой счет с О и его емкость равна N, а счетчики 57 моделей 28 начинают счет с

35

40

45

50

55

(N - q;j-).

Импульс переполнения счетчика 61 блока 29 управления поступает через элемент ШШ 75 на полюс 100. Кроме того, импульс переполнения счетчика 61 поступает на вход генератора 86, кото1)ый по этому импульсу выдает навход элемента И 71 импульс,который сдвинут относительно входного, Через элемент И 71 этот импульс не

пройдет, так как нет разрешения с единичного выхода триггера 85.

Далее этот импульс с полюса 100 блока 29 управления поступает на полюс 88 или 89 тех моделей 2В, которые в результате коммутации этими плюсами между собой образуют вершину сети, из которой отыскивается путь, и весь процесс выполнения шагов первого- этапа повторяется аналогично описанному. Итерационное выполнение шагов первого этапа повторяется до тех пор, пока очередной импульс переполнения счетчика 61 блока 29 управления, который поступает через элемент ИЛИ 75 на полюс 100, не появится на полюсе 101. Пояление импульса на полюсе 101 происхдит в результате распространения импульса переполнения счетчика 61 по тем моделям 28, триггеры 53 и 54 которых находятся в единичном состоянии. В таких моделях импульс с полюса 88 через элемент И 32 поступает на полюс 89 или с полюса 89 через элемент И 30 на полюс 88.

Момент появления импульса на полюсе 101 блока 29 управления свидетельствует о том, что первый этап работы устройства окончен и все множество ребер сети разбито на два подмножества. Одно подмножество содержит ребра, величины первичных потоков через которые удовлетворяют условию и в соответствующих им моделях 28 триггеры 53 и 54 находятся в единичном состоянии. Другое подмножество содержит ребра с величинами первичных потоков, которые не удовлетворяют указанному условию, и их триггеры 53 и 54 будут в нулевом состоянии. Это подмножество ребер при выполнении последующих этапов работы устройства не участвует в решении задачи.

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

Импульс, который появился на полюсе 101 бло ка 29 управления, поступит на вход элементов И 72-74. Через элемент И 72 импульс пройдет, так как есть разрешение с нулевого выход

триггера 85. С выхода элемента И 72 этот импульс поступает на единичный вход триггера 84 и установит его в единичное состояние. Единичное состояние этого триггера 85 снимает разрешение с входов элементов 64, 67 и 74 и выдает разрешение на элементы И 70, 71, 73 и полюс 94 блока

0 29 управления. В результате импульсы генератора 86 пройдут через элемент И 70 поступят на счетчика 62. Одновременно эти импульсы начнут поступать через элемент ИЛИ 76 на вход

5 счетчика 61 и на полюс 90 блока 29 управления.

В моделях 28 разрешение с полюса 91 поступит на входы элементов НЕ 59 и И 44. В результате на выходе эле0 мента НЕ 59 исчезн.ет сигнал и элемент И 43 будет заблокирован. Одновременно с этим импульсы, которые поступают на полюс 90, будут проходить через элемент И 44 на вход счетчи5 ка 58 до его переполнения. Следует заметить, что для моделей 28, у которых выполняется условие b Ь , счетчики 58 переполнятся раньше или одновременно со счетчиком 62 блока

0 29 управления. В эгих моделях 28 импульс переполнения сетчика 58 не пройдет через элемент И 41, так как триггер 56 находится в нулевом состоянии. Следовательно, триггер 55 у

, таких моделей 28 останется в нулевом состоянии, а триггеры 53 и 54 - в единичном.

В моделях 28, у которых не выполняется условие b jj b|, счетчики

Q 58 переполнятся позже, чем счетчик 62 блока 29 управления. В таких моделях 28 триггер 55 устанавливается в единичное состояние, а триггеры 53 и 54 - в нулевое. Это происходит

следующим образом.

Импульс переполнения счетчика 62 поступает на полюса 92 всех моделей 28. Б моделях 28 он. поступает на единичный вход триггера 56 и устанавQ ливает его в единичное состояние. Единичное состояние триггера 56 выдает разрешение на вход элемента И 41, что обеспечивает прохождение импульсов переполнения счетчика 58

в модели 28 через этот элемент. Импульс переполнения счетчика 58, пройдя через элемент И 41 на единичный вход триггера 55, установит его в единичное состояние. Единичное состо 3

яние триггера 55 выдает разрешение на вход элемента И 42 и снимает разрешение с входов элементов И 30-37, что .запрещает прохождение сигналов от плюса 88 модели 28 к полюсу 89, и наоборот. Это соответству-т ет исключению данной модели 28 из дальнейшего процесса решения задачи.

Очередной импульс переполнения счетчика 61 блока 29 управления поступает на вход элемента ИЛИ 75 и на вход генератора 86. По этому импульсу генератор 86 импульсов выдает импульс, который сдвинут относительно входного, на вход элемента И 71. Через элемент И 71 импульс пройдет, так как на входе этого элемента есть разрешение с единичного выхода триггера 85 и нулевого выхода триггера 84. С выхода элемента И 71 импульс поступает на полюса 93 всех моделей 28. В моделях 28 этот импульс поступает на нулевой вход триггера 56 и через элемент И 42 на нулевой вход триггер 54 и устанавливает их в нулевое состояние. Кроме того, этот импульс поступает на нулевые входы триггеров 53, 51 и 52. В результате они устанавливаются в нулевое состояние. К моменту появления импульса переполнения на выходе счетчика 61 информация в счетчиках 58 моделей 28 и в счетчике 62 блока 29 управления восстановлена, т.е. происходит регенерация. Роль регенерационного счетчика, также как и на первом этапе,для этих счетчиков выполняет счетчик 61 блока 29 управления. Он начинает счет с нуля, а счетчики 58 моделей 28 и счетчик 62 блока 29 управления начинает соответственно свой счет с (N - bjj) и (N - Ь) .

С выхода элемента ИЛИ 75 импульс переполнения счетчика 61 блока 29 управления поступает на полюс 100 и далее на полюса 88 или 89 моделей 28, которые подключены к полюсу 100. В моделях 28 этот импульс с полюса 88 через элемент И 32 поступает на полюс 89. Аналогично этот импульс с полюса 89 через элемент И 30 поступает на полюс 88. Таким образом, импульс переполнения с полюса 100 блока 29 управления, распространяясь по моделям от полюса 88 к полюсу 89 или от полюса 89 к полюсу 88, появится на полюсе 101 6jioKa 29 управления. Следует заметить, что импульс может про1

1587533

14

to

15

20

ходить только по тем моделям 28, у которых одновременно триггер 55 и триггеры 53 и 54 соответственно находятся в нулевом и единичном состоянии.

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

В противном случае устройство переходит к дальнейшему его нахождению. Это осуществляется следующим образом. Импульс генератора 86, который пройдет через элемент И 71, поступит на нулевой вход триггера 85 и установит его в нулевое состояние. Нулевое -состояние триггера 85 запретит прохождение импульсов генератора 86 через элемент И 70 и разрешит их прохождение через элемент И 64. Это приводит к тому, что весь описанный процесс повторяется, т.е. устройство сно- 25 ва переходит к выполнению операций первого и второго этапов. При этом из моделируемой сети будут исключены модели 28, в которых триггеры 55 находятся в единичном состоянии,а остальные триггеры - в нулевом.

В случае появления импульса на полюсе 101 устройство переходит к выполнению третьего этапа, т.е. к выделению ребер искомого пути и его индикации. Это происходит следующим образом. С полюса 101 импульсы в блоке 29 управления через элементы И 73 и ИЛИ 78 поступают на единичный вход триггеров 82, 84 и устанавливают их в единичное состояние. Единичное состояние триггера 82 снимает разрешение с полюсов 99 и выдает разрешение на полюса 98 всех моделей 28.

В моделях 28 разрещение с полюса 5 98 поступает через элемент ИЛИ 49 на нулевой вход триггера 54 и устанавливает его в нулевое состояние. Нулевое состояние триггера 54 разрывает закоротку полюсов 88 и 89.

Одновременно с этим импульсы генератора 86 начинают опять поступать на полюс 100. Это происходит потому,что единичное состояние триггера 84 блока 29 управления выдаёт сигнал через элемент И 72 на нулевой вход триггера 85. По этому сигналу триггер 85 устанавливается в нулевое состояние, чем обеспечивает прохождение импульсов генератора 86 через элемент И 64.

0

5

0

0

5

15

С полюса 100 импульсы генератор 86.поступают на полюса 88 и 89 моделей 28, к полюсам подключен полюс блока 29 управления. При этом в указанных йоделях 28 импульсы с полюса 88 поступают на вход элемента И 35 тех моделей 28, триггер 53 которых находится в единичном состоянии и пройдет через этот элемент. Далее эти импульсы с выхода элемента И 3 через элемент ИЛИ 45 поступают на единичный вход триггера 51. По первому импульсу из всей серии импульсов, поступивших в модель 28 на полюс 88, триггер 51 установится в ед ничнЬе состояние. Единичное состо- яние триггера 51 выдает разрешение на элемент И 33. Поэтому остальные импульсы из всей серии с полюса 88 через элемент И 33 поступают на полюс 89 модели 28. Таким образом, импульсы распространяются по сети .через модели 28, у которых триггер 51 находится в единичном состоянии, до тех пор, пока не появятся на полсе 101 блока 29 управления.

Поступившие на полюс 101 блока 2 управления импульсы пройдут через элемент И 74, ИЛИ 78 и И 69, так ка триггеры 85 и 82 соответственно находятся в нулевом, единичном состояниях, и первый из них установит триггер 83 в единичное состояние. Единичное состояние триггера 83 выдает разрешение на полюс 97, снимае разрешение с полюса 96, выдает разрешение на элементы И 63, 68 и снимае разрешение с элемента И 67, при этом с полюсов 96 всех моделей 28 будет снято разрешение, что заблокирует их элементы И 35, а на полюсах 97 по- , явится разрешение, что разрешит про- холдение сигналов через элемент И 37 Одновременно импульсы генератора 86 поступят на полюс 101 и далее на полюса 89 моделей 28, к которым подключен полюсом 101 блок 29 управления.

С плюса 89 в. модели 28 импульсы через элементы И 37 и ИЛИ 46 поступят на единичный вход триггера 52. По первому импульсу из серии импульсов, поступивших на полюс 89,триггер 52 установится в единичное состояние, которое выдает разрешение на элемент И 31, Поэтому остальные импульсы пройдут через элемент И 31 и поступят на полюс 88. Это происхо

16

дит только у тех моделей 28, у которых триггер 53 находится в единичном состоянии. Таким образом импульсы , распространяются по сети через модели 28 с полюса 89 на полюс 88 до тех пор, пока не появятся на полюсе 100 блока 29 управления.

С полюса 100 блока 29 управления

10 импульсы поступят через элемент И 63, так как на другом входе этого элемента есть разрешение с единичного выхода триггера 83, на нулевой вход триггера 80. Первьй из этих импульtS сов установит триггер 80 в нулевое состояние. Нулевое состояние триггера 80 сигнализирует о конце решения задачи. П15и этом модели 28, у которых триггеры 51 и 52 находятся

20 одновременно в единичном состоянии, принадлежат искомому пути. Эти модели индицируются элементом 60 индикации.

Дпя пояснения работы устройства

5 рассмотрим пример решения задачи

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

На фиг.7а цифрами обозначены пропускные способности соответственно по первичному и вторичному потокам ре5 бер: (Sx,), (Sx,,), (Sx .5) , (х ,х,) ,

(Х,, Х), (), (, (ХдХу),

(XjX), (,), (),(x4X7),(XjX) , (Xj-Xj), (), (Х, t), (х,, t),

( Cxg,t). Первая цифра указы- 0 вает на величину пропускной способности по первичному потоку по соответствующему ребру, а вторая цифра указывает на величину пропускной способности по вторичному потоку по тому же 5 ребру. Вершиныj которые формируются в результате коммутации моделей 28 между собой полюсами 88 и 89 согласно конфигурации сети, на фиг.7а обозначены S, Х, Xj, Х, Х, Ху, Х, Х,

0 в - Кроме того, вершины S и t обозначают вершины, между которыми отыскивается путь, оптимизирующий взаимосвязанные потоки, и к которым соответственно подключены полюса 100 и

5 101 блока 29 управления. В счетчики 57 и 58 каждой модели 28 заносится предварительно соответствующее число импульсов. В счетчик 62 импульсов бло- блока 29 управления заносится число

импульсов для всех ветвей сети. Буд считать, что Ър 8.

Работа устройства начинается с м мента установки триггера 80 в едининое состояние. Единичное состояние триггера 80 разрешает проховдение и пульсов генератора 86 через элемент И 64, И 67 и ИЛИ 75 на полюс 100 блока 29 управления. С полюса 100 ипульсы поступят на полюса 88 моделе 28, которые соответствуют ребрам (S х), (S Xj) и (S X з) моделируемой сети (фиг.7а). В этих моделях импульсы пройдут через элементы И 34 и ИЛИ 45 на единичный вход триггера 51. По первому импульсу триггер 51 установится в единичное состояние. Остальные импульсы подтверждают это состояние.Единичное состояние триггера 51 моделей 28 (S х ) (S х) и (S х) свидетельствует о том, что эт модели принадлежат первому разрезу К (на фиг.7а разрез обозначен пунктирной линией) из множества разрезов, что соответствует первому шагу первого этапа работы устройства.

В результате эти модели на свой псхпюс 95 выдадут сигнап, который поступит на соответствующий этой модели вход 95 многовходового элемента ИЛИ 87. На выходе многовходового элемента ИЛИ 87 появляется сигнал,который поступает на вход элемента НЕ 79 и И 65..

В результате на полюсе 94 всех мо делей 28 снято разрешение, что блокирует элемент И 40.

Сигнал, поступивший на вход элемента И 65,проходит на единичный вход триггера 81 и устанавливает его в единичное состояние. Это состояние триггера 81 свидетельствует о том, что устройство начинает вьтолнять вторую и третью операцию первого этапа, и разрешает поступать импульсам генератора 86 на вход счетчика 61 и на полюс 90. При этом через элемент И 67 импульсы не проходят (следовательно, они не проходят на полюс 100), так как нет разрешения на нулевом выходе триггера 81.

Из всего числа моделей 28,принадлежащих разрезу К, первым перепол- ниtcя счетчик 57 модели 28 (S х). Триггер 53 этой модели 28 установится в единичное состояние, а триггер 51 - в нулевое, что снимет сигнал с соответствукицего этой модели

25

28 полюса 95 многовходового элемента ИЛИ 87.

Очередной импульс, поступивший на полюс 90 модели 28 (S х ), установит триггер 53 в этой модели 28 в нулевое состояние.

Аналогичный процесс произойдет и с моделью 28, которая соответст- JQ вует ребру (S х) сети.

При появлении импульса переполнения счетчика 57 в модели 28, которая соответствует ребру сети (S х), ее триггеры 53 и 54 устанав- 15 ливаются ь единичное состояние.

Единичное состояние триггера 54 закоротит полюса 88 и 89 этой модели 28. Одновременно с этим на полюсе 95 этой модели 28 снимается сигнап 20 ,и, следовательно, с соответствующего этой модели полюса 95 многовходового элемента ИЛИ 87 тоже снимается сигнал. В результате на выходе многовходового элемента ИЛИ 87 исчезает сигнал, что приводит к появлению сигнала на полюсе 94 всех моделей 28.

Появление сигнала на полюсе 94 всех моделей 28 разрешает прохождение сигналам через элемент И 40 в этих моделях 28 на единичный вход триггера 54.

Таким обраэом, в моделях ветвей, которые соответствуют ветвям (х ,х J,

5 ( .(

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

Q или больше пропускной способности 4 . ребра (S Xj) разреза К,, т.е. q pt, 14. В этих моделях. 28 полюсы 88 и 89, аналогично модели 28 (S х), будут закорочены. Другими словами сеть,

5 показанная на фиг.7а, преобразуется в сеть, показанную на фиг.7б. На 4иг.7б S обозначены совмещенные в результате закорачивания по-шосов 88 и 89 модели 28 вершины S, х ,

V nlэ nпlтл riTJ t- - v,

0

0 X,; вершицой t - х ,, х ,, х, х

и С.

Импульс переполнения счетчика 61 поступит на полюса 92 моделей 28, к которым в новой сети окажется подключен полюс 100. Такими ребрами будут (S t ) и (S xg) . Импульс, поступивший на полюс 88 этих ребер, установит их триггера 51 в единичное состояние. Это свидетельствует о построении нового разреза K.J из множества разре19

зов к.с позиции исходной моделируемой сети (фиг.7а) разрезу Kj принадлежат , ребра: (,), (S x-j) , (,

(X-fXg), (Xj-Xg), (), (), (XjX), (X.,t ) и (Х4Х7).

В результате дальнейией работы устройства в разрезе К найдено ребро с максимальной пропускной способностью по первичному потоку (S t ) и (S xj), их пропускная способность q 13 (фиг.7б), Это соответствует ребрам исходной сети (фиг.7а) -

(XjXj), () и ().

Очередной импульс переполнения счетчика 61, поступивший на плюс 100, появится на полюсе 101, так как он проходит по закороченным ветвям с полюса 88 на полюс 89. Этот импульс устанавливает триггер 85 в единичное состояние. Это свидетельствует о том, что все ребра,., пропускная способность по первичному потоку которых удовлетворяет заданному условию, найдены, и устройство переходит к вы- .полнению шагов второго этапа работы.

Ребра исходной сети, пропускная способность по первичному потоку ко- торых удовлетворяет условию, показаны на фиг.7в.В дальнейшем устройство работает только с этими ветвями, так как в моделях, соответствующих этим ребрам, триггеры 53 и 54 одновременно находятся в единичном состоянии. На фиг.7в не показаны ребра, которые не удовлетворяют условию.

Единичное состояние триггера 85 выдает раз эешение на элементы И 70, 71, 73 и полюса 91 всех моделей 28. В результате в каждой модели 28 снятс разрешение с входа элемента И 43 и вьщано разрешение на вход элемента И 44. Кроме того, единичное состояние триггера 85 разрешает прохождение импульсов генератора 86 через элемент И 70 на вход счетчика 62 и через элемент ИЛИ 76 на вход счетчика 61 и полюса 90 всех моделей 28,

В моделях 28 с полюса 90 импульсы через элемент И 44 поступают на вход счетчика 58 до их переполнения. Реб- .ра, соответствующие этим моделям, показаны на фиг.7в,

.В каждой такой модели 28 импульс переполнения счетчика.58 через элемент И 41 не поступает на единичный вход триггера 55 и не устанавливает его в единичное состояние.. Это возможно только для тех моделей 28,про158753320

. пускная способность по вторичному потоку которых меньше или равна Ь, 8, заданной нами ранее. К таким ребрам относятся (х, х,.) , (,), 5 (хзХ.-), (xjX.,), (Xg.x,) и () фиг.7в.

В моделях 28, которые соответствуют ребрам (фиг.7в) (S х), (, () и () сети, триггер 55 уста10

15

20

25

30

навливается в единичное состояние. Это происходит потому, что импульс появится раньше, чем импульсы переполнения счетчика 58 этих моделей 28.

В результате импульс переполнения счетчика 62 поступает на полюса 92 всех моделей 28 и устанавливает триггер 56 в единичное состояние. Единичное, состояние триггера 56 вьщает разрешение на вход элемента И 41, что позволяет проходить импульсу переполнения счетчика 58 на единичный вход триггера 55.

Единичное состояние триггера 55 разрывает цепи прохождения сигнала с полюса 88 на полюс 89 в таких моделях 28, что исключает их из дальнейшего процесса решения задачи. Такими ребрами для примера будут (S х), (xjXj-), () и (). Их пропускная способность по вторичному потоку больше Ьд 8 (фиг.7в).

Очередной импульс переполнения счетчика 61 не сможет пройти по ребрам, которые показаны на фиг.7в, так как в моделях 28 (S х j) , () , ( и () заблокированы входы элементов И 30-37.

В результате на полюсе 101 этот импульс не появится. При этом по импульсу счетчика 61 генератор 86 Импульсов выдает импульс, который сдвинут относительно входного, на вход элемента И; 71, который пройдет через этот элемент, так как триггер 84 остается в нулевом состоянии. Этот импульс устанавливает триггер 85 в нулевое состояние и поступает на полюса 93 всех моделей-28, где он устанавливает триггеры 51-55 в нулевое состояние. Это приводит к тому,что устройство снова переходит к выполнению операций первого и второго этапов. При этом из моделирумой сети исключаются модели 28, которые не удовлетворяют условию. В таких моделях триггеры 55 находятся в единичном состоянии. Для нашего примера такими моделями 28 будут модели 28, которые соответствуют ветвям (S х 3), (x,x j) ,

35

40

45

50

0

5

0

5

0

навливается в единичное состояние. Это происходит потому, что импульс появится раньше, чем импульсы переполнения счетчика 58 этих моделей 28.

В результате импульс переполнения счетчика 62 поступает на полюса 92 всех моделей 28 и устанавливает триггер 56 в единичное состояние. Единичное, состояние триггера 56 вьщает разрешение на вход элемента И 41, что позволяет проходить импульсу переполнения счетчика 58 на единичный вход триггера 55.

Единичное состояние триггера 55 разрывает цепи прохождения сигнала с полюса 88 на полюс 89 в таких моделях 28, что исключает их из дальнейшего процесса решения задачи. Такими ребрами для примера будут (S х), (xjXj-), () и (). Их пропускная способность по вторичному потоку больше Ьд 8 (фиг.7в).

Очередной импульс переполнения счетчика 61 не сможет пройти по ребрам, которые показаны на фиг.7в, так как в моделях 28 (S х j) , () , ( и () заблокированы входы элементов И 30-37.

В результате на полюсе 101 этот импульс не появится. При этом по импульсу счетчика 61 генератор 86 Импульсов выдает импульс, который сдвинут относительно входного, на вход элемента И; 71, который пройдет через этот элемент, так как триггер 84 остается в нулевом состоянии. Этот импульс устанавливает триггер 85 в нулевое состояние и поступает на полюса 93 всех моделей-28, где он устанавливает триггеры 51-55 в нулевое состояние. Это приводит к тому,что устройство снова переходит к выполнению операций первого и второго этапов. При этом из моделирумой сети исключаются модели 28, которые не удовлетворяют условию. В таких моделях триггеры 55 находятся в единичном состоянии. Для нашего примера такими моделями 28 будут модели 28, которые соответствуют ветвям (S х 3), (x,x j) ,

5

0

5

0

211587533

Новая сеть показана на фиг.7г.

т т с ю т

Дальнейшая работа устройства с эт сетью (фиг,7г) на первом этапе дает множество ребер, показанное на фиг.7д

После выполнения устройством второго этапа получено множество ребер, которое показано на фиг.7е. При этом в процессе выполнения второго этапа импульс переполнения счетчика 61, поступивший на полюс 100, проходит чере модели 28 с полюса 88 на полюс 89 и появляется на полюсе 101. Ребрами, по которым пройдет этот импульс, будут (S X,), (, (), (x.-Xj) , (x-:i).

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

Процесс выделения ребер пути заключается в подаче импульсов в модели 28, связанных с полюсом 100, триггеры 53 которых находятся в единичном состоянии. Эти импульсы от генератора 86 поступают На полюс 88 модели 28. Такой моделью будет модель 28, соответствующая ребру (S х) фиг. 7е.1 мпульс с полюса 88 в модели 28 (S X ) поступает через элементы И 35, ИЛИ 45 на единичный вход триггера 51. Первый импульс из всей серии устанавливает триггер 51 в единичное состояние, что дает возможность остальным импульсам с полюса 88 через элемент И 33 проходить на полюс 89.

Далее они поступают с полюса 89 модели 28 (S х,) на полюса моделей (х,х) и (х ,х ,).

Таким образом, распространяясь по сети от модели 28 к модели 28 (фиг.7е), они появятся на полюсе 101 блока 29 управления, т.е. в вершине t. На фиг.7а это.распространение импульсов показано пунктирной стрелкой от S к t.

После этого блок 29 управления выдает импульсы на.полюс 101 и далее на полюса 89 моделей 28. Распространяясь, импульсы этой серии проходят от вершины t к вершине S, при этом триггер 52 установлен в единичное состояние, если они проходят с полюса 89 на полюс 88 через элемент И 31 и одновременно поступают на единичный вход триггера 52. На фиг.7а это распространение показано сплошной стрелкой.

22

На фиг.7е показно, что в результате действия обеих серий импульсов триггеры 51 и 52 моделей 28, которые соответствуют ребрам (S х), ( Л, ( ) , -( 7) и .(xt) ,устанавливаются в единичное состояние. В моделях 28 (), () и () только триггеры 51 устанавливаются в единичное состояние, а триггеры 52 остаются в нулевом.

Триггеры 51 и 52, находящиеся одновременно в единичном состоянии,определяют ребра пути, который оптимизирует два взаимосвязанных потока. Этот путь на фиг.7е показан жирной линией. Он индицируется элементами 60 индикации этих моделей 28.

Формула изобретения

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

П

0.

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

t

Фиг.2

I

20

Фиг.З

ь

Фuг.f

7

0usJ5

Xi t5.3 X 16,8

Jff

J /5.3 j fS;e Д

5

г

j /5;j 2 ;5;e ЛГу Я7;7;

fiLM.t

6

X /5;3 jf fS;e jXf

Л7 f

АЗ Jf5

Xj J5i3XifJ6i8 у -о ft

t

Фиг. 7