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

 

Изобретение относится к электронным моделям и позволяет анализировать сети с различными логическими зависимостями в узлах, в том числе сетевые графики и неориентированные сети, а также решать задач о наибольшем паросочетании в графе общего вида. Цель изобретения - расширение .области применения. Устройство содержит блок моделей ребер, каждая из которых содержит регистры, формирователь временных импульсов, триггеры, элементы И, элементы ИЛИ, а также генератор импульсов , блок формирования управляющих сигналов , блок формирования топологии. Последний блок совместно с первыми регистрами блока моделей ребер обеспечивает автоматическое формирование топологии исследуемого графа (сети), а совместно со вторыми регистрами блока моделей реберпометку ребер различными метками и анализ этих меток. 10 ил. со с

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/419

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ 0

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4864031/24 (22) 12.07.90 (46) 23.02,93. Бюл. № 7 (71) Институт проблем моделирования в энергетике АН УССР и Специальное конструкторско-технологическое бюро средств моделирования Института проблем моделирования в энергетике АН УССР (72) А.И.Баранов; В.В.Васильев. О.Н.Голованова и Е.А.Ралдугин (56) Авторское свидетельство СССР

N 907552, кл; G 06 F 15/20, 1980.

Авторское свидетельство СССР

¹ 708367; кл. G 06 G 7/48, 1977, (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВОГО ГРАФИКА (57) Изобретение относится к электронным моделям и позволяет анализировать сети с

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

Устройство можно использовать для моделирования сетевых графиков, сетей с различными логическими функциями в узлах, в т.ч. неориентированных сетей, и для решения задачи о наибольшем паросочетании в графах общего вида. Паросочетание — это множество независимых ребер графа, т.е. ребер, любая пара которых не имеет общих вершин; наибольшее паросочетание — паросочетание с максимаьным числом ребер. К этой задаче сводится один из вариантов задачи объединения электростанций, „„Я./„„1797130 А1 различными логическими зависимостями в узлах, в том числе сетевые графики и неориентированные сети, а также решать задачу о наибольшем паросачетании в графе общего вида. Цель изобретения — расширение области применения. Устройство содержит блок моделей ребер, каждая из которых содержит регистры, формирователь временных импульсов, триггеры, элементы И, элементы ИЛИ, а также генератор импульсов, блок формирования управляющих сигналов, блок формирования топологии.

Последний блок совместно с первыми регистрами.блока моделей ребер обеспечивает автоматическое формирование топологии исследуемого графа (сети), а совместно со вторыми регистрами блока моделей ребер— пометку ребер различными метками и анализ этих меток. 10 ил, Известны электронные моделирующие устройства для решения задач исследования операций и теории графов. В этих устройствах вершины и ребра сетей и графов моделируются посредством элементов цифровой выислительной техники, а их числовые характеристики представляются дискретными временными интервалами иили двоичными кодами. Сеть — это граф со взвешенными ребрами; аналоги вершин в графе — узлы в сетях, которые реализуют логические функции И, ИЛИ.

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

1797130 рого подключен к выходу третьего элемента

И, первые входы второго, третьего и четвертого элементов И подключены соответственно к первому, второму синхронизирующим выходам блока формирова30 ния управляющих сигналов и к выходу четвертого триггера, блок формирования топологии содержит инвертор, первый — четвертый элементы ИЛИ, первый — третий элементы И, причем выход первого элемен- 35 та И подключен ко второму входу формирователя временныx интервалов каждой модели ребра блока, первые входы первого ,и третьего элементов И подключены соответственно к выходу и входу инвертора, первые входы первого и второго элементов

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

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

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

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

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

1797 !30

20

30

Чередование адресных и информационных периодов зависит от выходйого сигнала элемента ИЛИ 33, Когда любой ФВИ 7окан55 чивает работу, через триггер 8 выдается сигнал прерывания, который через ИЛИ 34, ИЛИ 33, инвертор 30 прекращает информационный период и начинает адресный, При отсутствии сигналов прерывания от МР, адресный период организуется сигналом 2з. элементов И, вторые входы которых подключены соответственно к пятому и шестому задающим выходам блока формирования управляющих сигналов, а выходы — к второму и третьему входам пятого элемента ИЛИ, выход которого подключен к второму входу второго узла сравнения каждой модели ребра, первый и второй входы четвертого элемента И подключены соответственно к выходу четвертого элемента

ИЛИ и к выходу первого элемента ИЛИ, выход третьего элемента ИЛИ подключен к второму входу второго элемента ИЛИ, выход второго элемента И подключен к второму осведомительному входу блока формирования управляющих сигналов, первый и второй синхронизирующие входы которого подключены к соответствующим выходам генератора импульсов, Эти новые элементы и связи позволяют моделировать неориентированные графы с пометкой их ребер в процессе моделирования. За счет этого предложенное устройство решает задачу о наибольшем паросочетании, На фиг.1 дана функциональная схема устройства; на фиг,2, 3 — примеры выбора моделей ребер для обработки; на фиг,4— режимы работы устройства; на фиг.5, 6— иллюстрируют моделирование ориентированной и неориентированной сетей; на фиг.7-10 показано решение устройством задачи о наибольшем паросочетании, На фиг.1 обозначены; модель 1 ребра, блок 2 формирования топологии, блок 3 формирования управляющих сигналов, генератор 4 импульсов (далее обозначаемые соответственно МР, БФТ, БФУС и ГИ). Каждая МР содержит задатчики 5, 6 адресов, формирователь 7 временных интервалов, триггеры 8 — 11, узлы 12, 13 сравнения, элементы И 14 — 19, инвертор 20, элемент ИЛИ

21. (Далее позиции 5 и 6, 7 обозначаются соответственно ЗА и ФВИ). БФТ содержит регистры 22, 23, элементы И 24 — 29, инвер- 4 тор 30, элементы ИЛИ 31-35, 3A6 — кольцевой сдвиговый регистр; ЗА5, регистры 22, 23— сдвиговые регистры с входами записи, управления, сдвига; ФВИ7 — дискретная линия задержки, узлы 12, 13 сравнения —. 5 например, однородные двоичные сумматоры.

MP и БФТ предназначены для моделирования графа при автоматическом формировании его топологии. В .отличие от прототипа ЗА6 предназначен для записи обоих адресов (номеров) вершин (А1 и А2), инцидентных данному ребру. Узел 13 сравнения и триггер 10 предназначены для поразрядного сравнения А1 и А2 с задающими адресами (Аз и/или Аз2). Регистры 22, 23, элементы И 24, 25, 28, ИЛИ 31, 32 предназначены для записи, хранения и поочередной выдачи Аз1, А2; формирование Аз1, Аз2 рассмотрено ниже. При 2 п-разрядных 3А5, 3А6 регистры 22, 23 — Il-ðàýðÿäíые.

Элемент И 19, схемы 12 сравнения, ЗА5, триггер 9 предназначены для записи, хранения и сравнения с эталоном меток ребра.

Элементы И 29, ИЛИ всех МР предназначены для проверки наличия ребер с данными метками и/или инцидентных задающему узлу. Дальше называем. содержимое К-го разряда ЗА5 К-м признаком и обозначать Пк либо Пк (Пк=1 при Пк=О), БФУС предназначен для выдачи синхронизации 1с — 5 с, сигнала lc установки триггеров 9, 10 в единицу, сигнала Пр признака, задающих сигналов 1з — 6э, на основе поступающих на входы БФУС сигналов

1свх, 2свх, выдаваемых ГИ. В соответствии с логикой работы устройства импульсы серии tcex (2свх) будем называть информационными (адресными соответственно) импулЬсами.

Значение сигнала Пр равно значению признака, который либо записывается в ЗА5

МР, либо сравнивается с записанным ранее, посредством узла 12 сравнения. Запись и сравнение разнесены во времени за счет несовпадения сигналов Зз и 4с. (Триггеры 9,, 10 переключаются при подаче на их синхровходы сигналов 4с, 5с).

Сигналы 1с — 3c, Зз через элементы И

16 — 19 определяют режимы работы MP (запрас, начало, сброс, запись признака), а сигналы 1з, 4з — 6з — определяют режимы работы регистров 22, 23 (запись, выдача информации); сигнал Зз — вспомогательный, назначение раскрыто ниже. Техническая реализация БФУС может быть различной, Рассмотрим организацию работы устройства. Как и прототип, устройство работает посредством чередования двух периодов— информационного, когда на MP через элемент И 26 поступают информационные импульсы, и адресного, когда через элемент И

27 на MP поступают адресные импульсы, сдвигающие содержимые регистров 22, 23, ЗА5, ЗА6.

1797130

30

40

55

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

Рассмотрим режимы работы устройства, общие для всех задач: — Зп АР— запись адреса ребра, т,е, запись адресов инцидентных вершин ребра в регистры 22, 23; — BP (А1, В2) — выбор одного ребра, адрес которого записан в регистрах 22, 23, т,е, А1=Аз1, А2=Аз2;

ВРАз1 (ПмА Пн) — выбор множества ребер (м.б, и пустого) из числа инцидентных вершине с адресом Аз1, для которых . Пн=Пм=1; (точно так же выполняется выбор по любой другой совокупности признаков и по адресу Аэ2).

Частные случаи этого режима — BP Аз1 и ВР (Пм Л Пн), т,е, выбор К ребер, инциден тных Аз1, и ребер, для которых ПмЛ Пи=1, инцидеитных любым вершинам.

Если множество ребер, выбранных в третьем режиме, непустое, то сигнал 2ос (выход элемента И 29) равен нулю, т.к. при единичном состоянии триггеров 9, 10 выбранной МР, иа выходе элемента ИЛИ 21 этой МР, а также на входе элемента И 29, будет нулевой сигнал; нуль иа выходе элемента ИЛИ 21 выбранной МР, обеспечивает единицу на выходе инвертора 20 этой МР; последний сигнал открывает элементы И 14, И 16-19 той же МР, Будем называть устаиовкой (сбросом) триггера установку в единичное (нулевое соответственно) состояние; выдачей (сбросом) сигнала — выдачу сигнала, равного единице (нулю соответственно); будем обозначать Пн; = 1 — запись признака

Пн в 3А5 выбранной (выбранных) МР, ЗпАР обеспечивает запись в регистры

22, 23 адресов А1, А2 одной МР из числа выдавших сигналы прерывания. Рассмотрим режим ЗпАР на примере (фиг,2). На выходах трех МР есть сигналы прерывания.

Режим начинается установкой всех триггеров 9, 10 и выдачей сигнала 1з, задающего режим для регистра 22. После этого сигнал

5с выдается в кадом такте сдвига, сигнал 4с не выдается, поэтому триггеры 9 остаются в единице.

В нашем примере единицы с выходов

ЗА6 в МР1 2 поступают на выходы элементов И 14тех же МР; через элементы ИЛИ 35

И 28 они поступают на вход регистра 22 и через элемент ИЛИ 31 — на входы узлов 13 сравнения всех MP. После первого импульса 5с сбрасывается триггер 1ОМРЗ, в последнем разряде 3А6 которой записан нуль, После первого адресного импульса, единица с выхода И 28 записывается в первый разряд регистра 22. Нуль триггера 10 МР3 закрывает элемент И 14 М РЗ, поэтому дальше содержимое ЗА6 на элемент ИЛИ 34 не поступает. Следующие два такта сдвига протекают точно так же. После третьего адресного импульса в регистре 22 записан

Аз1=101, БФЧС сбрасывает сигнал 1з и выдает сигнал 4з, обеспечивая запись Аз2 в регистр 23. Четвертый адресный импульс не меняет состояния триггеров 10 МР1, 2; после пятого импульса триггер 10 М Р1 сбрасывается сигналом от узла 13 сравнения.

После шести адресных импульсов в регистрах 22, 23 записаны адреса Аз=101 и

Аз2=011, В общем, режим ЗпА обеспечивает запись в регистры 22, 23 адресов той МР, которая содержит в правых разрядах ЗА6 больше единиц, ь

BP (А1, А2) отличается от ЗпАР только. . тем, что адреса Аз1, Аз2 выдаются на узлы .

13 сравнения всех MP не с выхода элемента

И 28, а с выхода регистра 22 или 23, через элементы И 24, И 25. В этом режиме сигналы

1з, 4з равны нулю, поэтому элемент И 28 закрыт, а в регистрах 22, 23 информация ци р кули рует.

Режим начинается установкой триггеров 9, 10 и выдачей сигнала 5з; на выход элемента ИЛИ 31 поступает содержимое регистра 22, т.е. Аз1. Сравнение Аз1 с А1 всех

MP выполняется, как описано выше. Затем сигнал 5а снимается, выдается сигнал 6з и на выход элемента ИЛИ 31 поступает Аз2 из регистра 23, После 2п тактов сравнения остается на единице триггер 10 той МР, для которой А1=Аз1, А2=Аз2.

ВРАз1 отличается от ВР (А1, А2) только тем, что задающим является единственный адрес — Аз1, который сравнивается с А1 и А2 всех MP. При этом триггеры 9, 10 устанавливаются дважды — в начале режима и после и тактов сдвига, а сигнал 5з выдается в течение 2п тактов (естественно, ВР Аз2 выполняется точно тэк же). Поэтому режим ВРАз1 можно рассматривать состоящим из двух последовательных режимов: ВРАз1(А1) и

ВРАЗ(А2), т.е. выбор тех МР, для которых

А1=Аз1 и тех МР, для которых А2=Аз1.

ВРАз1 /ПнлПм) отличается от ВРАз1 тем, что в н-м и м-м тактах сдвига выполняется сравнение содержимых ЗА5 с эталонным признаком, равным единице. Последний поступает в этих тактах на общий вход всех узлов 12 сравнения. Сравнение выполняется.выдачей в тех же тактах сигналов 4с, по которым переключаются триггеры 9, B этом случае режимы ВРАз1(А1)/ПнЛ Пм) и

ВРАз1(А2) (ПнЛ Пм), выполняются последо13

14

1797130

30

40

Заявляемое устройство работает по следующему алгоритму.

1. Построить начальное паросочетание такое, чтобы в графе не было ребер, инци55 ченные, МР4 не помечаются, т.е. для нее П2

= ПЗ=О.

VtO. После одного информационного импульса кончает работу МР5.

АП, T.ê, Аз1 = 010 помечен как конечный, анализируется Аз2 = 100. Ребро 5 кончилось первым в этом узле, поэтому оно помечается; ПЗ: = 1. Т.к. для ребра 5 П6 = 1, работа устройства прекращается. Окончательные содержимые всех ЗА5 приведены на фиг,6г, Дерево кратчайших путей показано на фиг.бд; кратчайший путь между узлами 1 и 4— это ребра 1, 5, вес этого пути, равный суммарному числу информационных импульсов, поступивших на устройство — 4.

Задача 3. Решается на основе модифицированного алгоритма Эдмондса. Модификация обусловлена техническими особенностями устройства и не затрагивает математических аспектов алгоритма, Далее называем вершины и ребра, принадлежащие (не принадлежащие) паросочетанию, черными (белыми соответственно). Вершина белая, если ей не инцидентны черные ребра. Суть алгоритма .Эдмондса состоит в последовательном поиске аугментальных цепей (далее обозначаемых АЦ), т.е, цепей, ребра которых чередуются по цвету, а обе крайние вершины — белые. Перекраска ребер этой АЦ позволяет получить новое паросочетание, содержащее на одно ребро больше предыдущего. Для поиска таких цепей строятся альтернирующие деревья (АД), с корнем в непросмотренной вершине (белой), все четные (нечетные) ярусы которого черные (белые соответственно). Если АД достроено до конца. а АЦ в нем нет(все висячие вершины черные), корень дерева помечается как просмотренная вершина и строится новое АД, если это возможно. Процесс продолжается, пока есть непросмотренные белые вершины. Последнее из найденных паросочетаний — наибольшее;

Если при построении АД выявляется "цветок", т.е. цикл нечетной длины, то он "стягивается", что позволяет отыскать любую АЦ, проходящую через "цветок". После "стягивания" цветка построение данного АД возобновляется, начиная с корня. дентных двум белым вершинам, 2. Выбрать из .непросмотренных белых вершин вершину ХА, если таких вершин нет, то 9, 3. Построить первый ярус АД с корнем в ХА.

4. Построить черный ярус АД; если АД достроено до конца, то 6; если при построении этого яруса получился цветок, то 7, иначе 5.

5. Построить нечетный ярус АД: если найдена белая вершина ХВ, то 8, если при построении этого яруса получился цветок, то 7, иначе 4.

6. Пометить XA как просмотренную, перейти к 2.

7. Пометить все ребра цветка, перейти к

3, 8. Найти АЦ XB„..XA; изменить окраску ее ребер.

9. Конец: паросочетание, построенное последним, наибольшее.

Один из вариантов записи признаков в

ЗА5 может быть следующим.

П1 — ребро инцидентно корню моделируемого АД;

П2(ПЗ) — ребро ориентировано от А2 к А1 (от А1 к А2 соответственно);

П4 — ребро принадлежит цветку;

П5 — ребро инцидентно просмотренной белой вершине;

П6 — ребро черное, Рассмотрим решение задачи на примере графа (фиг,7а). Содержимые 3А6 приведены на фиг,7б, во всех ЗА5 нули. Первый шаг алгоритма иллюстрируется фиг.7в-7ж.

Режим начинается с установки триггеров 8 всех МР, за чем следуют адресные циклы. Каждый из них выполняется так. После ЗпАР выбранное ребро окрашивается черным (П6; = 1), после чего сбрасываются сигналы прерывания с выбранной MP u смежных с ней. Процесс продолжается, пока есть несброшенные сигналы прерывания, В нашем примере, в первом адресном цикле выбирается МР10. Для МР10 П6; = 1, после чего сбрасываются МР, инцидентные

Аз1, т.е. 8, 9, 10 и МР, инцидентные Аз2, т.е.

2, 11, (Как отмечено ранее, повторный сброс не влияет на работу MP и всего устройства, поэтому здесь и далее повторно сброшенные MP не перечисляем). Окраска МР10 показана на фиг.7в. Сброшенные ребра отмечены крестиком и дальше нэ фиг.7 не изображаются, Затем в следующем адресном цикле выбирается МРЗ (фиг.7г). Она окрашивается и сигналы прерысания от MP 1, 3, 4 сбрасываются, Затем окрашивается

МР5 и сбрасываются МР5, МР6 (фиг.7д). Осталась несброшенной одна MP — МР7, которая окрашивается и сбрасывается в следующем адресном цикле. Ненулевые содержимые ЗА5 показаны на фиг,7е, полученные паросочетэния — на фиг,7ж.

Начинается второй шаг алгоритма — поиск непросмотренной белой вершины. Вначале

1797130 выполняется запрос белых ребер, инцидентных непросмотренным вершинам — запрос

/П6/ П5/. Затем выбранные ребра поочередно проверяются на их смежность с черными ребрами (т,е. выполняется проверка

Аз1/П6/, Аз2/П6/ (см. фиг.4а). Если найдена белая вершина, она становится корнем

АД, Иначе выбранное белое ребро сбрасывается и начинается следующий адресный цикл — проверка другого белого ребра. Если все белые ребра сброшены, а корень АД не найден, решение задачи окончено.

Рассмотрим фиг.7ж. НАП; устанавливаются триггеры 8 всех белых МР; МР1, МР2, МР4, МР6, МР8, МР9, МР11. Затем в режиме ЗпАР из них выбирается МР9. Обе ее крайние вершины 4 и 7 — черные, МР9 сбрасывается. Затем выбирается МР6. Обе ее крайние вершины — 5 и 6 — черные, МР6 сбрасывается. После этого выбирается

МР11 — в регистрах 22, 23 записаны адреса

1010, 1001, Вершина 10 не имеет инцидентных черных ребер, т.е. является белой; второй шаг алгоритма выполнен, все сигналы прерывания сбрасываются. Устройство переходит к выполнению третьего шага алгоритма — построению первого яруса АД с корнем в ХА (в вершине 10). Далее считаем, что адрес корня — Аз1 (для Аз2 рассуждения аналогичны).

Построение первого яруса АД состоит в том, что вначале все ребра, инцидентные корню АД, помечаются (П1: = 1), и ориентируются от корня, Затем на эти МР посылается запрос, после чего они выдают сигналы прерывания. При обработке последних выдается запрос на смежные черные ребра.

Затем поочередно моделируются четные (черные) и нечетные (белые) ярусы, при этом каждое ребро ориентируется в одном либо двух направлениях (фиг.8а,б); в последнем случае, ребро замыкает цветок (фиг.8в,г, ребра V>. Чь). Если замыкающее ребро не помечено (П4 = О), построение АД прерывается и начинается пометка цветка, Во всех других случаях выдается запрос на следующий ярус, (фиг,8д; запрос показан стрелками в начале ребра). Ребро ориентируется, как и в задаче о кратчайшем пути на неориентированном графе, в направлении от вершины, помеченной как конечная к вершине, не имеющей такой пометки. B случае, если обе крайние вершины ребра имеют такую пометку, ребро ориентируется в двух направлениях. Кроме этого, каждое черное ребро проверяется на принадлежность ранее построенному цветку (т.е. по признаку П4). Если для этого ребра П4 = i, то запрос выдается на все смежные непройденные ребра от обеих его крайних вершин

15

20 конце, ребра, на которые послан запрос—

30

55 (фиг,8е), за счет чего цветок "стягивается", Если смоделированный черный ярус — последний в АД, то корень АД помечается. как просмотренная вершина, а признак корня—

П1 — стирается (т,е, вы полн я ется В Р/П1/, П1:=О, П5:-1).

Каждое белое ребро, кроме ребер первого яруса, проверяется на инцидентность белой вершине ХВ; если это так, то есть АЦ

ХВ,,ХА. Рассмотрим построение АД на том же примере (фиг,7ж). На фиг.9а — 9г показано построение соответственно первого, второго, третьего и четвертого ярусов АД. Это построение выполняется без особенностей, его ход определяется чередованием черных и белых ярусов дерева, т.е. нечетных и четных шагов моделирования АД, ЗА5 отработавших MP показаны на фиг.9д — 9з.

Пройденные ребра обозначены стрелками в стрелками в .начале. Иначе моделируетсв

МР6 (пятый ярус АД). После окончания она ориентируется в обоих направлениях, т.к. вершины 5 и 6 помечены как конечные, Т,к, для МР6 П4 = О, на пятом ярусе моделирование АД прерывается и начинается пометка цветка (фиг,9и, шаг 7 алгоритма). Этот шаг выполняется посредством режимов запрос, пометка, проверка, сброс. Замыкающее ребро (6, фиг:9и) помечается (П4: = 1), затем признак П4 = 1 распрстраняется от крайних вершин этого ребра по пройденным (т,е. ориентированным) ребрам встречно их ориентации (штриховая линия на фиг.9и). Это означает, что запрос посылается из начальной вершины помеченного ребра на смежное ребро, входящее в эту вершину.

Пометка ребер цветка продолжается до достижения начальной вершины цветка (вершина 7 фиг.9и). Признаком достижения начальной вершины является единственный сигнал прерывания (от МР10 на фиг.9и), в отличие от большего числа сигналов прерывания на каждом из предыдущих шигов пометки цветка, Обратимся к нашему примеру (фиг.9и). Исходное состояние: Аз1 = 0110, Аз2 = 0101, для МР6 П2 = ПЗ = 1.

HA1l. Для МР6 П4: = 1, из крайних вершин 5, 6 посылаются запросы на входящие в эти вершины ребра с П4 = О. Сброс МР6.

АП, МР5, МР7 выдают сигналы прерывания. Первой выбирается МР5, сброс МР5.

Сигнал 1ос равен единице, что означает наличие сигнала прерывания, т.е. начальная вершина цветка не достигнута. В Р(Аз1, Аз2), П4 . = 1, обеспечивает пометку МР5, после чего. выдается запрос на МР, входящую в вершину 4 — МР9, Затем обрабатывается сигнал преырвания от МР7: П4 = 1, запрос на МРЗ, сброс, МР8, МР9 в следующем АП

1797130

10

40 тации ребра (фиг.4г), 55 у

На фиг.4г показан выбор ребер с А1 =

Аэ1, Пн = 1, и ребер с А2 =Аз1, Пм =1.

Режим запрос (начало, сброс, запись н признака) выполняются при выдаче сигнала

1 с (2с, Зс, Зз соответственно); эти сигналы г вательно в течение 2 тактов каждый, т.к, Пн и Пм могут принимать любые значения от 1 до 2п, Сигнал 5э. как и для режимов

ВРАэ1(А1) и ВРАз2(А2), выдается в течение и тактов, Поясним режим на примере (фиг.3), Пусть Аз1=101, ПнЛПм=П2ЛП5, т.е, нужно выбрать ребра, инцидентные Аз1, для которых П2л П5 = 1. Режим начинается установкой триггеров 9, 10. На первом такте сдвига сбрасываются триггеры МРЗ, МР4; на втором такте — на вход Пр выдается сигнал, который сравнивается с П2 всех MP. Ha выходе узла 12 МР4 появляется сигнал, который по сигналу 4с, выданному одновременно с 5с, сбрасываеттриггер 9МР4; После третьего такта сдвига остаются в единице триггеры 10МР1, МР2 и триггеры 9 всех МР, кроме МР4, Затем сигналы 5с не выдаются. триггеры 10 не переключаются в следующие

2п = 6 тактов. На пятом такте сдвига единица на входе Пр сравнивается с П5 всех МР; в результате сбрасывается триггер 9МР1, Через 2п тактов сдвига ЗА возвращаются в исходное состояние; режим ВРАз1{А1) {П24 25

П5) завершен; выбрана МР2 (у нее триггеры

9, 10 не сброшены, на выходе ее инвертора — еди ни ца).

Начинается ВРАз1(А2) (П2 П5). После установки триггеров 9, 10, сравнение Пр с 30

П2 и П5 выполняется, как описано выше, но сигналы 5с начинают поступать íà MP после трех адресных импульсов; этим обеспечивается сравнение А2 с Аз1. После 2п тактов сдвига остаются в единице триггеры 9 МР2, 35

МРЗ, МР5, и триггер 10 МРЗ, т.е. выбрана

МРЗ, По фиг.3 видно, что ребра 2, 3 удовлетворяют заданным условиям. Из описанного ясно выполнение ВРАз1 и BP (ПнлПм). А именно, для первого (второго) из них сигнал

4с (5с соответственно) не выдается.

Ассоциативный поиск по совокупности признаков, выполняемый прототипом — это выбор ребер по этой совокупности признаков, Например, поиску по совокупности признаков ПндПмлПт, соответствует режим

ВР (ПнЛПм Пт).

На основе режима выбора строятся другие режимы, в частности, проверка признака (совокупности признаков) для одного 50 ребра, (фиг.4а, 46 соответственно), проверка признака для всех ребер, инцидентных

Аз1 (фиг.4в), и проверка для тех же ребер разных признаков, в зависимости от ориенпоступают на выбранные МР через элементы И 16-19, открытые выходным сигналом инвертора 20.

В режиме "Запрос" сигнал с выхода элемента И 16 устанавливает триггер 11. разрешая прохождение в следующем информационном периоде импульса через элемент И 15 на вход триггера 8; в результате MP выдает сигнал прерывания. Запрос может выполняться многократно.

В режиме "Начало" сигнал 2с через элемент И 17 выбранных MP поступает на входы ФВИ, разрешая им отсчет импульсов в следующем информационном периоде. Пометка каждого оконченного ребра и связь элемента И 17 с нулем триггера 8 обеспечивают однократное выполнение режима "Начало" для каждой МР, В режиме "Сброс" сигнал Зс через элемент И 18 сбрасывает триггеры 8, 11 выбранных МР, чем снимается сигнал прерывания и обеспечивается воэможность многократного выполнения режима "Запрос".

В режиме "Запись признака" сигнал Зз, через элемент И 19 задает для 3А5 выбранных МР режим записи, позволяя в следующем такте сдвига записать в нужный разряд

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

Рассмотрим решение на устройстве таких задач: поиск оптимального пути на ори енти рован ной сети с логическим функциями в узлах И, ИЛИ (задача 1); поис., кратчайшего пути на неориентированного сети (задача 2), поиск наибольшего паросочетания в графе общего вида {задача 3).

{Модель задачи о кратчайшем пути— сеть с узлами ИЛИ, сетевой график — сеть с узлами И).

При описании задач адресный период будем обозначать АП, информационный—

ИП, начальный адресный период — НАП (организуется выдачей сигнала 2з). При решении задач 1, 2 для MP выполняется режим

"Начало", при решении задачи 3 — режим

"Запрос".

Считаем, что в задачах 1, 2 отыскивается. оптимальный путь между на чальным и,:(0нечным узлами сети; дерево оптимальных путей — это дерево с корнем в нача lb îì узле сети. В исхОдном состоянии начальный зел сети записан в регистре 22, конечный— в регистре 23.

Если ребро(А1, А2) помечается как приадлежащее дереву, то за этим следует Начало" ребер, выходящих из его конечноо узла; каждый адресный цикл (т.е. обра1797130

5

55 ботка сигнала прерывания от MP (А1, А2), завершается сбросом этой MP. Запись и интерпретация признаков в ЗА5 может быть произвольной.

Один из возможных вариантов записи некоторых признаков в ЗА5 для задач 1, 2 приведен ниже, П1 — ребро инцидентно начальному узлу сети и ориентировано от А2 и А1;

П2 — ребро принадлежит дереву оптимальных путей и ориентировано от А2 и А1;

П5 — ребро окончено;

П6 — ребро инцидентно конечному узлу сети.

После режима Зп АР в задачах 1, 2 для

MP c А1 = Аз1, А2 = Аз2 выполняется П5: =

1; "Начало" выполняется для ребер с П5 = О.

Другие признаки описаны при рассмотрении конкретных задач.

Задача 1 (решается прототипом).

Все ребра ориентированы от А2 к А1.

Кроме общих признаков для задач 1,2 используется П4 — ребро входит в узел И, Ребро получаем П2 = 1, если оно окончилось последним из ребер, входящих в узел И (т.е. нет ребер, входящих в тот же узел, для которых П4 П5 = 1); либо если оно окончилось первым из ребер, входящих в у%л ИЛИ (т,е. нет ребер, входящих в тот же узел, для которых П2 = 1), Рассмотрим решение задачи 1 для сети, фиг,5а. Начальные содержимые ЗА5 — на фиг.5б, веса ребер указаны на фиг,5а.

HAIl. ВРАз1(А2); П1 = 1; ВРАз2(А1); П6:

= 1; Начало: /П1/, В результате П1 (Пб) записан в МР1, МР2, МРЗ (MP2, МР5, МР6 соответственно); "начало" — íà МР1, МР2, МРЗ, 3А5 показаны на фиг.5в.

ИП. После двух информационных импульсов окончил работу ФВИ МРЗ, который выдает сигнал прерывания.

АП. B регистр 22{23) записывается 010 (001 соответственно, т.к. нет помеченных П2 ребер, входящих в узел 010 типа ИЛИ, то ребро 3 помечается, т.е. для него П2: = 1.

Разрешение начала — на МР4, 6.

ИП. После одного информационного импульса выдают сигнал прерывания МР2, M Р6.

АП. Для анализа первой выбирается

МР2 (см. режим ЗпАР). Ее A1 = 100 и А2 =

001 записываются в регистры 22, 23. Узел 4 — типа И; среди входящих в него ребер есть неоконченное — 5; поэтому ни МР2, ни МР6 не помечаются.

ИП, После одного информационного импульса завершает работу МП4.

АП. Выполняется так же, как и для МР3; для МР4 П2; =- 1; разрешается начало МР5, ИП. После одного информационного импульса завершает работу ФВИ МР1.

АП. T.ê. для МР4 П2 = 1, т.е. уже есть помеченное ребро, входящее в узел 3, то ребро 1 не помечается.

ИП. После двух импульсов информационной серии завершает работу ФВИ МР5.

АП. T.к. все ребра, входящие в узел 4, окончены (П5 = 1), то ребро 5 помечается П2;

= 1; т.к. помеченное ребро инцидентно конечному узлу сети (П6 = 1), то на этом решение задачи оканчивается.

Оптимальный путь — ребра 5, 4, 2; суммарное число информационных импульсов, поступивших на MP в процессе решения, равное 7, т.е. весу оптимального пути на сети между узлами 1, 4.

Задача 2, В исходном состоянии ребра определяются инцидентными узлами, адреса которых записаны Ф ЗА6 в произвольном порядке. Ребра ориентируются в процессе решения; ребер, входящих в начальный узел сети, нет. Кроме признаков, общих для задач 1, 2, используются следующие:

ПЗ вЂ” ребро принадлежит дереву и ориентировано от А1 и А2;

П4 — ребро инцидентно начальному узлу сети и ориентировано от А1 к А2. Ребро (А1, А2) получает, например, признак П2 = 1, если А1 не начальный узел сети, и ребро (А1, А2) окончилось первым в А1, Если ребро не помечается по А1 (признаком П2), то проверяется возможность его пометки по А2.

Рассмотрим пример фиг,б; 3А6 показаны на фиг.бб; в 3А5 записаны нули.

HAIK, В РАэ1 (А2); П1; = 1, В Р Аэ1 (А1); П4:

= 1; ВРАз2; П6: = 1, Начало; /П1/; /П4/. ЗА5 приобрели вид фиг,бв; начаты МР1, 2, 3.

ИП. После двух информационных импульсов окончила работу МР3;

АП. Т.к. Аз1 = 001 — начальный узел сети

{для МРЗ П4 = 1), то ребро от А2 к А1 не помечается и устройство переходит к проверке Аз2 = 011. T.к, 001 — не начальный и нет ребер, для которых он был бы помечен как конечный, МРЗ помечается по адресу

011, т.е. ПЗ; = 1. T,к, 011 — не конечный адрес (для МРЗ Пб = О), то начинаются инцидентные 011 ребра 4, 6.

Nil. После одного информационного импульса кончают работу МР1, МР4.

АП, Первой выбирается для анализа

МР1. T,к. Аэ1 = 001 — начальный узел сети, то проверяем ориентацию ребра от А1 к А2.

T.ê. нет помеченных ребер, инцидентных

Аз2 = 010. то для МР1, ПЗ: = 1, и сигнал

"Начало" выдается на МР5. Затем анализируется МР4, T.к, среди ребер, инцидентных обоим конечным узлам ребрам 4, есть поме17

1797130

20

ЗО

50 обрабатываются аналогично. Обе эти MP выдают запрос на МР10. В следующем АП, МР10 выбирается и сбрасывается, больше сигналов прерывания нет,. пометка цветка. окончена. Устройство возвращается к моде- 5 лированию АД, восстановив исходные состояния всех МР, кроме 1. яруса. А именно, в режиме ВР /П1/, П2: = 0; ПЗ: = О, для всех

МР, не инцйдентных корню, стираются.признаки П2, ПЗ. Затем следует запрос /П1/. В результате все MP 1-го яруса, сохранившие ориентацию, выдают сигналы прерывания, после чего моделирование АД продолжается, как раньше, В примере фиг.9, повторное моделирование АД начинается от состояния 15 на фиг.9а, 9д, с той разницей, что ребра 5-9 имеют йризнак цветка (П4 = 1}. Далее АД моделируется согласно фиг.96-9в, вплоть до обработки сигнала прерывания от МР5.

Для нее П4 = П6 = 1, поэтому от вершины 4, 5 начинаются непройденные ребра 4; 6, Обработка МР7 приводит к прежним результатам. Четвертый шаг моделирования показан на фиг,10а. 106. В следующем АП обрабатываются сигналы прерывания от МР4, МР6, 25

Ребра, смежные ребру 6, уже пройдены, поэтому "рост" АД продолжается только от вершины 3. После 7-го шага моделирования, 3А5 и граф имеют вид фиг.10в, 10г соответственно. Ребро 1 (инцидентно белой вершине, что означает наличие АЦ 0001,...1010.

Начинается. шаг 8,— перекраска ребер АЦ, Зто выполняется с учетом ориентации ребер и чередованя цветов. А именно, черные ребра выбираются для перекраски одно- 35 значно, из белых. выбираются принадлежащие цветку либо ориентированные встречно направлению окраски. Последнее означает, что иэ начальной вершины перекрашенного ребра выдается запрос "на 40 смежное ребро; входящее в эту вершину

При этом выбранное для перекраски белое ребро и белые ребра, смежные с ним, исключаются из дальнейшего рассмотрения, путем стирания признаков П2, ПЗ, П4. С учетом технических качеств устройства, после выбора ребра для перекраски посылается запрос на ребро, которое будет перекрашено следующим; а затем ребро перекрашивается и исключаются, если нужно, смежные с ним белые ребра. Процесс продолжается до перекраски ребра с П! = 1, т.е. ребра из первого яруса АД. Значение П1 проверяется для каждого белого ребра, что дальше не оговаривается. Для фиг.10е: в регистрах 22, 23, записаны адреса 0010 и

0001. Выдается запрос на смежное черное ребро — ребро 3. затем — сброс П2, ПЗ, П4 для всех белых ребер. инцидентных вершинам 1 и 2. Этот сброс выполняется для каж!

8 дого выбранного белого ребра, что дальше не оговаривается. Для ребер 1, 2 этот сброс не приводит ни к каким результатам, т.к. для этих ребер П2 - ПЗ = П4 = О. Затем ребро окрашивается (П6 5 =1), и МР1 сбрасывается, В следующем АП выдает сигнал прерывания МРЗ. От МР3 выдается запрос на смежное белое ребро, входящее в крайнюю вершину (ребро 4), затем для МРЗП6; = О, сброс МРЗ. Обработка МР4 выполняется так же, как МР1. Запрос поступает на смежное черное ребро — 5, после сброса П2, ПЗ, П4, ребра 3, 4, 9 теряют ориентацию, а ребро 9 — еще и ппррииззннаак к ццввееттккаа, Для МР4 П6: = 1; сброс МР4, МР5 обрабатывается, как МРЗ, Запрос от МР5 поступает íà МР6, с П4 = 1.

На МР9 запрос от МР5 не поступает, т.к. для

МР9 П2 = ПЗ = П4 = О. МР6 обрабатывается, как МР4. Дальше процесс продолжается аналогично; от МР10 запрос поступает на

МР11, т.к. для МР2 П2 = ПЗ = П4 = О. Для

МР11 П1 =1, поэтому перекраской этого ребра оканчивается перекраска АЦ

0001Ä,.1010, Затем стирается признак П1 для ребер 1 яруса. Результирующее паросочетание и содержимые 3А5 приведены на фиг.10д, 10е соответственно, Формула изобретения

Устройство для моделирования сетевого графика, содержащее генератор импульсоа, блок формирования управляющих сигналов, блок формирования топологии, блок моделей ребер по числу работ исследуемого сетевого графика, причем каждая модель ребра содержит формирователь временных интервалов, первый — четвертый триггеры, первый — четвертый элементы И, элемент ИЛИ, инвертор, первый и второй узлы сравнения, эадатчик адреса начального узла и задатчик адреса конечного узла, выходы которых подключены соответственно к первым входам первого и второго узлов сравнения, выходы которых подключены со- ответственно к первым входам первого и второго триггеров, выходы второго задатчика и второго триггера подключены соответственно к первым входам первого элемента

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

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

1797130

20 содержит инвертор, первыф — четвертый элементы ИЛИ, первый — третий элементы

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

10 управляющих сигналов и к второму входу второго триггера, третий вход которого подключен к пятому:синхронизирующему выходу блока формирования управляющих сигналов, в блок формирования топологии

15 дополнительно введены четвертый, пятый и шестой элементы И, пятый элемент ИЛИ, первый и второй регистры, первые входы которых подключены к выходу третьего элемента И, вторые вхадь1 — к выходу четверто20 го элемента И и к входу пятого элемента

ИЛИ, третьи входы — соответственно к первому входу первого элемента ИЛИ, к второ-. му входу первого элемента ИЛИ и к четвертому задающему выходу блока формирования управляющих сигналов, а выходы — к первым входам пятого и шестого элементов И, вторые входы которых подключены соответственно к пятому и шестому задающим выходам блока формирования

30 управляющих сигналов, а выходы — к второму и третьему входам пятого элемента ИЛИ, выход которого подключен к второму входу второго узла сравнения каждой модели ревыходу четвертого элемента ИЛИ и к выходу первого элемента ИЛИ, выход третьего элемента ИЛИ подключен к второму осведоми40 тельному входу блока формирования управляющих сигналов, первый и второй синхронизирующие входы которого подключены к соответствующим выходам генератора импульсов, 35 бра, первый и второй входы четвертого элемента И подключены соответственно к

17ñ 71.5

1

8P(PА) Д Д / „

Г !

L н =/

-rP

1 Г ф/4/ г

I n;-q ! !

-! !

J /ц)п./

Ъ4

Ом Ъ-

Ю. Я/

ИЛи

М юг

/Щ л рррр

МР$

МРР

ЩАДЯ

335 Я,8 б ф

ЮК l7 т

МРг

МРЗ

/ЮФ

ПР5

Юб

ЛР

Р7Р2 иРЗ т1

ЮР5

/ Щ

Г

1 !

I ! !

t !

Г

I ! ! ! !

7@8 Лу

Г

0 — — fi g

1797130 а) .ЯР 8< /76 Ю4 п1йбп504/и Я

KA

ЮРГ яИ

ФР4

Ю5 пР8

Фиг. Б

1797130

04 mr

Ю/ у

NR иМ

ЯК

1797130

Р7Р8 юг

ИК

1797130

° е м

Ю г, / г р,3

l7z=ns=d

ЯГ М и- н=пИ ю=а= М

ПРО/ХРУ к (Т) 1797130

1797130

Составитель О,Голованова .

Техред М.Моргентал Корректор Q.ÊðàBöoâà

Редактор О.Стенина

Заказ 654 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г. Ужгород. ул.Гагарина 101

87854 9 Я/

ЯИ

Ю8

-/ РЗ Р4 ,мД5 мРС

/бР7

МУ

ФУ

/ РВ

/ ®

81/54 38Г

ЯР4 Ю

Ю3 ю4 юЯ

/ РЮ

МРf

Ю3

// 3

/7/ Ю

/ Ю

МР/

NP$ щц

М5

ЯР6 .ИР7

ЮЯ

Ю3

МРЕМ

ИРВ