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

(5)5 6 06 Р 15/419 СПИ ЕНИ лоМОДЕЛИРОВАН ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) НИЕ ИЗОБР ИДЕТЕЛ ЬСТВУ(71) Институт проблем моделирования вэнергетике АН УССР и Специальное конструкторско-технологическое бюро средствмоделирования Института проблем моделирования в энергетике АН УССР(56) Авторское свидетельство СССРМ 907552, кл; С 06 Е 15/20, 1980.Авторское свидетельство СССРМ 708367; кл. 6 06 0 7/48, 1977,(54) УСТРОЙСТВО ДЛЯСЕТЕВОГО ГРАФИКА(57) Изобретение относится к электронн моделям и позволяет анализировать сети с Изобретение относится к вычислительной технике, в частности к электронным моделирующим устройствам, и может быть использовано в цифровых специализированных машинах для решения задач исследования операций и теории графов. Устройство можно использовать для моделирования сетевых графиков, сетей с различными логическими функциями в узлах, в т.ч, неориентированных сетей, и для решения задачи о наибольшем паросочетании в графах общего вида. Паросочетание - это множество независимых ребер графа, т.е. ребер, любая пара которых не имеет общих вершин; наибольшее паросочетание -паросочетание с максимаьным числом ребер, К этой задаче сводится один из вариантов задачи объединения электростанций,различными логическими зависимостями в узлах, в том числе сетевые графики и неориентированные сети, а также решать задачу о наибольшем паросачетании в графе общего вида. Цель изобретения - расширение области применения. Устройство содержит блок моделей ребер, каждая из которых содержит регистры, формирователь временных импульсов, триггеры, элементы И, элементы ИЛИ, а также генератор импульсов, блок формирования управляющих сигналов, блок формирования топологии. Последний блок совместно с первыми регистрами.блока моделей ребер обеспечивает автоматическое формирование топологии исследуемого графа (сети), а совместно со вторыми регистрами блока моделей ребер - пометку ребер различными метками и анализ этих меток. 10 ил,Известны устройства дл ния операций ройствах вер моделируются ровой выисли вые характе дискретными или двоичным взвешенными граФе - узлы логические фу Перечисле шать задачу о графе общего По техни близко к пре делирования сэлектронные моделирующиея решения задач исследоваи теории графов. В этих устшины и ребра сетей и графовпосредством элементов цифтельной техники, а их числористики представляются временными интервалами и- и кодами. Сеть - это граф со ребрами; аналоги вершин в в сетях, которые реализуют нкции И, ИЛИ.нные устройства не могут ренаибольшем паросочетании в вида,ческой сущности наиболее длагаемому устройство для моетевых графиков, принятое всодержит инвертор, первы - четвертый элементы ИЛИ, первый - третий элементы И, причем выход первого элемента И подключен к второму входу формирователя временных интервалов каждой модели ребра блока, первые входы первого и третьего элементов И подключены соответственно к выходу и входу инвертора, йервые входы первого и второго элементов ИЛИ подключены соответственно к переому и второму задающим выходам блока формирования управляющих сигналов, выход второго элемента ИЛИ подключен к первому осведомительному входу блока формирования управляющих сигналов, входы третьего и четвертого элементов ИЛИ и второго элемента И подключены соответственно к первому выходу третьего триггера, к выходам первого элемента И и элемента ИЛИ каждой модели ребра блока. вторые входы пераого и третьего элементов И подключены к соответствующим выходам генератора импульсов, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения, в каждую модель ребра блока дополнительно введены пятый и шестой элементы И, первые входы которых подключены соответственно к третьим синхронизирующим и задающему выходам блока формирования управляющих сигналов, третий вход первого элемента И и вторые входы. второго, третьего, пятого и шестого элементов И подключены через инвертор к выходу элемента ИЛИ, выходы второго и пятого элементов И подключены к соответствующим входам четвертого триггера, третий вход третьего элемента И подключен к второму выходу третьего триггера, третий вход которого подключен к выходу четвертого элемента И, второй вход которого подключен к второму входу формирователя временных интервалов, первый, второй, третий. входы задатчика адреса на.- чального узла подключены соответственно к выходу шестого элемента И, к входу задатчика адреса конечного узла и к выходу35 бра, первый и второй входы четвертого элемента И подключены соответственно квыходу четвертого элемента ИЛИ и к выходу первого элемента ИЛИ, выход третьего элемента ИЛИ подключен к второму осведоми 40тельному входу блока формирования управляющих сигналов, первый и второй синхронизирующие входы которого подключены к соответствующим выходам генератора импульсов,10152030 третьего элемента И блока формирования топологии, к выходу задания признака блока формирования управляющих сигналов и к второму входу первого узла сравнения, второй вход элемента ИЛИ подключен к выходу первого триггера, второй, третий входыкоторого подключены соответственно к четвертому синхронизирующему выходу блокаформирования управляющих сигналов, к установочному выходу блока формированияуправляющих сигналов и к второму входувторого триггера, третий вход которого подключен к пятому:синхронизирующему выходу блока формирования управляющихсигналов, в блок формирования топологиидополнительно введены четвертый, пятый ишестой элементы И, пятый элемент ИЛИ,первый и второй регистры, первые входы которых подключены к выходу третьего элемента И, вторые входь 1 - к выходу четвертого элемента И и к входу пятого элемента ИЛИ, третьи входы - соответственно к первому входу первого элемента ИЛИ, к второ-. му входу первого элемента ИЛИ и кчетвертому задающему выходу блока формирования управляющих сигналов, а выходы - к первым входам пятого и шестого элементов И, вторые входы которых подключены соответственно к пятому и шесто.- му задающим выходам блока формированияуправляющих сигналов, а выходы - к второму и третьему входам пятого элемента ИЛИ,выход которого подключен к второму входу второго узла сравнения каждой модели рен. а ц Щ 4 б МРЗ РР 1/ Фаг. 5 1ЯЯУиД.0 иГ ЮГ гРГ иРЗ Р 1 Ю 5 Ю ФВ пел рр МЦ МРР/1 Р ЮРЯ .Я 3 ИИ . ИРВ а/ 4 Составитель О,ГоловановаТехред М.Моргентал дактор О.Стенина Корректор О,Кравц каз 654 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открыти 113035, Москва, Ж, Раушская наб., 4/5 при ГКНТ СС Производственно-издательский комбинат "Патент" город. ул.Гагарина 101 87854 98/ ЯИ Ю 3 мР 3 ИР 4 рД 5 мРС ИР 7 МУ /7 Р У /РВ / ЗУФУФ 38 Г МР 4 МР 8 /ЮР 3 ю 4 /О ЮфЮ МРГрого подключен к выходу третьего элемента И, первые входы второго, третьего и четвертого элементов И подключены соответственно к первому, второму синхронизирующим выходам блока формирова 30 ния управляющих сигналов и к выходу четвертого триггера, блок формирования топологии содержит инвертор, первый - четвертый элементы ИЛИ, первый - третий элементы И, причем выход первого элемен та И подключен ко второму входу формирователя временных интервалов каждой модели ребра блока, первые входы первого ,и третьего элементов И подключены соответственно к выходу и входу инвертора, первые входы первого и второго элементов 40 ИЛИ подключены соответственно к первому и второму задающим выходам блока формирования управляющих сигналов, выход второго элемента ИЛИ подключен к первому осведомительному входу блока формирования управляющих сигналов, входы третьего и четвертого элементов ИЛИ и второго элемента И подключены соответственно к первому выходу третьего триггера, к выходам первого элемента И и элемента ИЛИ каждой модели ребра блока, вторые входы первого и третьего элементов И подключены к соответствующим выходам генератора импульсов,Устройство моделирует сетевые графики, ориентированные сети с различными ло 50 55 гическими функциями в узлах и выполняетассоциативный поиск по совокупности признаков. качестве прототипа, Это устройство содержит генератор импульсов, блок формирования управляющих сигналов, блок формирования топологии, блок моделей ребер по числу работ исследуемого сетевого 5 графика, причем каждая модель ребра содержит формировател ь времен н ых интервалов, первый - четвертый триггеры, первый - четвертый элементы И, элемент ИЛИ, инвертор, первый и второй узлы срав- "0 нения, задатчик адреса начального узла и задатчик адреса конечного узла, выходы которых подключены соответственно к первым входам первого и второго узлов сравнения, выходы которых подключены соответственно к первым входам первого и второго триггера, выходы второго задатчика и второго триггера подключены соответственно к первым входам первого элемента И и элемента ИЛИ, второй вход первого эле мента И подключен к первому выходу третьего триггера, первый и второй входы которого подключены соответственно к выходам второго элемента И и формирователя временных интервалов, первый вход котоНедостаток прототипа - невозможность решения на нем задачи.о наибольшем паросочетании в графе общего вида, Этот недостаток обусловлен тем, что устройство не позволяет моделировать неориентированные .графы с пометкой ребер в процессе моделирования.Цель изобретения - расширение области применения за счет решения задачи о наибольшем паросочетании в графе общего вида,Цель достигается тем, что в каждую модель ребра блока дополнительно введены пятый и шестой элементы И, первые входы которых подключены соответственно к третьим синхронизирующему и задающему выходам блока формирования управляющих сигналов, третий вход первого элемента И и вторые входы второго, третьего, пятого и шестого элементов И подключены через инвертор к выходу элемента ИЛИ, вы,- ходы второго и пятого элементов И подключены к соответствующим входам четвертого триггера, третий вход третьего элемента И подключен к второму выходу третьего триггера, третий вход которого подключен к выходу четвертого элемента И, второй вход которого подключен к второму входу формирователя временных интервалов, первый, второй, третий входы задатчика адреса начального узла подключены соответственно к выходу шестого элемента И, к входу задатчика адреса конечного узла и к выходутретьего элемента И блока формирования топологии, к выходу задания признака блока формирования управляющих сигналов и к второму входу первого узла сравнения, второй вход элемента ИЛИ подключен к выходу первого триггера, второй, третий входы которого подключены соответственно к четвертому синхронизирующему выходу блока формирования управляющих сигналов, к установочному выходу блока формирования управляющих сигналов и ко второму входу второго триггера, третий вход которого подключен к пятому синхронизирующему выходу блока формирования управляющих сигналов, в блок формирования топологии дополнительно введены четвертый, пятый и шестой элементы И, пятый элемент ИЛИ, первый и второй регистры, первые входы которых подключены к выходу третьего элемента И, вторые входы - к выходу четвертого элемента И и к входу пятого элемента ИЛИ, третьи входы - соответственно к первому входу первого элемента ИЛИ, к второму входу первого элемента ИЛИ и к четвертому задающему выходу блока формирования управляющих сигналов, а выходы - к первым входам пятого и шестого15 20 25 30 40 Чередование адресных и информационных периодов зависит от выходйого сигнала элемента ИЛИ 33, Когда любой ФВИ 7 окан чивает работу, через триггер 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, инвертор 30, элементы ИЛИ 31-35, ЗА 6 - кольцевой сдвиговый регистр; ЗА 5, регистры 22, 23 -сдвиговые регистры с входами записи, управления, сдвига; ФВИ 7 - дискретная линия задержки, узлы 12, 13 сравнения - . 5например, однородные двоичные сумматоры.МР и БФТ предназначены для моделирования графа при автоматическом формировании его топологии, В .отличие отпрототипа ЗА 6 предназначен для записиобоих адресов (номеров) вершин (А 1 и А 2),инцидентных данному ребру. Узел 13 сравнения и триггер 10 предназначены для поразрядного сравнения А 1 и А 2 с задающими адресами (Аз 1 и/или Аз 2). Регистры 22, 23, элементы И 24, 25, 28, ИЛИ 31, 32 предназначены для записи, хранения и поочередной выдачи Аз 1, А 2; формирование Аз 1, Аз 2 рассмотрено ниже, При 2 п-разрядных ЗА 5, ЗА 6 регистры 22, 23 - п-разрядные.Элемент И 19, схемы 12 сравнения, ЗА 5, триггер 9 предназначены для записи, хранения и сравнения с эталоном меток ребра,Элементы И 29, ИЛИ всех МР предназначены для проверки наличия ребер с данными метками и/или инцидентных задающему узлу, Дальше называем. содержимое К-го разряда ЗА 5 К-м признаком и обозначать Пк либо Пк (Пк=1 при Пк=О),БФУС предназначен для выдачи синхронизации 1 с - 5 с, сигнала с установки триггеров 9, 10 в единицу, сигнала Пр признака, задающих сигналов 1 з - 6 э, на основе поступающих на входы БФУС сигналов 1 свх, 2 свх, выдаваемых ГИ. В соответствии с логикой работы устройства импульсы серии 1 свх (2 свх) будем называть информационными (адресными соответственно) импульсами,Значение сигнала Пр равно значению признака, который либо записывается в ЗА 5 МР, либо сравнивается с записанным ранее, посредством узла 12 сравнения, Запись и сравнение разнесены во времени за счет несовпадения сигналов Зз и 4 с. (Триггеры 910 переключаются при подаче на их синхровходы сигналов 4 с, 5 с),Сигналы 1 с - Зс, Зз через элементы И16 - 19 определяют режимы работы МР (запрас, начало, сброс, запись признака), а сигналы 1 з, 4 з - 6 з - определяют режимы работы регистров 22, 23 (запись, выдача информации); сигнал Зз - вспомогательный, назначение раскрыто ниже, Техническая реализация БФУС может быть различной, Рассмотрим организацию работы устройства. Как и прототип, устройство работает посредством чередования двух периодов - информационного, когда на МР через элемент И 26 поступают информационные импульсы, и адресного, когда через элемент И 27 на МР поступают адресные импульсы,сдвигающие содержимые регистров 22, 23,ЗА 5, ЗА 6.Поскольку решение различных задач отличается организацией адресных периодов, в дальнейшем основание внимание уделено именно им. Считаем, что один сигнал прерывания обрабатывается в течение одного адресного цикла.Рассмотрим режимы работы устройства, общие для всех задач:- Зп АР - запись адреса ребра, т,е, запись адресов инцидентных вершин ребра в регистры 22, 23;- ВР (А 1, В 2) - выбор одного ребра, адрес которого записан в регистрах 22, 23, т,е, А 1=Аз 1, А 2=Аз 2;ВРАз 1 (ПмА Пн) - выбор множества ребер (м.б, и пустого) из числа инцидентных вершине с адресом Аз 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 остаются вединице.В нашем примере единицы с выходовЗА 6 в МР 1 2 поступают на выходы элементов И 14 тех же МР; через элементы ИЛИ 35И 28 они поступают на вход регистра 22 и через элемент ИЛИ 31 - на входы узлов 13 сравнения всех МР, После первого импульса 5 с сбрасывается триггер 10 МРЗ, в последнем разряде ЗА 6 которой записан нуль, 5 10 15 20 25 30 35 40 50 55 После первого адресного импульса, единица с выхода И 28 записывается в первый разряд регистра 22, Нуль триггера 10 МРЗ закрывает элемент И 14 М РЗ, поэтому дальше содержимое ЗА 6 на элемент ИЛИ 34 не поступает. Следующие два такта сдвига протекают точно так же. После третьего адресного импульса в регистре 22 записан Аз 1=101, БФЧС сбрасывает сигнал 1 з и выдает сигнал 4 з, обеспечивая запись Аз 2 в регистр 23. Четвертый адресный импульс не меняет состояния триггеров 10 МР 1, 2; после пятого импульса триггер 10 М Р 1 сбрасывается сигналом от узла 13 сравнения. После шести адресных импульсов в регистрах 22, 23 записаны адреса Аз=101 и Аз 2=011, В общем, режим ЗпА обеспечивает запись в регистры 22, 23 адресов той МР, которая содержит в правых разрядах ЗА 6 больше единиц,ьВР (А 1, А 2) отличается от ЗпАР только. . тем, что адреса Аз 1, Аз 2 выдаются на узлы .13 сравнения всех МР не с выхода элемента И 28, а с выхода регистра 22 или 23, через элементы И 24, И 25. В этом режиме сигналы 1 з, 4 з равны нулю, поэтому элемент И 28 закрыт, а в регистрах 22, 23 информация ци р кули рует.Режим начинается установкой триггеров 9, 10 и выдачей сигнала 5 з; на выход элемента ИЛИ 31 поступает содержимое регистра 22, т.е, Аз 1. Сравнение Аз 1 с А 1 всех МР вь 1 полняется, как описано выше, Затем сигнал 5 а снимается, выдается сигнал 6 з и на выход элемента ИЛИ 31 поступает Аз 2 из регистра 23, После 2 п тактов сравнения остается на единице триггер 10 той МР, для которой А 1=Аз 1, А 2=Аз 2.ВРАз 1 отличается от ВР (А 1, А 2) только тем, что задающим является единственный адрес - Аз 1, который сравнивается с А 1 и А 2 всех МР. При этом триггеры 9, 10 устанавливаются дважды - в начале режима и после и тактов сдвига, а сигнал 5 з выдается в течение 2 п тактов (естественно, ВР Аз 2 выполняется точно тэк же). Поэтому режим ВРАз 1 можно рассматривать состоящим из двух последовательных режимов: ВРАз 1(А 1) и ВРАЗ(А 2), т.е. выбор тех МР, для которых А 1=Аз 1 и тех МР, для которых А 2=Аз 1. ВРАз 1 /ПнЬПм) отличается от В РАз 1 тем; что в н-м и м-м тактах сдвига выполняется сравнение содержимых ЗА 5 с эталонным признаком, равным единице. Последний поступает в этих тактах на общий вход всех узлов 12 сравнения, Сравнение выполняется.выдачей в тех же тактах сигналов 4 с, по которым переключаются триггеры 9, В этом случае режимь 1 ВРАз 1(А 1)/ПнЛ Пм) и ВРАз 1(А 2) (ПнЛ Пм), выполняются последо= ПЗ=О.ИП. После одного информационного импульса кончает работу МР 5. АП, Т.к, Аз 1 = 010 помечен как конечный,анализируется Аз 2 = 100. Ребро 5 кончилосьпервым в этом узле, поэтому оно помечается; ПЗ: = 1, Т.к. для ребра 5 П 6 = 1, работа устройства прекращается. Окончательные содержимые всех ЗА 5 приведены на фиг,6 г, Дерево кратчайших путей показано на фиг.бд; кратчайший путь между узлами 1 и 4 - это ребра 1, 5, вес этого пути, равный суммарному числу информационных импульсов, поступивших на устройство - 4.Задача 3. Решается на основе модифицированного алгоритма Эдмондса. Модификация обусловлена техническими особенностями устройства и не затрагивает математических аспектов алгоритма, Далее называем вершины и ребра, принадлежащие (не принадлежащие) паросочетанию, черными (белыми соответственно). Вершина белая, если ей не инцидентны черные ребра. Суть алгоритма,Эдмондса состоит в последовательном поиске аугментальных цепей (далее обозначаемых АЦ), т.е, цепей, ребра которых чередуются по цвету, а обе крайние вершины - белые. Перекраска ребер этой АЦ позволяет получить новое паросочетание; содержащее на одно ребро больше предыдущего, Для поиска таких цепей строятся альтернирующие деревья (АД), с корнем в непросмотренной вершине (белой), все четные (нечетные) ярусы которого черные (белые соответственно). Если АД достроено до конца. а АЦ в нем нет(все висячие вершины черные), корень дерева помечается как просмотренная вершина и строится новое АД, если это возможно. Процесс продолжается, пока есть непросмотренные белые вершины. Последнее из найденных паросочетаний - наибольшее; Если при построении АД выявляется "цветок", т.е. цикл нечетной длины, то он "стягивается", что позволяет отыскать любую АЦ, проходящую через "цветок". После "стягивания" цветка построение данного АД возобновляется, начиная с корня. 50 Заявляемое устройство работает по следующему алгоритму. 1. Построить начальное паросочетание такое, чтобы в графе не было ребер, инци дентных двум белым вершинам,2. Выбрать из .непросмотренных белыхвершин вершину ХА, если таких вершин нет,то 9,3. Построить первый ярус АД с корнемв ХА. 4. Построить черный ярус АД; если АДдостроено до конца, то 6; если при построении этого яруса получился цветок, то 7, иначе 5,5. Построить нечетный ярус АД: еслинайдена белая вершина ХВ, то 8, если припостроении этого яруса получился цветок,то 7, иначе 4,6. Пометить ХА как просмотренную, перейтик 2.7. Пометить все ребра цветка, перейти к3,8. Найти АЦ ХВ.,ХА; изменить окраскуее ребер.9. Конец: паросочетание, построенноепоследним, наибольшее,Один из вариантов записи признаков вЗА 5 может быть следующим.П 1 - ребро инцидентно корню моделируемого АД;П 2(ПЗ) - ребро ориентировано от А 2 к А 1(от А 1 к А 2 соответственно);П 4 - ребро принадлежит цветку;П 5 - ребро инцидентно просмотреннойбелой вершине;П 6 - ребро черное,Рассмотрим решение задачи на примере графа (фиг,7 а). Содержимые ЗА 6 приведены на фиг,7 б, во всех ЗА 5 нули. Первыйшаг алгоритма иллюстрируется фиг.7 вж,Режим начинается с установки триггеров 8 всех МР, за чем следуют адресныециклы. Каждый из них выполняется так, После ЗпАР выбранное ребро окрашиваетсячерным (П 6; = 1), после чего сбрасываютсясигналы прерывания с выбранной МР исмежных с ней. Процесс продолжается, пока есть несброшенные сигналь 1 прерывания, В нашем примере, в первом адресномцикле выбирается МР 10. Для МР 10 П 6; = 1,после чего сбрасываются МР, инцидентныеАз 1, т,е. 8, 9, 10 и МР, инцидентные Аз 2, т.е.2, 11, (Как отмечено ранее, повторный сбросне влияет на работу МР и всего устройства,поэтому здесь и далее повторно сброшенные МР не перечисляем). Окраска МР 10 показана на фиг.7 в, Сброшенные ребраотмечены крестиком и дальше нэ фиг,7 неизображаются, Затем в следующем адресном цикле выбирается МРЗ (фиг.7 г). Она окрашивается и сигналы прерысания от МР 1,3, 4 сбрасываются, Затем окрашиваетсяМР 5 и сбрасываются МР 5, МР 6 (фиг,7 д). Осталась несброшенной одна МР - МР 7, которая окрашивается и сбрасывается вследующем адресном цикле. Ненулевые содержимые ЗА 5 показаны на фиг,7 е, полученные паросочетэния - на фиг,7 ж.Начинается второй шаг алгоритма - поискнепросмотренной белой вершины. Вначалевыполняется запрос белых ребер, инцидентных непросмотренным вершинам - запрос /П 6/1 П 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 в,г, ребра Ча. Чь). Если замыкающее ребро не помечено (П 4 = 0), построение АД прерывается и начинается пометка цветка, Во всех других случаях выдается запрос на следующий ярус, (фиг,8 д; запрос показан стрелками в начале ребра). Ребро ориентируется, как и в задаче о кратчайшем пути на неориентированном графе, в направлении от вершины, помеченной как конечная к вершине, не имеющей такой пометки. В случае, если обе крайние вершины ребра имеют такую пометку, ребро ориентируется в двух направлениях, Кроме этого, каждое черное ребро проверяется на принадлежность ранее построенному цветку (т.е. по признаку П 4). Если для этого ребра П 4 = 1, то запрос выдается на все смежные непройденные ребра от обеих его крайних вершин(фиг,8 е), за счет чего цветок "стягивается", Если смоделированный черный ярус - последний в АД, то корень АД помечается. как просмотренная вершина, а признак корня - П 1 - стирается (т,е, вы полн я ется В Р/П 1/, П 1: =О, П 5:-1).Каждое белое ребро, кроме ребер первого яруса, проверяется на инцидентность белой вершине ХВ; если это так, то есть АЦ 10 ХВХА. Рассмотрим построение АД на том же примере (фиг,7 ж). На фиг,9 а - 9 г показано построение соответственно первого, второго, третьего и четвертого ярусов АД. Это построение выполняется без особенностей, его ход определяется чередованием черных и белых ярусов дерева, т.е. нечетных и четных шагов моделирования АД, ЗА 5 отработавших МР показаны на фиг,9 д - 9 з. Пройденные ребра обозначены стрелками в 15 стрелками в начале, Иначе моделируетсв МР 6 (пятый ярус АД). После окончания она ориентируется в обоих направлениях, т.к. вершины 5 и 6 помечены как конечные, Т,к,для МР 6 П 4 = О, на пятом ярусе моделирование АД прерывается и начинается пометка цветка (фиг,9 и, шаг 7 алгоритма). Этот шаг выполняется посредством режимов запрос, пометка, проверка, сброс, Замыкающее ре 25 30 бро (6, фиг;9 и) помечается (П 4; = 1), затем признак П 4 = 1 распрстраняется от крайних вершин этого ребра по пройденным (т,е. ориентированным) ребрам встречно их ориентации (штриховая линия на фиг,9 и). Это 35 40 означает, что запрос посылается из начальной вершины помеченного ребра на смежное ребро, входящее в эту. вершину. Пометка ребер цветка продолжается до достижения начальной вершины цветка (вершина 7 фиг.9 и). Признаком достижения начальной вершины является единственный сигнал прерывания (от МР 10 на фиг.9 и), в отличие от большего числа сигналов прерывания на каждом из предыдущих шигов по 45 50 55 метки цветка, Обратимся к нашему примеру (фиг.9 и). Исходное состояние: Аз 1 = 0110, Аз 2 = 0101, для МР 6 П 2 = ПЗ = 1,НАП. Для МР 6 П 4: = 1, из крайних вершин 5, 6 посылаются запросы на входящие в эти вершины ребра с П 4. = О. Сброс МР 6.АП, МР 5, МР 7 выдают сигналы прерывания. Первой выбирается МР 5, сброс МР 5, Сигнал 1 ос равен единице, что означает наличие сигнала прерывания, т,е, начальная вершина цветка не достигнута. В Р(Аз 1, Аз 2), П 4. = 1, обеспечивает пометку МР 5, после чего. выдается запрос на МР, входящую в вершину 4 - МР 9, Затем обрабатывается сигнал преырвания от МР 7: П 4 = 1, запрос на МРЗ, сброс, МР 8, МР 9 в следующем АП 20 конце, ребра, на которые послан запрос -10 1520 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 всех МР. На выходе узла 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 с начинают поступать на МР после трех адресных импульсов; этим обеспечивается сравнение А 2 с Аз 1. После 2 п тактов сдвига остаются в единице триггеры 9 МР 2, 35 МРЗ, МР 5, и триггер 10 МРЗ, т.е. выбрана МРЗ, По фиг.3 видно, что ребра 2, 3 удовлетворяют заданным условиям. Из описанного ясно выполнение ВРАз 1 и ВР (ПнЛПм), А именно, для первого (второго) из них сигнал 4 с (5 с соответственно) не выдается.Ассоциативный поиск по совокупности признаков, выполняемый прототипом - это выбор ребер по этой совокупности признаков, Например, поиску по совокупности признаков ПнЛПмЛПт, соответствует режим ВР (ПнЛПмЛПт).На основе режима выбора строятся другие режимы, в частности, проверка признака (совокупности признаков) для одного 50 ребра, (фиг.4 а, 46 соответственно), проверка признака для всех ребер, инцидентных Аз 1 (фиг,4 в), и проверка для тех же ребер разных признаков, в зависимости от ориенпоступают на выбранные МР через элементы И 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) помечается как приадлежащее дереву, то за этим следуетНачало" ребер, выходящих из его конечноо узла; каждый адресный цикл (т,е, обра 1797130 125 10 15 20 25 30 35 40 45 50 55 ботка сигнала прерывания от МР (А 1, А 2), завершается сбросом этой МР, Запись и интерпретация признаков в ЗА 5 может быть произвольной.Один из возможных вариантов записи некоторых признаков в ЗА 5 для задач 1, 2 приведен ниже,П 1 - ребро инцидентно начальному узлу сети и ориентировано от А 2 и А 1;П 2 - ребро принадлежит дереву оптимальных путей и ориентировано от А 2 и А 1;П 5 - ребро окончено;Пб - ребро инцидентно конечному узлу сети.После режима Зп АР в задачах 1, 2 для МР с А 1 = Аз 1, А 2 = Аз 2 выполняется П 5: = 1; "Начало" выполняется для ребер с П 5 = О,Другие признаки описаны при рассмотрении конкретных задач.Задача 1 (решается прототипом).Все ребра ориентированы от А 2 к А 1. Кроме общих признаков для задач 1,2 используется П 4 - ребро входит в узел И, Ребро получаем П 2 = 1, если оно окончилось последним из ребер, входящих в узел И (т.е. нет ребер, входящихв тот же узел, для которых П 44 П 5 = 1); либо если оно окончилосьпервь 1 м из ребер, входящих в у%л ИЛИ (т,е.нет ребер, входящих в тот же узел, для которых П 2 = 1),Рассмотрим решение задачи 1 для сети,фиг,5 а. Начальные содержимые ЗА 5 - нафиг.5 б, веса ребер указаны на фиг,5 а.НАП. ВРАз 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, б.ИП, После одного информационного импульса выдают сигнал прерывания МР 2, МРб.АП. Для анализа первой выбирается МР 2 (см. режим ЗпАР). Ее А 1 = 100 и А 2 = 001 записываются в регистры 22, 23. Узел 4 - типа И; среди входящих в него ребер есть неоконченное - 5, поэтому ни МР 2, ни МР 6 не помечаются. ИП, После одного информационного импульса завершает работу МП 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, В исходном состоянии ребра определяются инцидентными узлами, адреса которых записаны Ф ЗАб в произвольном порядке. Ребра ориентируются в процессе решения; ребер, входящих в начальный узел сети, нет. Кроме признаков, общих для задач 1, 2, используются следующие;ПЗ - ребро принадлежит дереву и ориентировано от А 1 и А 2;П 4 - ребро инцидентно начальному узлу сети и ориентировано от А 1 к А 2, Ребро (А 1, А 2) получает, например, признак П 2 = 1, если А 1 не начальный узел сети, и ребро(А 1, А 2) окончилось первым в А 1, Если ребро не помечается по А 1 (признаком П 2), то проверяется возможность его пометки по А 2.Рассмотрим пример фиг,б; ЗАб показаны на фиг.бб; в ЗА 5 записаны нули.НАП, ВРАэ 1 (А 2); П 1; = 1, ВРАэ 1 (А 1); П 4; = 1; ВРАз 2; Пб; =1, Начало; /П 1/; /П 4/. ЗА 5 приобрели вид фиг,бв; начаты МР 1, 2, 3.ИП, После двух информационных импульсов окончила работу МРЗ;АП, Т.к. Аз 1 = 001 - начальный узел сети (для МРЗ П 4 = 1), то ребро от А 2 к А 1 не помечается и устройство переходит к проверке Аз 2 = 011, Т,к, 001 - не начальный и нет ребер, для которых он был бы помечен как конечный, МРЗ помечается по адресу 011, т.е, ПЗ; = 1. Т,к, 011 - не конечный адрес (для МРЗ Пб = О), то начинаются инцидентные 011 ребра 4, б,ИП. После одного информационного импульса кончают работу МР 1, МР 4.АП, Первой выбирается для анализа МР 1. Т,к. Аэ 1 = 001 - начальный узел сети, то проверяем ориентацию ребра от А 1 к А 2. Т.к. нет помеченных ребер, инцидентных Аз 2 = 010. то для МР 1, ПЗ: = 1, и сигнал "Начало" выдается на МР 5, Затем анализируется МР 4, Т.к, среди ребер, инцидентных обоим конечным узлам ребра 4, есть поме17 1797130 10 20 ЗО 45 50 обрабатываются аналогично. Обе эти МР выдают запрос на МР 10, В следующем АП, МР 10 выбирается и сбрасывается, больше сигналов прерывания нет, пометка цветкаокончена. Устройство возвращается к моде лированию АД, восстановив исходные состояния всех МР, кроме 1. яруса, А именно, в режиме ВР /П 1/, П 2: = 0; ПЗ: = О, для всех МР, не инцйдентных корню, стираются.признаки П 2, ПЗ. Затем следует запрос /П 1/. В результате все МР 1-го яруса,.сохранившие ориентацию, выдают сигналы прерывания, после чего моделирование АД продолжается, как раньше, В примере фиг,9, повторное моделирование АД начинается от состояния 15 на фиг,9 а, 9 д, с той разницей, что ребра 5-9 имеют йризнак цветка (П 4 = 1). Далее АД моделируется согласно фиг.9 бв, вплоть до обработки сигнала прерывания от МР 5. Для нее П 4 = П 6 = 1, поэтому от вершины 4, 5 начинаются непройденные ребра 4; 6, Обработка МР 7 приводит к прежним результатам, Четвертый шаг моделирования показан.на фиг,10 а, 10 б. В следующем АП обрабатываются сигналы прерывания от МР 4, МР 6, 25Ребра, смежные ребру 6, уже пройдены, поэтому "рост" АД продолжается только от вершины 3. После 7-го шага. моделирования, ЗА 5 и граф имеют вид фиг.10 в, 10 г соответственно. Ребро 1 инцидентно белой вершине, что означает наличие АЦ 0001,1010. Начинается. шаг 8, - перекраска ребер АЦ, Зто выполняется с учетом ориентации ребер и чередованя цветов. А именно, черные ребра выбираются для перекраски одно значно, из белых. выбираются принадлежащие цветку либо ориентированные встречно направлению окраски. Последнее означает, что иэ начальной вершины перекрашенного ребра выдается запрос "на 40 смежное ребро; входящее в эту вершину При этом выбранное для перекраски белое ребро и белые ребра, смежные с ним, исключаются из дальнейшего рассмотрения, путем стирания признаков П 2, ПЗ, П 4, С учетом технических качеств устройства, после выбора ребра для перекраски посылается запрос на ребро, которое будет перекрашено следующим; а затем ребро перекрашивается и исключаются, если нужно, смежные с ним белые ребра. Процесс продолжается до перекраски ребра с П = 1, т.е, ребра из первого яруса АД. Значение П 1 проверяется для каждого белого ребра, что дальше не оговаривается. Для фиг.10 е: в регистрах 22, 23, записаны адреса 0010 и 0001, Выдается запрос на смежное черное ребро - ребро 3. затем - сброс П 2, ПЗ, П 4 для всех белых ребер. инцидентных вершинам 1 и 2. Этот сброс выполняется для каж 8дого выбранного белого ребра, что дальше не оговаривается. Для ребер 1, 2 этот сброс не приводит ни к каким результатам, т.к. для этих ребер П 2 - ПЗ = П 4 = О. Затем ребро окрашивается П 6 5 =1), и МР 1 сбрасывается, В следующем АП выдает сигнал прерывания МРЗ. От МРЗ выдается запрос на смежное белое ребро, входящее в крайнюю вершину (ребро 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 яруса, Результирующее паросочетание и содержимые ЗА 5 приведены на фиг.10 д, 10 е соответственно,Формула изобретения Устройство для моделирования сетевого графика, содержащее генератор импульсоа, блок формирования управляющих сигналов, блок формирования топологии, блок моделей ребер по числу работ исследуемого сетевого графика, причем каждая модель ребра содержит формирователь временных интервалов, первый - четвертый триггеры, первый - четвертый элементы И, элемент ИЛИ, инвертор, первый и второй узлы сравнения, эадатчик адреса начального узла и задатчик адреса конечного узла, выходы которых подключены соответственно к первым входам первого и второго узлов сравнения, выходы которых подключены со-ответственно к первым входам первого и второго триггеров, выходы второго задатчика и второго триггера подключены соответственно к первым входам первого элемента И и элемента ИЛИ, второй вход первого элемента И подключен к первому выходу третьего триггера, первый и второй входы которого подключены соответственно к выходам второго элемента И и формирователя временных интервалов, первый выход которого подключен к выходу третьего элемента И, первые входы второго, третьего и четвертого элементов И подключены соответственно к первому, второму синхрпнизирующим выходам блока формирования управляющих сигналов и квыходу четвертого триггера, блок формирования топологии