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

) В И.Х.Галимзянов,В.Тихобаев, А.Г.Шеко процесс внения, 9 блока рмирногокаход 7 П.В.Денисо чик и Н,А. (53) 681.3 (56) Автор Ф 1425705,Сидоре 33 (088 ское с синхр они закратчайшихПеред начал2 заносят весов устройства налы блока.8)видетельство СССР 06 Р 15/20, 1987. соответств Б)ЕНИЯ 3 ю устанавлнное) сод 7 пуульс ур ивают в исстояние о локи ойст а устня логиче синхро- выходах этом блна своихность си к н 8 гналов,налы блотчайшихафа в л 10 правлением к торых к ения кр ршины г 2 накапливают энач путей из каждой ве бую другую его вер шину. ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ И К АВТОРСКОМУ СВИ(54) УСТРОЙСТВО ДЛЯ РЕ АДАЧНА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах, Целью изобретения является расширение функциональных возможностейустройства за счет определения ма"трицы,кратчайших путей в графе. Устройство содержит блок 1 синхронизации, многоканальный накапливающий 2блок 2 выбора минимумаделирования волнового ный блок 4 сравнеования волновогоальный блок 6 срауска, выходы 8 иции и .выходы 10путей в графеом работы в казначения весов ребер графа, е (невозбужд 3 и 5. На в ва подают имп единицы. При ии формирует последователИзобретение относится к вычислительной технике и.может быть использовано для исследования путей в графах,5Целью изобретения является расширение функциональных возможностейустройства за счет определейия матрицы кратчайших путей в графе,На фиг. 1 представлена функциональная схема устройства; на фиг.2 - описание алгоритма решения задачи; нафиг.3 - пример.Устройство содержит блок 1 синхронизации, многоканальный накапливающий блок 2 выбора минимума, блок3 моделирования волнового процесса,второй многоканальный блок 4 сравнения, блок 5 формирования волновогопроцесса, первый многоканальный блок6 сравнения, вход 7 пуска устройства,выходы 8 и 9 блока 1 синхронизации ивыходы 10 весов кратчайших путей вграфе устройства.Устройство работает следующим образом.Пусть необходимо определить матрицу величин кратчайших путей в графе,т.е. значение кратчайшего пути из любой вершины графа в любую другую еговершину,Рассмотрим алгоритм решения задачив терминах клеточных автоматов.Для нахождения матрицы величинкратчайших путей между всеми парами35вершин графа с В вершинами потребуется клеточный автомат размеромВхВ. В каждой клетке находится автомат, имеющий 5 входов и 5 выходов(см. Фиг.2 е).40Каждый автомат может обмениваться" сигналами с четырьмя ближайшими соседями по горизонтали и вертикали, получать сигнал от автомата, находящегося сверху слева, передавать сигнал 45-1, +2, -2, +3,Каждая клетка может обмениватьсясчетным множеством сигналов ер, е ,е, , е, е с соседними по го-ризонтали и вертикали, получать подиагональному входу и передавать по диагональному выхаду спецсигнал Обозначим сигнал е угловой скобкой , сигналы е - стрелкой -, сигнал Г - волнистой линией - . Тогда правила переходов автомата, необходимые для решения указанной задачи, имеют вид, показанный на фиг.2 а-д. В группах правил а-г внутри клетки указано значение числа В; , в группе правил д - степень активности (при этом значение числа В; произвольно, пустая клетка соответствует пассивному состоянию).Настройка на решаемую задачу осуществялется путем отображений матрицы весов исследуемого графа в клеточную структуру. А именно, в клетке 11 В устанавливается равным весу реб 1ра из д в 1, если такое ребро существует, и сь в противном случае, Запуск решения осуществляется подачей спецсигнала Е на диагональный вход клетки 1, 1, Процесс завершается стабилизацией состояний не более чем через 5 В тактов. При этом В ц, равно величине кратчайшего пути из 1 в 1. Пусть, например, матрица смежнОсти неориентированного графа имеет вид, показанный на фиг.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 510 15 20 25 30 35 40 45 50 55 так и программную реализацию (т.е,могут быть блоками параллельного ал-.горитма). Кроме того, если блоки 1-6имеют матричную структуру, то, используя методы модульной оптимизации,можно построить однородную структуру, которая характеризуется простотой наращивания аппаратных средствс целью увеличения размерности решаемой задачи (в данном случае. порядка матрицы кратчайших путей). Формула изобретения Устройство для решения задач на графах, содержащее блок формирования волнового процесса, два многоканальных блока сравнения, блок моделирования волнового процесса и блок синхронизации, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовым входам блока моделирования волнового процесса и блока формирования волнового процесса, выход признака наличия горизонтальной волны в (К,М)-й точке пространства которого (К = 1В; М = - 1В, где В - количество вершин в графе) подключен к входу опроса (К,М)-го канала первого многоканального блока сравнения, выход признака наличия вертикальной волны в (К,М)-й точке пространства блока формирования волнового процесса подключен к входу опроса (К,М)-го канала второго многоканального блока сравнения, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения матрицы кратчайших путей в графе, в него введен многоканальный накапливающий блок выбора минимума, причем второй выход блока синхронизации подключен к тактовому входу многоканального накапливающего блока выбора минимума, информационный выход (К,М)-го канала которого является выходом веса (К,М)-го кратчайшего пути устройства и подключен к входу задания амплитуды волны в (К,М)-й точке пространства блока моделирования волнового процесса, к информационному входу (К,И)-го канала первого иного- канального блока сравнения и к информационному входу (К,М)-го канала второго многоканального блока сравнения, выход признака отсутствия бесконеч 1596343но большого значения которого подключен к входу признака начала моделирования горизонтальной волны в (К,М) -й точке пространства блока моделирования волнового процесса, выход признака отсутствия бесконечно большого значения (К,М)-го канала первого многоканальногоблока сравнения подключен к входу признака началаУЯ моделирования вертикальной волны в(К,М)-й точке пространства блока моделирования волнового процесса, выходсуммарной амплитуды в (К,М)-й точкепересечения горизонтальной и вертикальной волн которого подключен к информационному входу (К,М)-го каналамногоканального накапливающего блока выбора минимума.1. 11 ипле актор Л.Веселовска оррект ираж 57 аказ 291 писное и ГКНТ СССР кий комбинат "Патент", г.Ужгород, ул. Гагарина, 10 изводственно сударственного комитета по изобретениям и открытия 113035, Иосква, В, Рауаская наб., д. 4/5