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

(51)5 6 06 Г 15/41 ПИСАНИЕ ИЗОБРЕТЕН ВТОРСКОМУ СВИДЕ ТВ,08.88,ИЯ ЗАДАЧ СО Ю ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(54) УСТРОЙСТВО ДЛЯ РЕШЕННА ГРАФАХ(57) Изобретение относится к области вычислительной техники и может быть использовано для анализа путей в графах, Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все остальные вершины графа, Устройство содержит многоканальный блок 1 регистрации, многоканальный накапливающий блок 2 формирования маршрута, многоканальный блок 3 выбора минимума, блок 4 выбора минимума, блок 5 синхронизации, вход 6 пуска, входы 7 задания веса ребер графа, выходы 8 состава кратчайшего пути в К-ю вершину графа. Перед началом работы в один из каналов блока 1 регистрации, соответствующий номеру начальной вершины, заносят маршрут, состоящий из одной начальной вершины, а остальные каналы обнуляют. По входам 7 устройства задают веса ребер (или дуг) графа, На вход пуска устройства подают сигнал уровня логической единицы, При этом блок 5 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 8 устрой ства формируется состав кратчайших маршрутов из первой во все остальные вершины графа. 1 ил.Изобретение относится к области вычислительной техники и может быть использовано для анализа путей в графах,Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего путииз начальной во все остальные вершиныграфа.На чертеже представлена функциональная схема устройства.Устройство для решения задач на гра фах содержит многоканальный блок 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 ционному входу М-го канала многоканального блока регистрации, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия устройства при решении задачи определения кратчайшего пути из начальной во все50 остальные вершины графа, в него введеныблок выбора минимума и блок синхронизации, причем вход пуска устройства подключен к входу пуска блока синхронизации,первый выход которого подключен к такто 55 вому входу многоканального накапливающего блока формирования маршрутов,второй выход блока синхронизации подключен к входу опроса блока выбора минимума,М-й выход позиции минимума которого под, ключен к входу признака записи М-го кана1765832 Составитель А.МишинТехред М.Моргентал Корректор Е Папп Редактор Т.Орловская Заказ 3386 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 ла многоканального блока регистрации, информационный выход К-го канала которого является выходом состава кратчайшего пути в К-ю вершину графа устройства и подключен к входам задания состава маршрута К-х каналов всех групп, выход веса маршрута К-го канала М-й группы которого подключен к К-му информационному входу М-го канала многоканального блока выбора минимума, К-й выход позиции минимума М-го канала которого подключен к входу опроса состава маршрута М-й группы, информаци онный выход М-го канала многоканальногоблока выбора минимума подключен к М-му информационному входу блока выбора минимума.