Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

г

8

6

W

ч|

О

ел

00

со

к

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

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

На чертеже представлена функциональная схема устройства.

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

Устройство работает следующим образом.

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

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

Блок 5 синхронизации формирует импульс уровня логической единицы на своем первом выходе. При этом каналы блока 2 проверяют наличие связи между соответствующей им по номеру в группе вершиной и конечной вершиной маршрута, поступившего на их входы задания маршрутов. В том случае, если указанные вершины связаны, каналы включают в состав поступившего на их входы маршрута вершину, номер которой совпадает с номером группы канала, если включение указанной вершины в состав маршрута не приводит к появлению замкнутого цикла, определяют вес маршрута (как сумму весов входящих в него ребер), запоминают (накапливают) вес и состав полученного маршрута и выдают вес маршрута на свои выходы весов маршрута. В противном случае (т.е. при отсутствии связности вершин или при появлении циклов) каналы выдают на свой выход веса маршрута максимально возможные значения. При этом каналы блока 3 выбора минимума выдают сигнал уровня логической единицы на тот свой выход, позиция которого соответствует позиции информационного входа канала, на которую поступило наименьшее значение и выдают это значение на свои информационные входы (тем самым выбирается

маршрут наименьшего веса в вершину, совпадающую по номеру с номером канала блока 3). При этом каналы блока 2 выдают на выход соответствующей им группы состав своего маршрута.

0

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

0 (тем самым из всех сформированных в данном такте работы маршрутов выбирается наименьший). При этом соответствующий ему канал блока 1 регистрации фиксирует установленное на его информационном вхо5 де значение (т.е. состав кратчайшего маршрута) и выдает его на свой информационный выход.

Через время, достаточное для выполнения указанных операций, блок 5 синхрони0 зации повторяет цикл выдачи синхроимпульсов на свои выходы. При этом работа устройства повторяется. Формула изобретения Устройство для решения задач на гра5 фах, содержащее многоканальные блок регистрации, блок выбора минимума и накапливающий блок формирования маршрута, причем вход задания веса (К,М)-го ребра графа устройства (К . 1В; М 1

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

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

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

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