Устройство для решения задач на графах

(51)5 0 06 Р 15/419 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВ ЛЬСТВУ(56) Авторское свидетельство СССРМ 1587534, кл. 0 06 Е 15/20, 1988,Авторское свидетельство СССРМ 1683035, кл. О 06 Г 15/20, 1988,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧНА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано длярешения задач, связанных с определениемкратчайших путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения последовательности вершин маршрутов в графе. Устройство содержит блок 1 синхронизации, многоканальный блок регистрации, (блок определения последовательности вершин маршрута), первый блок 3 регистрации, блок 4 определения концевых вершин дуг, второй блок 5 регистрации, вход пуска, вход 7 задания множества дуг маршрута и вход 8 задания начальной вершины маршрута. При поступлении на вход 6 пуска импульса уровня логической единицы блок 1 синхронизации формирует на своих выходах последовательность сигналов, под управлением которой в блоке 2 регистрации накапливается искомая последовательность вершин, 2 ил.Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением кратчайшего пути на графе,Известно устройство для операций над графами, содержащее, в частности, блок синхронизации, блок регистрации, блок определения концевых вершин дуг, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен в входу признака записи блока регистрации, выход состава множества концевых вершин дуг блока определения концевых вершин дуг подключен к информационному входу блока регистрации. Недостатком этого устройства является отсутствие у него возможности определения последовательности вершин маршрутов в графе.Цель изобретения - расширение функциональных возможностей устройства за счет определения последовательности вершин маршрутов в графе.Указанная цель достигается тем, что в устройство введены блок определения последовательности вершин маршрута и второй блок регистрации, причем информационный выход первого блока регистрации подключен к информационному входу второго блока регистрации и к информационному входу блока определения последовательности вершин маршрута, вход выбора К-го канала которого(К = 1, 2 В, где В - количество вершин в графе) подключен к К-му выходу группы блока синхронизации, второй выход которого подключен к входу признака записи блока определения последовательности вершин маршрута и к входу признака записи второго блока регистрации, К-й разряд(К = 1, ,В) информационного выхода которого подключен к входу опроса К-й начальной вершины дуги блока определения концевых вершин дуг, вход задания топологии графа которого является входом задания множества дуг маршрута устройства, вход задания начальной вершины маршрута которого подключен к установочному входу второго блока регистрации,Техническая эффективность использования изобретения состоит в обеспечении возможности автоматического и редставления пути на графе в виде упорядоченной последовательности номеров вершин графа. Этим обеспечивается повышение оперативности и достоверности принятия управленческих решений по задачам моделирования с помощью графов,На фиг.1 представлена обобщенная структурная схема устройства; на фиг,2 -пример функциональной схемы конкретного выполнения устройства,Структурная схема содержит блок 1 синхронизации, многоканальный блок 2 регист 5 рации (блок определенияпоследовательности вершин маршрута),блок 3 регистрации, блок 4 определенияконцевых вершин дуг, блок 5 регистрации,вход 6 пуска, вход 7 задания множества дуг10. маршрута и вход 8 задания начальной вершины маршрута.Функциональная схема содержит единичный элемент 9, триггер 10, генераторимпульсов 11, элемент И 12, распределите 15 ли 13 и 14, группу элементов И 151 - 15 с(С = В - 1; В - количество вершин в графе),группу регистров 161 - 16 с, единичный элемент 17, наборное поле 18, элемент задержки 19, группу элементов И 201 - 20 г,20 элемент задержки 21, группу элементовИЛИ 221 - 22 г, элемент ИЛИ 23, регистр 24,дешифратор 25, единичный элемент 26, наборные поля 27 и 28, регистр 29, группушифраторов 30 - 30 в, группу элементов25 ИЛИ 31 - 31 г, элемент задержки 32, регистр33.Блок 1 синхронизации предназначендля синхронизации работы блоков, имеющих вход признака записи.30 Многоканальный блок 2 регистрациипредназначен для поочередного приема всвои секции и хранения кодов вершин маршрута, Блок 3 регистрации предназначендля приема, хранения и выдачи кода очеред 35 ной вершины маршрута в первом такте очередного цикла работы устройства.Блок 3 определения концевых вершиндуг предназначен для формирования кодаконцевой вершины любой дуги графа, а так 40 же для формирования и хранения кода множества дуг маршрута и кода множества дуги вершин маршрута,Блок 5 регистрации предназначен дляприема, хранения и выдачи кода очередной45 вершины маршрута во втором такте очередного цикла работы устройства, а также дляформирования, хранения и выдачи кода начальной вершины маршрута.Вход 6 пуска предназначен для приема50 сигнала пуска устройства.Вход 7 задания начальной вершинымаршрута предназначен для приема сигнала признака записи кода начальной вершины маршрута устройства.55 Вход 8 задания множества дуг маршрута предназначен для приема сигнала признака записи кода множества дуг и вершинмаршрута устройства.Единичный элемент 9 предназначен дляобеспечения формирования сигнала и на 17771565 10 хождении устройства в режиме Формирования кодов.Триггер 10 предназначен для формирования, хранения и выдачи сигнала о нахождении устройства в режиме формированиякодов.Генератор импульсов 11 предназначендля обеспечения формирования сигналов;воспроизводящих номера циклов и тактовработы устройства.Элемент И 12 предназначен для выделения пачек импульсов из последовательности.Распределители 13 и 14 предназначенысоответственно для формирования сигналов номеров циклов и тактов работы устройства,Группа элементов И 151 - 15 с предназначена для формирования сигналов выборалюбого из С каналов многоканального блока 2 регистрации во втором такте очередного цикла оаботы устройства,Группа регистров 161 - 16 с предназначена для приема, хранения и выдачи кодоввершин маршрута.Единичный элемент 17 предназначендля обеспечения формирования кода начальной вершины маршрута,Наборное поле 18 предназначено дляформирования кода начальной вершинымаршрута. Элемент задержки 19 предназначен для удлинения продолжительностивоспро зведения кода начальной вершинымаршрута, с тем, чтобы этот код мог бытьзаписан в блоке 5 регистрации по заднемуфронту сигнала признака записи этого. блока.Группа элементов И 201 - 20 г предназначена для управления по времени процессом записи кода начальной вершинымаршрута в блоке 5 регистрации.Элемент задержки 21 предназначен длязадержки восприятия сигнала признака записи блока 5 регистрации до того момента,пока второй тактовый сигнал блока 1 синхронизации не примет нулевого значения,Группа элементов ИЛИ 221 - 22 г предназначена для записи в блок 5 регистрациив очередном цикле кода начальной вершины маршрута либо кода одной из остальныхвершин маршрута.Элемент ИЛИ 23 предназначен дляформирования сигнала установки блока 5регистрации по сигналу задания начальнойвершины маршрута либо по сигналу признака записи в блок 5 регистрации с второговыхода блока 1 синхронизации.Регистр 24 предназначен для приема,хранения и выдачи кода очередной верши 20 25 30 35 40 45 50 55 ны маршрута во втором такте кэ:д:дога цикла работы устройства.Дешифратор 25 предназначен для Формирования сигнала признака начальной вершины очередной дуги маршрута.Единичный элемент 26 предназначен для обеспечения процесса формирования кода множества дуг маршрута.Наборное поле 27 предназначено для формирования кода множества дуг маршру. та,Наборное поле 28 предназнацено для формирования кода множества дуг и вершин маршрута. Регистр 29 предназначен для приема,хранения и выдачи кода множества дуг ивершин маршрута.Каждый из группы шифраторов 301 -30 в предназначен для формирования кодаконечной вершины дуги маршрута, исходящей из вершины графа, одноименной сэтим шифратором.Группа элементов ИЛИ 311 - 31 г предназначена для выдачи кодов всех конечныхвершин дуг маршрута на выходе блока 4определения конечных вершин дуг.Элемент задержки 32 предназначен длязадержки восприятия сигнала признака записи в блоке 3 регистрации до тех пор, покапервый тактовый сигнал блока 1 синхронизации не примет нулевого значения.Регистр 33 предназначен для приема,хранения и выдачи кода очередной вершины маршрута в первом такте каждого циклаработы устройства,При нахождении устройства в начальном состоянии на всех его входах устанавливается нулевой потенциал. На выходеблока 5 регистрации устанавливается унитарный код начальной вершины маршрута,На выходе блока 4 определения концевыхвершин дуг устанавливается двоичный кодпервой после начальной вершины маршрута. На выходах остальных блоков устройстваустанавливается нулевой код.Для установки устройстве в начальноесостояние все его блоки предварительно устанавливают в ноль (соответствующие цепиопущены).В блоке 4 определения концевых вершин дуг путем проведения соответствующих коммутаций выставляют код дугимаршрута и код принадлежности дуг графа.Таким же образом в блоке 5 регистрациивыставляют код начальной вершины маршрута. Затем на входы 7 задания множествадуг маршрута и 8 задания начальной вершины маршрута подают один и тот же единичный сигнал, по заднему фронту которого45 50 55 регенерирует) нулевой код. Кодирование мвершин графа этим кодом должно быть заного кода с выхода состава множества концевых вершин дуг блока 4 определения концевых вершин дуг в блок 3 регистрации. По заднему фронту единичного сигнала с второго выхода блока 1 синхронизации происходит запись кода К-й вершины маршрута с информационного выхода блока 3 регистрации в К-ю секцию многоканального блока 2 регистрации и в блок 5 регистрации.В С-м цикле работы устройства при Т = В (Т - количество вершин маршрута), а также начиная с Т-го цикла при ТВ, блок 4 определения концевых вершин дуг формирует(а во втором из перечисленных случаев 5 10 15 20 25 30 35 40 прещено. Появление впервые этого кода в очередном цикле работы на выходе состава множества концевых вершин дуг блока 4 определения концевых вершин дуг означает, что в предыдущем цикле работы был сформирован код конечной вершины и что никакого другого кода, кроме нулевого, в оставшихся циклах работы устройства на укаэанном выходе не появится,По окончании С-го цикла работы устройства при Т = В в К-й секции многоканального блока 2 регистрации хранится код К-й вершины маршрута (без учета начальной), В случае ТВ в секциях с Т-й по С-ю этого блока хранится нулевой код, В обоих указанных случаях код начальной вершины маршрута хранится в блоке 5 регистрации.По окончании С-го цикла работы устройство переходит в режим хранения кодов, сформированных в режиме формирования кодов. В этом режиме устройство находится вплоть до его перевода в начальное состояние,Принцип работы устройства поясняет фиг,2,При установке устройства в начальное состояние на наборном поле 27 путем соответствующей коммутации между его входами и выходами выставляют Н-разрядный (Н-количество ветвей графа) двоичный код дуг маршрута с единичными значениями в тех разрядах, номера которых совпадают с номерами дуг маршрута. На наборном поле 28 таким же образом выставляют Н-разрядный коддуг и вершин маршрута. Последний представляет собой перегруппированный код дуг маршрута с расположением в одной и той же группе разрядов признаков дуг, исходящих из одной и той же вершины, и с числом групп, равным В. При этом каждый из Н выходов наборного поля 27 оказывается соединенным с помощью наборного поля 28 и регистра 29 с одним из входов одного из шифраторов группы 301 - 30 в. Кроме того, выходы наборного поля 27 оказываются объединенными в группы, одноименные с номерами вершин графа, таким образом, что в одной группе находятся выходы, одноименные с номерами дуг графа, исходящих из вершины, одноименной с номером группы. Из фиг.2 следует, что из первой вершины графа, которой соответствует 1-я группа выходов наборного поля 27 и шифратор 301, исходит О дуг, а из В-й вершины графа, которой соответствует В-я группа выходов наборного поля 27 и шифратор 30 в, исходит Н - Е + 1 дуг, На наборном поле 18 выставляют г-разрядный код начальной вершиныаршрута,В начальное состояние устройстьо, предварительно установленное в ноль, переводится единичным сигналом, одновременно поступающим на вход 7 задания множества дуг маршрута и вход 8 задания начальной вершины маршрута. По заднему фронту этого сигнала, поступающего на вход признака записи регистра 29, происходит запись Н-разрядного кода дуг и вершин маршрута, сформированного с помощью единичного элемента 26 и наборных полей 27 и 28, в этот регистр. Кроме того, по заднему фронту этого же сигнала, поступающего через элемент ИЛИ 23 с входа 8 задания начальной вершины маршрута на вход признака записи регистра 24, происходит запись кода начальной вершины графа, предварительно сформированного наборным полем 18 с помощью единичного элемента 17, через группу элементов И 201 - 20 г и группу элементов ИЛИ 221 - 22 г, в этот регистр. При этом элемент задержки 19 и радлевает присутствие кода начальной вершины маршрута на информационных выходах регистра 24 на величину, достаточную для осуществления записи в регистр 24 по заднему фронту второго тактового сигнала,По заднему фронту единичного сигнала с входа 6 запуска, поступающего на инверсный динамический вход признака записи триггера 10, происходит запись "1", воспроизводимой на единичном входе этого триггера в виде единичного потенциала единичным элементом 9, Начиная с этого момента времени устройство переходит в режим формирования кодов. В каждом цикле этого режима распределитель 14 на основе импульсов с выхода генератора импульсов 11, поступающих на информационный вход этого распределителя через элемент И 12, предварительно разблокированный единичным потенциалом с прямого выхода триггера 10, формирует последовательность во времени на своих первом и втором выходах одноименные единичные тактовые сигналы.В К-м цикле работы устройства в режиме формирования кодов появление единичного сигнала на первом выходе распределителя 14 сопровождается следующим, В блоке 5 регистрации происходит возбуждение К-го выхода дешифратора 25 и выбор сигналом с его К-го выхода дешифратора 30 к блока 4 определения концевых вершин дуг. Выходные сигналы последнего через группу элементов ИЛИ 311 - 31 г формируют на выходах последних г-разрядный код К-й вершины маршрута. По первому тактовому сигналу, поступающему непосредственно на установочный вход регистра 33, Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, первый блок регистрации и блок определения концевых вершин дуг, причем вход, пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к входу признака записи первого блока регистрации, выход состава множества концевых вершин дуг блока определения концевых вершин дуг подключен к информационному входе первого блока регистрации, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения последовательности вершин маршрутов в графе, в него введены блок определения последовательности вершин маршрута и второй блок регистрации, причем информационный выход первого блока регистрации подключен к информационному входу второго блока регистрации и к информационному входу блока определения последовательно 5 10 15 20 25 30 35 40 45 50 55 последний устанавливается в ноль,. По окончании действия этого сигнала нз выходе элемента задержки 32 формируется сигнал признака записи, по заднему фронту которого в регистр 33 записывается код К-й вершины маршрута с информационного выхода состава множества концевых вершин дуг блока 4 определения. концевых вершин дуг. По переднему фронту первого такта сигнала, поступающего непосредственно на информационный вход распределителя 13, на К-м выходе последнего формируется единичный сигнал К-го цикла.По окончании первого такта на втором выходе распределителя 14 формируется единичный сигнал второго такта. По этому сигналу, непосоедственно поступающему на установочный вход регистра 24, происходит установка в ноль последнего. Па заднему фронту сигнала с выхода элемента ИЛИ 23, формируемого элементом задержки 21 по окончании действия второго тактового сигнала, происходит запись кода К-й вершина маршрута с информационного выхода блока 3 регистрации через группу элементов ИЛИ 221 - 22 г в регистр 24. Кроме того, по заднему фронту второго тактового сигнала, поступающего через элемент 15 к на вход признака записи регистра 16 к, происходит запись в последний кода К-й вершины маршрута с информационного выхода блока 3 регистрации.В режиме хранения код начальной вершины маршрута воспроизводится на выходах наборного паля 18, а коды последующих вершин маршрутов - в регистрах 161 - 16 с.12 1777156 Фиг оставитель Ю. Беликовехред М.Моргентал Карре ндрушенко Редактор Г, Бельская Подписноеа по изобретениям и открытиям при ГКНТ СССЖ, Раушская наб., 4/5 каз 4123 ВНИИП Тираж Государственного коми 113035, Москроизводственно-издательский комбинат "Патент", г. Ужгород,арина. сти вершин маршрута, вход выбора К-го канала которого (К = 1, 2В, где В - количество вершин в графе) подключен в К-му выходу группы блока синхронизации, второй выход которого подключен к входу при знака записи блока определения последовательности вершин маршрута и к входу признака записи второго блока регистрации, К-й разряд информационного выхода которого подключен к входу опроса К-й начальной вершины дуги блока определения концевых вершин дуг, вход задания топологии графа которого является входом задания множества дуг маршрута устройства, вход задания начальной вершины маршрута которого подключен к установочному входу второго блока регистрации.