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

 

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

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

СОРИА ЛИСТИЧЕСНИХ

РЕСПУБЛИН, SU 1Щ6343

А! щ) G 06 F 15/20 .

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

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

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

ПРИ ГКНТ СССР

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4406541/24-24 (22) 08.04.88 (46) 30.09.90. Бюл. К - 36 (72) В.Ю.Анисимов, И.Х.Галимзянов, П.В.Денисович, А.В.Тихобаев, А.Г.Шевчик и Н.А.Сидоренко (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 1425705, кл. G 06 F 15/20, 1987. (54) УСТРОЙСТВО ДЛЯ РЕНЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения матрицы,кратчайших путей в графе. Устройство содержит блок 1 синхронизации, многоканальный накапливающий

2 блок 2 выбора минимума, блок 3 моделирования волнового процесса, мно-, гоканальный блок 4 сравнения, блок

5 формирования волнового процесса, многоканальный блок 6 сравнения, вход 7 пуска, выходы 8 и 9 блока 1 синхронизации и выходы 10 весов кратчайших путей в графе устройства.

Перед началом работы в каналы блока

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

8, 9 последовательность сигналов, под управлением которых каналы блока

2 накапливают значения кратчайших путей из каждой вершины графа в любую другую его вершину. 3 ил.

1596343

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

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

На фиг. 1 представлена функциональ- 10 ная схема устройства; на фиг.2 — описание алгоритма решения задачи; на фиг.3 — пример.

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

3 моделирования волнового процесса, второй многоканальный блок 4 сравнения, блок 5 формирования волнового процесса, первый многоканальный блок

6 сравнения, вход 7 пуска устройства, выходы 8 и 9 блока 1 синхронизации и выходы 10 весов кратчайших путей в графе устройства.

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

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

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

Для нахождения матрицы величин кратчайших путей между всеми парами

35 вершин графа с В вершинами потребуется клеточный автомат размером

BxR. В каждой клетке находится автомат, имеющий 5 входов и 5 выходов (см. фиг.2е).

Каждый автомат может обмениваться

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

Внутреннее состояние автомата с индексом ij определяют (i = 1,...,В;

«1 = 1,...,в): е

a) степень активности: пассивное;

А1; А2; б) хранимое число В °, принимающее

% счетное множество значейий: ео, +1, -1, +2, -2, +3,...

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

Обозначим сигнал е угловой скобкой

>, сигналы е — стрелкой -, сигнал

1 волнистой линией - . Тогда правила переходов автомата, необходимые для решения указанной задачи, имеют вид, показанный на фиг.2а-д. В группах правил а-г внутри клетки указано значение числа В;, в группе правил д — степень активности (при этом значение числа В; произвольно, пустая клетка соответствует пассивному состоянию).

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

В" устанавливается равным весу реб1! ра из i в j если такое ребро существует, и с в противном случае. Запуск решения осуществляется подачей спецсигнала f на диагональный вход клетки 1, 1. Процесс завершается стабилизацией состояний не более чем через

5 В тактов. При этом В ц, равно величине кратчайшего пути из 1 в j . Пусть, например, матрица смежнОсти неориентированного графа имеет вид, показанный на фиг.3.1. Тогда процесс решения по указанным правилам примет вид, показанный на фиг.3.1-3.20.

Перед началом работы в каналы многоканального накапливающего блока 2 выбора минимума заносят значения весов соответствующих ребер графа, устанавливают в исходное состояние блок

3 моделирования волнового процесса и блок 5 формирования волнового процесса.

На вход 7 пуска устройства подают импульс уровня логической едини-: цы. При этом блок 1 синхронизации формирует на своих выходах 8 и 9 по следовательность сигналов, предусмотренную временной диаграммой его работы. При этом блок 5 формирует на своих выходах признаков наличия горизонтальной и вертикальной волн в точках пространства последовательность сигналов уровня логической единицы, определяющих используемый волновой процесс (т ° е. можно говорить, что блок 5 последовательно (по каждому второму тактовому импульсу) инициализирует волну в диагональных элементах матрицы (точках пространства, заданного матрицей), начиная с первого диагонального элемента и

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

При этом блок 3 инициализирует в каждой из укаэанных точек пространства горизонтальные и вертикальные волны заданной амплитуды.

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

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

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

10

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

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

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

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

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

1596343

УЛ ов оо е

Д е ю Я

Еб ! б

Составитель А.липин

Редактор Л.Веселовская Техред Л.Олийнык. Корректор 0.Ibrплe г

Заказ 2911 Тираж 571 . Подписное

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

113035, Иосква, K-35, Раушская наб., д. 4/5 !

Производственно-издательский комбинат "Патент", r.Óæãîðoä, ул. Гагарина, 101