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

ю

9uz. т Иэобретение относится квычислительной технике и. может быть использовано для исследования путей в . Целью изобретения является расширение функциональных возможностей устройства за счет определейия матри цы кратчайших путей в графе. На фиг.1 представлена функциональ ная схема устройства; на фиг.2 - опи сание алгоритма решения задачи; на фиг.З - пример. Устройство содержит блок 1 синхронизации, многоканальный накапливающий блок 2 выбора минимума, блок 3 моделирования волнового процесса, второй многоканальный блок 4 сравнения, блок 5 формирования волнового процесса, первый многоканальный блок 6 сравнения, вход 7 пуска устройства выходы 8 и 9 блока 1 синхронизации и выходы 10 весов кратчайших путей в ; графе устройства. Устройство работает следующим образом. Пусть необходимо определить матри цу величин кратчайших йутей в графе, т.е. значение кратчайшего пути из лю бой вершины графа в любую другую его вершину. Рассмотрим алгоритм решения задач в терминах клеточных автоматов. Для нахождения матрицы величин кратчайших путей между всеми парами вершин графа с В вершинами потребуется клеточный автомат размером ВхВ, В каждой клетке находится автомат, имеющий 5 входов и 5 выходов (см. фиг.2е). . Каждый автомат может обмениваться сигналами с четырьмя ближайшими сосе дями по горизонтали и вертикали, получать сигнал от автомата, находящегося сверху слева, передавать сигнал . автомату, находящемуся справа внизу. Внутреннее состояние автомата с индексом ij определяют (i 1,...,В; J I,...,D)I а)степень активности: пассивное; А1; А2; б)хранимое число Bj:, принимающе счетное множество значений: со, +1, -1, +2, -2, +3,.. Казвдая клетка может обмениваться счетным множеством сигналов е, еу, е, , e/L, е,,..., с соседними по горизонтали и вертикали, получать по диагональному входу и передавать по диагональному ВЫХ.ОДУ спецсигнаоТ f. Обозначим сигнал е угловой скобкой , сигналы е - - стрелкой-, сигнал f - волнистой линией . Тогда правила переходов автомата, необходимые для решения указанной задачи, имеют вид, показанный на фиг.2а-д. В группах правил а-г внутри клетки указано значение числа В-- , в группе правил д - степень активности (при этом значение числа В ,-1 произвольно, пустая клетка соответствует пассивному состоянию). Настройка на решаемую задачу осуществялется путем отображений матрицы весов исследуемого графа в клеточную структуру. А именно в клетке ij устанавливается равным весу ребра из i в j, если такое ребро существует, и с в противном случае. Запуск решения осзтцествляется подачей спецсигнала f на диагональный вход клетки 1,1. Процесс завершается стабилизацией состояний не более чем через 5 В тактов. При этом В ij, равно величине кратчайшего пути из i в j. Пусть, например, матрица смежнйсти неориентированного графа имеет вид, показанный на фиг.3.1. Тогда процесс решения по указанным правилам примет вид, по-казанный на фиг.3.1-3.20. Перед началом работы в каналы многоканального накапливающего блока 2 выбора минимума заносят значения весов соответствующих ребер графа, устанавливают в исходное состояние блок 3 моделирования волнового процесса и блок 5 формирования волнового процесса. На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах 8 и 9 последовательность сигналов, предусмотренную временной диаграммой его работы. При этом блок 5 формирует на своих выходах признаков наличия горизонтальной и вертикальной волн в точках пространства последовательность сигналов уровня логической единицы, определяющих используемый волновой процесс (т.е. можно говорить. Что блок 5-последовательно (по каж- дому второму тактовому импульсу) инициализирует волну в диагональных элементах матрицы (точках пространства,- заданного матрицей), начиная с первого диагонального элемента и

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

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

Следует отметить, что блоки 1-6 предлагаемого устройства (как, впрочем, и блоки любьпс вычислительных устройств) допускают как аппаратн.

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

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

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

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

подключен к входу признака начала

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

Х

ею

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

у

Ар

«N

8j

/f /,2,...c«; t, M - mifiiK L- j

Фиг. 2

vti

HN

e