Устройство для решения задач на графах
Изобретение относится к области вычислительной техники и может быть использовано для анализа путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все остальные вершины графа, Устройство содержит многоканальный блок 1 регистрации, многоканальный накапливающий блок 2 формирования маршрута, многоканальный блок 3 выбора минимума, блок 4 выбора минимума, блок 5 синхронизации, вход 6 пуска, входы 7 задания веса ребер графа, выходы 8 состава кратчайшего пути в К-ю вершину графа. Перед началом работы в один из каналов блока 1 регистрации, соответствующий номеру начальной вершины , заносят маршрут, состоящий из одной начальной вершины, а остальные каналы обнуляют . По входам 7 устройства задают веса ребер (или дуг) графа. На вход пуска устройства подают сигнал уровня логической единицы . При этом блок 5 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устройства формируется состав кратчайших маршрутов из первой во все остальные вершины графа. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ о (л
Q0
Ю р
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4729168/24 (22) 09,08.89 (46) 30.09,92. Бюл. ¹ 36 (72) С.А.Ильин, С.В.Листровол, В.Я.Певнев, В.H,Màðèÿí и В,И,Сова (56) Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
Авторское свидетельство СССР
¹ 1639303, кл. G 06 F 15/419, 16,08.88, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
НА ГРАФАХ (57) Изобретение относится к области вычислительной техники и может быть использовано для анализа путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все остальные вершины графа, Устройство содержит многоканальный блок 1 регистрации, многоканальный накапливаю„„Я „„1765832 А1 щий блок 2 формирования маршрута, многоканальный блок 3 выбора минимума, блок 4 выбора минимума, блок 5 синхронизации, вход 6 пуска, входы 7 задания веса ребер графа, выходы 8 состава кратчайшего пути в
К-ю вершину графа. Перед началом работы в один из каналов блока 1 регистрации, соответствующий номеру начальной вершины, заносят маршрут, состоящий из одной начальной вершины, а остальные каналы обнуляют. По входам 7 устройства задают веса ребер (или дуг) графа, На вход пуска устройства подают сигнал уровня логической единицы, При этом блок 5 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устрой ства формируется состав кратчайших маршрутов из первой во все остальные вершины графа. 1 ил.
1765832
Изобретение относится к области вычислительной техники и может быть использовано для анализа путей в графах, Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все остальные вершины графа.
На чертеже представлена функциональная схема устройства.
Устройство для решения задач на гра фах содержит многоканальный блок 1 регистрации, многоканальный накапливающий блок 2 формирования маршрута, многоканальный блок 3 выбора минимума, блок 4 выбора минимума, блок 5 синхронизации, вход 6 пуска устройства, входы 7 задания веса ребер графа устройства, выходы 8 состава кратчайшего пути в К-ю вершину графа устройства, Устройство работает следующим образом.
Перед началом работы в один из каналов блока 1 регистрации, соответствующий номеру начальной вершины, заносят маршрут, состоящий из одной начальной вершины, а остальные каналы обнуляют. По входам 7 устройства задают веса ребер (или дуг) графа.
На вход пуска устройства подают сигнал уровня логической единицы. При этом блок 5 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, Блок 5 синхронизации формирует импульс уровня логической единицы на своем первом выходе. При этом каналы блока 2 проверяют наличие связи между соответствующей им по номеру в группе вершиной и конечной вершиной маршрута, поступившего на их входы задания маршрутов. В том случае, если указанные вершины связаны, каналы включают в состав поступившего на их входы маршрута вершину, номер которой совпадает с номером группы канала, если включение указанной вершины в состав маршрута не приводит к появлению замкнутого цикла, определяют вес маршрута (как сумму весов входящих в него ребер), запоминают (накапливают) вес и состав полученного маршрута и выдают вес маршрута на свои выходы весов маршрута. В противном случае (т.е. при отсутствии связности вершин или при появлении циклов) каналы выдают на свой выход веса маршрута максимально возможные значения. При этом каналы блока 3 выбора минимума выдают сигнал уровня логической единицы на тот свой выход, позиция которого соответству10
15 ет позиции информационного входа канала, на которую поступило наименьшее значение и выдают это значение на свои информационные входы (тем самым выбирается маршрут наименьшего веса в вершину, совпадающую по номеру с номером канала блока 3). При этом каналы блока 2 выдают на .выход соответствующей им группы состав своего маршрута.
Через время, достаточное для выполнения указанных операций, блок 5 синхронизации формирует импульс уровня логической единицы на своем втором выходе. При этом блок 4 выбора минимума выдает сигнал уровня логической единицы на тотсвой выход, позиция которогосоответствует позиции информационного входа, на которую поступило наименьшее значение
20 (тем самым из всех сформированных в данном такте работы маршрутов выбирается наименьший). При этом соответствующий ему канал блока 1 регистрации фиксирует установленное на его информационном вхо25 де значение (т,е. состав кратчайшего маршрута) и выдает его на свой информационный выход.
Через время, достаточное для выполнения укаэанных операций, блок 5 синхрони30 эации повторяет цикл выдачи синхроимпульсов на свои выходы. При этом работа устройства повторяется, Формула изобретения
Устройство для решения задач на гра35 фах, содержащее многоканальные блок регистрации, блок выбора минимума и накапливающий блок формирования маршрута, причем вход задания веса (К,М)-го ребра графа устройства (К . 1, ...., В; М = 1, „„, 40 В, где  — количество вершин в графе) подключен к одноименному входу многоканального накапливающего блока формирования маршрута, выход состава маршрута каналов
М-й группы которого подключен к информа45 ционному входу М-ro канала многоканального блока регистрации, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все
50 остальные вершины графа, в него введены блок выбора минимума и блок синхронизации, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к такто55 вому входу многоканального накапливающего блока формирования маршрутов, второй выход блока синхронизации подключен к входу опроса блока выбора минимума, M-й выход позиции минимума которого под, ключен к входу признака записи М-ro кана1765832
Составитель А.Мишин
Техред М.Моргентал Корректор Е.Папп
Редактор Т.Орловская
Заказ 3386 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 ла многоканального блока регистрации, информационный выход -ro канала которого является выходом состава кратчайшего пути в К-ю вершину графа устройства и подключен к входам задания состава маршрута
К-х каналов всех групп, выход веса маршрута К-го канала M-й группы которого подключен к К-му информационному входу M-ro канала многоканального блока выбора минимума, К-й выход позиции минимума М-го канала которого подключен к входу опроса состава маршрута M-й группы, информаци5 онный выход М-го канала многоканального блока выбора минимума подключен к М-му информационному входу блока выбора минимума.
