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

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

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

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

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

VJ о

XJ

со

о

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

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

. Недостаток прототипа - невозможность решения на нем задачи.о наибольшем паро- сочетании в графе общего вида. Этот недостаток обусловлен тем, что устройство не

позволяет моделировать неориентированные графы с пометкой ребер в процессе моделирования.

Цель изобретения - расширение области применения за счет решения задачи о

0 наибольшем паросочетании в графе общего вида.

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

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

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

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

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

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

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

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

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

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

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

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

На фиг.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, инвертор 30, элементы ИЛИ 31-35, ЗАб - кольцевой сдвиговый регистр; ЗАБ, регистры 22, 23 - сдвиговые регистры с входами записи, управления, сдвига; ФВИ7 - дискретная ли- ния задержки, узлы 12, 13 сравнения - например, однородные двоичные сумматоры.

МР и БФТ предназначены для моделирования графа при автоматическом формировании его топологии. В отличие от прототипа ЗА6 предназначен для записи обоих адресов (номеров) вершин (А1 и А2), инцидентных данному ребру. Узел 13 сравнения и триггер 10 предназначены для поразрядного сравнения А1 и А2 с задающими

адресами (Аз1 и/или Аз2). Регистры 22, 23, элементы И 24, 25, 28. ИЛИ 31, 32 предназначены для записи.хранения и поочередной выдачи Аз1.А2; формирование Аз1,Аз2 рас- 5 смотрено ниже. При 2 n-рззрядных ЗА5. ЗАб регистры 22, 23 - п-разрядные.

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

0 Элементы И 29, ИЛИ всех МР предназначены для проверки наличия ребер с данными метками и/или инцидентных задающему узлу. Дальше называем содержимое К-го разряда ЗА5 К-м признаком и обозначать Пк

5 либо Пк ( при ).

: БФУС предназначен для выдачи синхронизации 1с - 5 с, сигнала Ic установки триггеров 9, 10 в единицу/сигнала Пр признака, задающих сигналов 1з-бз, на основе

0 поступающих на входы БФУС сигналов 1свх,2свх, выдаваемых ГИ. В соответствии с логикой работы устройства импульсы серии IC BX (2свх) будем называть информаци- онными (адресными соответственно)

5 импульсами.

Значение сигнала Пр равно значению признака, который либо записывается вЗА5 МР, либо сравнивается с записанным ранее, посредством узла 12 сравнения. Запись

0 и сравнение разнесены во времени за счет несовпадения сигналов Зз и 4с. (Триггеры 9, . ТО переключаются при подаче на их синх- ровходы сигналов 4с, 5с).

Сигналы tc-Зс, Зз через элементы И

5 16-19 определяют режимы работы МР (запрос, начало, сброс, запись признака), а сигналы 1з, 4з-6з - определяют режимы работы регистров 22, 23 (запись, выдача информации); сигнал З.з - вспомогательный,

0 назначение раскрыто ниже. Техническая реализация БФУС может быть различной.

Рассмотрим организацию работы устройства. Как и прототип, устройство работает посредством чередования двух периодов 5 информационного, когда на МР через элемент И 26 поступают информационные импульсы, и адресного, когда через элемент И 27 на МР поступают адресные импульсы, сдвигающие содержимые регистров 22, 23,

0 ЗА5, ЗА6..

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

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

Рассмотрим режимы работы устройства, общие для всех задач:. .

- Зп АР - запись адреса ребра, т.е. запись адресов инцидентных вершин ребра в регистры 22, 23;

- ВР (А1, В2) - выбор одного ребра, адрес которого записан в регистрах 22, 23, т.е. ,

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

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

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

ЗпАР обеспечивает запись в регистры 22, 23. адресов А1, А2 одной МР из числа выдавших сигналы прерывания. Рассмотрим режим ЗпАР на примере (фиг,2). На выходах трех МР есть сигналы прерывания. Режим начинается установкой всех триггеров 9, 10 и выдачей сигнала 1з, задающего режим для регистра 22. После этого сигнал 5с выдается в кадом такте сдвига, сигнал 4с не выдается, поэтому триггеры 9 остаются в единице.

В нашем примере единицы с выходов ЗАб в МР1 2 поступают на выходы элементов И 14тех же МР; через элементы ИЛИ 35, И 28 они поступают на вход регистра 22 и через элемент ИЛИ 31 - на входы узлов 13 сравнения всех МР. После первого импульса 5с сбрасывается триггер 10МРЗ, в последнем разряде ЗА6 которой записан нуль.

После первого адресного импульса, единица с выхода И 28 записывается в первый разряд регистра 22. Нуль триггера 10 МРЗ закрывает элемент И 14 МРЗ, поэтому дальше содержимое ЗА6 на элемент ИЛИ 34 не поступает. Следующие два такта сдвига протекают точно так же. После третьего адресного импульса в регистре 22 записан . БФУС сбрасывает сигнал 1з и выдает сигнал 4з, обеспечивая запись Аз2 в регистр 23. Четвертый адресный импульс не меняет состояния триггеров 10 МР1, 2; после пятого импульса триггер 10 МР1 сбрасывается сигналом от узла 13 сравнения.

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

больше единиц,

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

13 сравнения всех МР не с выхода элемента И 28, а с выхода регистра 22 или 23, через

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

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

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

В,РАз1 отличается от ВР (А1, А2) только

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

и тех МР, для которых . ВРАз /ПнАПм) отличается от ВРАз1 в н-м и м-м тактах сдвига выполняется сравнение содержимых ЗА5 с эталонным признаком, равным единице. Последний

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

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

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

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

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

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

2. Выбрать из непросмотренных белых вершин вершину ХА, если таких вершин нет, то 9.

3. Построить первый ярус АД с корнем в ХА..

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

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

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

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

8. Найти АЦ ХВ....ХА; изменить окраску ее .

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

Один из вариантов записи признаков в ЗА5 может быть следующим.

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

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

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

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

П6 - ребро черное.

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

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

выполняется запрос белых ребер, инцидентных непросмотренным вершинам - запрос /П6ЛП5/. Затем выбранные ребра поочередно проверяются на их смежность с черными ребрами (т.е. выполняется проверка Аз1/П6/, Аз2/Пб/ (см. фиг.4а). Если найдена белая вершина, она становится корнем АД. Иначе выбранное белое ребро сбрасывается и начинается следующий адресный цикл - проверка другого белого ребра. Если все белые ребра сброшены, а корень АД не найден, решение задачи окончено.

Рассмотрим фиг.7ж. НАП; устанавливаются триггеры 8 всех белых МР: МР1, МР2, МР4, МР6, МР8, МР9, МР11. Затем в режи- ме ЗпАР из них выбирается МР9, Обе ее крайние вершины 4 и 7 - черные, МР9 сбрасывается. Затем выбирается МРб. Обе ее крайние вершины - 5 и 6 - черные, МР6 сбрасывается. После этого выбирается МР11 - в регистрах 22, 23 записаны адреса 101С, 1001, Вершина 10 не имеет инцидентных черных ребер, т.е. является белой; второй шаг алгоритма выполнен, все сигналы прерываний сбрасываются. Устройство пе- реходит к выполнению третьего шага алгоритма - построению первого яруса АД с корнем в ХА (в вершине 10). Далее считаем, что адрес корня -Аз.1 (для Аз2 рассуждения аналогичны).

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

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

(фиг,8е), за счет чего цветок стягивается, Если смоделированный черный ярус - последний в АД, то корень АД помечается, как просмотренная вершина, а признак корня - П1 - стирается (т.е. выполняется ВР/П1/, П1: 0, П5: 1).

Каждое белое ребро, кроме ребер первого яруса, проверяется на инцидентность белой вершине ХВ; если это так, то есть АЦ ХВ....ХА. Рассмотрим построение АД на том же примере (фиг.Тж). На фиг.9а-9г показано построение соответственно первого, второго, третьего и четвертого ярусов АД, Это построение выполняется без особенностей, его ход определяется чередованием черных и белых ярусов дерева, т.е. нечетных и четных шагов моделирования АД. ЗА5 отработавших МР показаны на фиг.9д-9з. Пройденные ребра обозначены стрелками в конце, ребра, на которые послан запрос - стрелками в хачале. Иначе моделируется, МР6 (пятый ярус АД). После окончания она ориентируется в обоих направлениях, т.к. вершины 5 и б помечены как конечные. Т.к. для МР6 П4 0, на пятом ярусе моделирование АД прерывается и начинается пометка цветка (фиг.Эи, шаг 7 алгоритма). Этот шаг выполняется посредством режимов запрос, пометка, проверка, сброс. Замыкающее ребро (6, фиг.-9и) помечается (П4: 1), затем признак П4 1 распрстраняется от крайних вершин этого ребра по пройденным (т.е. ориентированным) ребрам встречно их ориентации (штриховая линия на фиг.9и). Это означает, что запрос посылается из начальной вершины помеченного ребра на смежное ребро, входящее в эту.вершину. Пометка ребер цветка продолжается до достижения начальной вершины цветка (вершина 7 фиг.Эи). Признаком достижения начальной вершины является единственный сигнал прерывания (от МР10 на фиг.Эи), в отличие от большего числа сигналов прерывания на каждом из предыдущих шигов пометки цветка. Обратимся к нашему примеру (фиг.Эи). Исходное состояние: Аз1 0110, Аз2 0101, для МР6 П2 ПЗ 1.

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

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

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

Поясним режим на примере (фиг.З). Пусть , ПнАПм П2ЛП5, т.е. нужно выбрать ребра, инцидентные Аз1, для которых П2/1 П5 1. Режим начинается установкой триггеров 9, 10. На первом такте сдвига сбрасываются триггеры МРЗ, МР4; на втором такте - на вход Пр выдается .сигнал, который сравнивается с П2 всех МР. На выходе узла 12 МР4 появляется сигнал, который по сигналу 4с, выданному одновре- менно с 5с, сбрасывает триггер 9МР4. После третьего такта сдвига остаются в единице триггеры 10МР1, МР2 и триггеры 9 всех МР, кроме МР4, Затем сигналы 5с не выдаются, триггеры 10 не переключаются в следующие 2п 6 тактов. На пятом такте сдвига единица на входе Пр сравнивается, с П5 всех МР; в результате сбрасывается триггер 9МР1. Через 2п тактов сдвига ЗА возвращаются в .исходное состояние; режим ВРАз 1(А1) (П2И П5) завершен; выбрана МР2 (у нее триггеры 9, 10 не сброшены, на выходе ее инвертора - единица).

Начинается ВРАз1(А2) (П2 П5). После установки триггеров 9, 10, сравнение Пр с П2 и П5 выполняется; как описано выше, но сигналы 5с начинают поступать на МР после трех адресных импульсов; этим обеспечивается сравнение А2 с Аз1. После 2п тактов сдвига остаются в единице триггеры 9 МР2, МРЗ, МР5, и триггер 10 .МРЗ, т.е. выбрана МРЗ. По фиг.З видно, что ребра 2, 3 удовлетворяют заданным условиям. Из описанного ясно выполнение ВРАзТ и ВР (ПнИПм). А именно, для первого (второго) из них сигнал 4с (5с соответственно) не выдается.

Ассоциативный поиск по совокупности признаков, выполняемый прототипом - это выбор ребер по этой совокупности признаков, Например, поиску по совокупности признаков Пн/., соответствует режим ВР(ПнЛПмЛПт).

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

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

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

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

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

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

В. режиме Сброс сигнал Зс через элемент И 18 сбрасывает триггеры 8, 11 выбранных МР, чем снимается сигнал прерывания и обеспечивается возможность многократного выполнения режима Запрос.

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

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

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

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

При описании задач адресный период будем обозначать АП, информационный - ИП, начальный адресный период- НАЛ (организуется выдачей сигнала 2з). При решении задач 1, 2 для МР выполняется режим Начало, при решении задачи 3 - режим Запрос.

Считаем, что в задачах 1,2 отыскивается. оптимальный путь между начальным и конечным узлами сети; дерево оптимальных путей - это дерево с корнем в начальном узле сети. В исходном состоянии начальный узел сети записан в регистре 22, конечный - в регистре 23.

Если ребро (А1, А2) помечается как принадлежащее дереву, то за этим следует Начало ребер, выходящих из его конечного узла: каждый адресный цикл (т.е. обработка сигнала прерывания от МР (А1, А2), завершается сбросом этой МР. Запись и интерпретация признаков в ЗА5 может быть произвольной.

Один из возможных вариантов записи некоторых признаков в ЗА5 для задач 1,2 приведен ниже.

П1 -ребро инцидентно начальному узлу сети и ориентировано от А2 и А1;

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

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

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

После режима Зп АР в задачах 1, 2 для МР с А1 Аз Т, А2 Аз2 выполняется П5: 1; Начало выполняется для ребер с П5 0.

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

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

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

Рассмотрим решение задачи 1 для сети, фиг.ба. Начальные содержимые ЗА5 - на фиг.56, веса ребер указаны на фиг.ба.

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

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

АЛ, В регистр 22(23) записывается 010 (001 соответственно, т.к. нет помеченных П2 ребер, входящих в узел 010 типа ИЛИ, то ребро 3 помечается, т.е. для него П2: 1. Разрешение начала - на МР4, 6.

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

АД. Для анализа первой выбирается МР2 (см. режим ЗпАР). Ее А1 100 и А2 001 записываются в регистры 22, 23. Узел 4 - типа И; среди входящих в него ребер есть неоконченное - 5: поэтому ни МР2, ни МРб не помечаются.

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

АЛ. Выполняется так же, как и для МРЗ; для МР4 П2: -- 1: разрешается начало МР5.

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

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

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

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

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

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

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

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

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

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

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

АД. Т.к. Аз1 001 - начальный узел сети (для ТИРЗ П4 1), то ребро от А2 к А1 не помечается и устройство переходит к проверке Аз2 011. Т.к. 001 - не начальный и нет ребер, для которых он был бы помечен как конечный, МРЗ помечается по адресу 011, т.е. ПЗ: 1. Т.к. 011 - не конечный адрес (для МРЗ Пб 0), то начинаются инцидентные 011 ребра 4, 6.

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

АП. Первой выбирается для анализа МР1. Т.к. Аз1 001 - начальный узел сети, то проверяем ориентацию ребра от А1 к А2. Т.к. нет помеченных ребер, инцидентных Аз2 010, то для МР1, ПЗ; 1, и сигнал Начало выдается на МРБ. Затем анализируется МР4, Т.к. среди ребер, инцидентных обоим конечным узлам ребр-ч 4. есть помеобрабатываются аналогично. Обе эти МР выдают запрос на МР10, В следующем АП, МР10 выбирается и сбрасывается, больше сигналов прерывания нет, пометка цветка окончена. Устройство возвращается к моделированию АД, восстановив исходные состояния всех МР, кроме 1 яруса. А именно, в режиме В.Р /П1/, П2: 0; ПЗ: 0, для всех МР, не инцидентных корню, стираются признаки П2, ПЗ. Затем следует запрос /П1 /. В результате все М-Р 1-го яруса, сохранившие ориентацию, выдают сигналы прерывания, после чего моделирование АД продолжается, как раньше. В примере фиг.9, повторное моделирование АД начинается от состояния на фиг.Эа, 9д, с той разницей, что ребра 5-9 имеют признак цветка (П4 1). Далее АД моделируется согласно фиг.9б-9в, вплоть до обработки сигнала прерывания от МР5. Для нее П4 П6 1, поэтому от вершины 4, 5 начинаются непройденные ребра 4, 6, Обработка МР7 приводит к прежним результатам. Четвертый шаг моделирования показан нафиг.Юа, 106. В следующем АП обрабатываются сигналы прерывания от МР4, МРб, Ребра, смежные ребру 6. уже пройдены, поэтому рост АД продолжается только от вершины 3. После 7-го шага моделирования, ЗА5 и граф имеют вид фиг.Шв, Юг соответственно. Ребро 1 (инцидентно белой вершине, что означает наличие АЦ 0001,...1010. Начинается шаг 8 - перекраска ребер АЦ. Это выполняется с учетом ориентации ребер и чередованя цветов. А именно, черные ребра выбираются для перекраски однозначно, из белых выбираются принадлежащие цветку либо ориентированные встречно направлению окраски; Последнее означает, что из начальной вершины перекрашенного ребра выдается запрос на смежное ребро, входящее в эту вершину. При этом выбранное для перекраски белое ребро и белые ребра, смежные с ним, исключаются из дальнейшего рассмотрения, путем стирания признаков П2, ПЗ, ПА. С учётом технических качеств устройства, после выбора ребра для перекраски посылается запрос на ребро, которое будет перекрашено следующим, а затем ребро перекрашивается и исключаются, если нужно, смежные с ним белые ребра. Процесс продолжается до перекраски ребра с П1 1, т.е. ребра из первого яруса АД. Значение П1 проверяется для каждого белого ребра, что дальше не оговаривается. Для фиг.Юе: в регистрах 22, 23, записаны адреса 0010 и 0001. Выдается запрос на смежное черное ребро - ребро 3, затем - сброс П2, ПЗ, П4 для всех белых ребер, инцидентных вершинам 1 и 2. Этот сброс выполняется для каждого выбранного белого ребра, что дальше не оговаривается. Для ребер 1, 2 этот сброс не приводит ни к каким результатам, т.к. для этих ребер П2 ПЗ П4 0. Затем ребро 5 окрашивается (П6 5 1), и МР1 сбрасывается. В следующем АП выдает сигнал прерывания МРЗ. От МРЗ выдается запрос на смежное белое ребро, входящее в крайнюю вершину (ребро 4), затем для МРЗП6: О,

0 сброс МРЗ. Обработка МР4 выполняется так же, как МР1. Запрос поступает на смежное черное ребро - 5, после сброса П2, ПЗ, П4, ребра 3, 4, 9 теряют ориентацию, а ребро 9 - еще и признак цветка. Для МР4 П6: 1;

5 сброс МР4. МР5 обрабатывается, как МРЗ. Запрос от МР5 поступает на МРб, с П4 1. На МР9 запрос от МР5 не поступает, т.к. для МР9 П2 ПЗ П4 0. МРб обрабатывается, как МР4. Дальше процесс продолжается

0 аналогично; от МР10 запрос поступает на МР11, т.к. для МР2 П2 ПЗ П4 0. Для МР11 П1 1, поэтому перекраской этого ребра оканчивается перекраска АЦ 0001,...1010. Затем стирается признак П1

5 для ребер 1 яруса. Результирующее паросо- четзние и содержимые ЗА5 приведены на фиг. 10д, Юе соответственно.

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

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

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

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

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

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

Ww) . /7,

-... г1797130

г -

hzzi

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

Ми

ПБЛЧМ

/у

Фиг. 5

, ПнлП„

--Г

-ПнлПк1

М . М

)

Ztjc I

еЈсУ{

17

H

У

Г

s

Ј

Ј

Ш/7

/ 1

и

п

SI

JI&

I) MS

71 /f« /

1 5/

l5/

I Tf I f A

$1)7/

bl

$

Я

«

4

Фм.М

1}

3fl5 r / Фи.г.Ь

Фиг.1

Г

г

-1

Р/7 Г ПГГ АТ/АЛ

u У

1

i

| W№ li

ОННЗЗШЭЗ ГЯАЭЭК

eopadivd ц -tjfvdn 7 /

4 V 7 /fflg

-I

f. .

w4M

/ ЛЛ .

П

Ч .H

a

J

f

ЗП

V

r

OCI-L6AI

№

Фиг. 7

№.№0

ле м

)

«ft

№ Л1

г/

«;

I/

/у

в 7S3k з гt

ti6Ј4-3- t

3//

/

S 7 6 $ 4 г /

дм

У

ЭЛ5

V