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

 

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

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

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4683233/24 (22) 27.04.89 (46) 23,11.92. Бюл. ¹ 43 (72) Ю.В.Беликов и П.А.Жигора (56) Авторское свидетельство СССР № 1587534, кл. G 06 F 15/20, 1988, Авторское свидетельство СССР № 1683035, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач, связанных с определением кратчайших путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет. Ж 7П715о А) определения последовательности вершин маршрутов в графе. Устройство содержит блок 1 синхронизации, многоканальный блок регистрации, (блок определения последовательности вершин маршрута), первый блок 3 регистрации, блок 4 определения концевых вершин дуг, второй блок 5 регистрации, вход пуска, вход 7 задания множества дуг маршрута и вход 8 задания начальной вершины маршрута. При поступлении на вход 6 пуска импульса уровня логической единицы блок 1 синхронизации формирует на своих выходах последовательность сигналов, под управлением которой s блоке 2 регистрации накапливается искомая последовательность вершин, 2 ил.

1777156

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

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

Указанная цель достигается тем, что в устройство введены блок определения последовательности вершин маршрута и второй блок регистрации, причем информационный выход первого блока регистрации подключен к информационному входу второго блока регистрации и к информационному входу блока определения последовательности вершин маршрута, вход выбора -ro канала которого (K = 1, 2,..., В1, где B — количество вершин в графе) подключен к К-му выходу группы блока синхронизации, второй выход которого подключен к входу признака записи блока определения последовательности вершин маршрута и к входу признака записи второго блока регистрации, К-й разряд(К = 1, ...,В) информационного выхода которого подключен к входу опроса К-й начальной вершины дуги блока определения концевых вершин дуг, вход задания топологии графа которого является входом задания множества дуг маршрута устройства, вход задания начальной вершины маршрута которого подключен к установочному входу второго блока регистрации.

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

Структурная схема содержит блок 1 синхронизации. многоканальный блок 2 регист5 рации (блок определения последовательности вершин маршрута), блок 3 регистрации, блок 4 определения концевых вершин дуг, блок 5 регистрации, вход 6 пуска, вход 7 задания множества дуг

10. маршрута и вход 8 задания начальной вершины маршрута.

Функциональная схема содержит единичный элемент 9, триггер 10, генератор импульсов 11, элемент И 12, распределите15 ли 13 и 14, группу элементов И 151 — 15с (С = В = 1;  — количество вершин в графе), группу регистров 16 — 16с, единичный элемент 17, наборное поле 18, элемент задержки 19, группу элементов И 201 — 20г, 20 элемент задержки 21, группу элементов

ИЛИ 221 — 22r элемент ИЛИ 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 предназначен для обеспечения формирования сигнала и на1777156

10 хождении устройства в режиме формирования кодов.

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

Генератор имгульсов 11 предназначен для обеспечения формирования сигналов; воспроизводящих номера циклов и тактов работы устройства.

Элемент И 12 предназначен для выделения пачек импульсов из последовательности.

Распределители 13 и 14 предназначены соответственно для формирования сигналов номеров циклов и тактов работы устройства, Группа элементов И 15 — 15с предназначена для формирования сигналов выбора любого из С каналов многоканального блока 2 регистрации во втором такте очередного цикла работы устройства, Группа регистров 161 — 16c предназначена для приема, хранения и выдачи кодов вершин маршрута.

Единичный элемент 17 предназначен для обеспечения формирования кода начальной вершины маршрута.

Наборное поле 18 предназначено для формирования кода начальной вершины маршрута. Элемент задержки 19 предназначен для удлинения продолжительности воспро зведения кода начальной вершины маршрута, с тем, чтобы этот код мог быть записан в блоке 5 регистрации по заднему фронту сигнала признака записи этого . блока.

Группа элементов И 201 — 20г предназначена для управления по времени процессом записи кода начальной вершины маршрута в блоке 5 регистрации.

Элемент задержки 21 предназначен для задержки восприятия сигнала признака записи блока 5 регистрации до того момента, пока второй тактовый сигнал блока 1 синхронизации не примет нулевого значения.

Группа элементов ИЛИ 22 — 22г предназначена для записи в блок 5 регистрации в очередном цикле кода начальной вершины маршрута либо кода одной из остальных вершин маршрута.

Элемент ИЛИ 23 предназначен для формирования сигнала установки блока 5 регистрации по сигналу задания начальной вершины маршрута либо по сигналу признака записи в блок 5 регистрации с второго выхода блока 1 синхронизации.

Регистр 24 предназначен для приема, хранения и выдачи кода очередной верши20

55 ны маршрута Ro BTopoM такте каждого цикла работы устройства.

Дешифратор 25 предназначен для формирования сигнала признака начальной вершины очередной дуги маршрута.

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

Наборное поле 27 предназначено для формирования кода множества дуг маршру, та, Наборное поле 28 предназначено для формирования кода множества дуг и вершин маршрута.

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

Каждый из группы шифраторов 30i—

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

Группа элементов ИЛИ 311 — 31 предназначена для выдачи кодов всех конечных вершин дуг маршрута на выходе блока 4 определения конечных вершин дуг.

Элемент задержки 32 предназначен для задержки восприятия сигнала признака записи в блоке 3 регистрации до тех пор, пока первый тактовый сигнал блока 1 синхронизации не примет нулевого значения.

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

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

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

Для установки устройстве в начальное состояние все его блоки предварительно устанавливают в ноль (соответствующие цепи опущены).

В блоке 4 определения концевых вершин дуг путем проведения соответствующих коммутаций выставляют код дуги маршрута и код принадлежности дуг графа.

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

1777156

50

55 регенерирует) нулевой код. Кодирование м вершин графа этим кодом должно быть заустройство переходит в начальное состояние, устройство работает в двух режимах работы: формирования кодов и хранения, В режиме формирования кодов устройство формирует последовательность кодов вершин маршрута и осуществляет их запоминание, В этот режим устройство переводится иэ начального состояния по заднему фронту единичного сигнала, поступающего на вход 6 пуска устройства. Процесс формирования последовательности кодов вершин маршрута осуществляется в течение С циклов(С = В = 1). Длительность К-ro цикла(К=

1„...С) воспроизводится одиночным сигналом на К-м выходе группы блока 1 синхронизации. Каждый цикл состоит из непересекающихся во времени первого и второго тактов, начало каждого из которых воспроизводится передним фронтом единичного сигнала с одноименного выхода блока 1 синхронизации. Длительность как первого, так и второго тактовых сигналов не должна превышать 1/4 длительности сигнала цикла. Этим обеспечивается возможность формирования на основе каждого из них разновременно воспроизводимых сигнала установки и сигнала признака записи для блоков 3 или 5 регистрации, действующих в пределах одного и того же такта, т.е. одной и той же половины цикла.

В первом такте К-го цикла многоканальный блок 2 регистрации сигналом с К-го выхода группы блока 1 синхронизации подготавливается к записи в свою К-ю секцию кода К-й вершины (без учета начальной вершины маршрута.8 этом же такте в блоке 4 определения концевых вершин дуг происходит формирование кода К-й вершины маршрута и выдача его на свой выход состава множества концевых вершин дуг, По заднему фронту единичного сигнала первого такта К-ro цикла с первого выхода блока 1 синхронизации происходит запись указанного кода с выхода состава множества концевых вершин дуг блока 4 определения концевых вершин дуг в блок 3 регистрации.

По заднему фронту единичного сигнала с второго выхода блока 1 синхронизации происходит запись кода К-й вершины маршрута с информационного выхода блока 3 регистрации в К-ю секцию многоканального блока

2 регистрации и в блок 5 регистрации.

В С-м цикле работы устройства при Т =

В (T — количество вершин маршрута), а также начиная с T-ro цикла при Т < В, блок 4 определения концевых вершин дуг формирует(а во втором из перечисленных случаев

40 прещено. Появление впервые этого кода в очередном цикле работы на выходе состава множества концевых вершин дуг блока 4 определения концевых вершин дуг означает, что в предыдущем цикле работы был сформирован код конечной вершины и что никакого другого кода, кроме нулевого, в оставшихся циклах работы устройства на укаэанном выходе не появится, По окончании С-ro цикла работы устройства при Т = В в К-й секции многоканального блока 2 регистрации хранится код К-й вершины маршрута (без учета начальной). В случае Т<В в секциях с Т-й по С-ю этого блока хранится нулевой код. В обоих указанных случаях код начальной вершины маршрута хранится в блоке 5 регистрации.

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

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

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

28 и регистра 29 с одним из входов одного из шифраторов группы 30> — 30я. Кроме того, выходы наборного поля 27 оказываются объединенными в группы, одноименные с номерами вершин графа, таким образом, что в одной группе находятся выходы, одноименные с номерами дуг графа, исходящих из вершины, одноименной с номером группы. Из фиг.2 следует, что из первой вершины графа, которой соответствует 1-я группа выходов наборного поля 27 и шифратор 30, исходит D дуг, а из В-й вершины графа, которой соответствует В-я группа выходов наборного поля 27 и шифратор 30, исходит

Н - Е + 1 дуг. На наборном поле 18 выставляют r-разрядный код начальной вершины аршрута.

1 77156

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

27 и 28, в этот регистр. Кроме того, по заднему фронту этого же сигнала, поступающего через элемент ИЛИ 23 с входа 8 задания начальной вершины маршрута на вход признака записи регистра 24, происходит запись кода начальной вершины графа, предварительно сформированного наборным полем 18 с помощью единичного элемента 17, через группу элементов И 20 — 20г и группу элементоь ИЛИ 22 — 22г, в этот регистр. При этом элемент задержки 19 и радлевает присутствие кода начальной вершины маршрута на информационных выходах регистра 24 на величину, достаточную для осуществления записи в регистр 24 по заднему фронту второго тактового сигнала.

По заднему фронту единичного сигнала с входа 6 запуска, поступающего на инверсный динамический вход признака записи триггера 10, происходит запись "1", воспроизводимой на единичном входе этого триггера в виде единичного потенциала единичным элементом 9, Начиная с этого момента времени устройство переходит в режим формирования кодов. В каждом цикле этого режима распределитель 14 на основе импульсов с выхода генератора импульсов 11, поступающих на информационный вход этого распределителя через элемент И 12, предварительно разблокированный единичным потенциалом с прямого выхода триггера 10, формирует последовательность во времени на своих первом и втором выходах одноименные единичные тактовые сигналы.

В К-м цикле работы устройства в режиме формирования кодов появление единичного сигнала на первом выходе распределителя 14 сопровождается следующим. В блоке 5 регистрации происходит возбуждение К-го выхода дешифратора 25 и выбор сигналом с его К-го выхода дешифратора ЗОК блока 4 определения концевых вершин дуг. Выходные сигналы последнего через группу элементов ИЛИ 31 — 31г формируют на выходах последних r-разрядный код К-й вершины маршрута. По первому тактовому сигналу, поступающему непосредственно на установочный вход регистра 33, 5

55 последний fñòçHý вливается в ноль,. ПО окончании действия этого сигнала на выходе элемента задержки 32 формируется сигнал признака записи, по заднему фронту которого в регистр 33 записывается код К-й вершины маршрута с информационного выхода состава множества концевых вершин дуг блока 4 определения концевых вершин дуг.

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

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

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

23, формируемого элементом задержки 21 по окончании действия второго тактового сигнала, происходит запись кода К-й вершина маршрута с информационного выхода блока 3 регистрации через группу элементов ИЛИ 22 — 22г в регистр 24. Кроме того, по заднему фронту второго тактового сигнала, поступающего через элемент 15к на вход признака записи регистра 16v„происходит запись в последний кода К-й вершины маршрута с информационного выхода блока 3 регистрации.

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

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

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

1777156

Oxr. 2

Составитель IQ. Беликов

Техред М.Моргентал. Корректор М. Андрушенко

Редактор Г. Бельская

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина.101 сти вершин маршрута, вход выбора K-ro канала которого (К = 1, 2,...,8-1, где  — количество вершин в графе) подключен в К-му выходу группы блока синхронизации, второй выход которого подключен к входу при- 5 знака записи блока определения последовательности вершин маршрута и к входу признака записи второго блока регистрации, К-й разряд информационного выхода которого подключен к входу опроса К-й начальной вершины дуги блока определения концевых вершин дуг, вход задания топологии графа которого является входом задания множества дуг маршрута устройства, вход задания начальной вершины маршрута которого подключен к установочному входу второго блока регистрации.