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

(51)5 6 06 Е 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ КОМУ СВИДЕТЕЛЬСТВУ В управлен асполож фиксиру ем которои в посленых ячейках блока 5ся сортируемые пуработы, поддовательнорегистрацити. 1 ил.(56) Авторское свидетельство СССР М 1444830, кл, О 06 С 7/122, 1987.Авторское свидетельство СССР М 1683037, кл, 6 06 Р 15/419, 15,03.89.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к области вычислительнбй техники и может быть использовано для анализа экстремальных (кратчайших и/илидлиннейших) путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания). Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3 регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации, вход 6 пуска устройства, выход 7 признака окончания работы устройства, вход 8 задания количества сортируемых путей устройства, вход 9 задания начальной вершины пути устройства, вход 10 задания конечной вершины пути устройства, входы 11 признаков наличия дуг устройства, вход 12 начальной установки устройства, входы 13 задания веса дуг устройства и вход 14 задания режима сортировки. Пусть необходимо определить в порядке убывания (возрастания) их веса несколько длиннейших (кратчайших) путей в графе между заданной парой вершин, Перед началом работы по входам 8, , 14 задают необходимые для работы исходные данные. На вход пуска устройства подают импульс уровня логическойединицы. При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его10 15 20 Изобретение относится к области вычислительной техники и может быть использовано для анализа экстремальных(кратчайших и/или длиннейших) путей вграфах.Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальныхпутей в графе в порядке их возрастания(убывания).На чертеже представлена функциональная схема устройства.Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации, вход 6 пуска устройства, выход 7признака окончания работы устройства,вход 8 задания количества сортируемых путей устройства, вход 9 задания начальнойвершиныпути устройства, вход 10 заданияконечной вершины пути устройства, входы11 признаков наличия дуг устройства, вход12 начальной установки устройства, входы13 задания веса дуг устройства и вход 14задания режима сортировки.Устройство работает следующим образом.Пусть необходимо определить в порядке убывания (возрастания) их веса несколько длиннейших (кратчайших) путей в графемежду заданной парой вершин,Перед началом работы по входам 9, 10,11 устройства соответственно задают начальную, конечную вершины графа и еготопологию. По входу 8 устройства задаютзначение количества сортируемых путей,При этом блок 1 синхронизации фиксируетдопустимое количество своих перезапусков(повторных пусков). По входам 13 устройства задают веса дуг графа. При этом каналыблока 3 регистрируют поданные на них значения (веса дуг). По входу 14 задают режимсортировки (возрастание/убывание), Приэтом блок 4 регистрирует максимально возможное (при выборе минимума) или минимально возможное (при выборе максимума)значение, которое в дальнейшем будет использоваться в качестве исходного значения при выполнении операции сравнения.На вход начальной установки устройстваподают импульс уровня логической единицы, При этом блок 2 устанавливает (регистрирует) потенциалы уровня логическойединицы на тех своих выходах признаковпринадлежности дуг текущему маршруту,которые соответствуют дугам первого измаршрутов, соединяющего заданные начальную и конечную вершины графа при заданном наборе его дуг, блок 5 устанавливает адрес своей первой регистрирующей ячейки, Одновременно многоканальный блок 3 регистрации выдает на выходы опрошенных каналов установленные ранее значения (веса дуг, входящих в текущиймаршрут),На вход пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих первом и втором выходах последовательность сигналов, предусмотренную временной диаграммой его работы.Блок 1 формирует импульс уровня логической единицы на своем втором выходе. При этом блок 4 вычисляет сумму всех поступивших на его входы слагаемых и сравнивает ее (сумму) со значением, зарегистрированным в одном из предыдущих тактов работы, В том случае, если по входу выбора типа экстремума установлен выбор максимума, и значение суммы, вычисленное в данном такте работы, больше зарегистрированного значения или, если по входу выбора типа экстремума установлен выбор минимума и значение суммы, вычисленное в данном такте работы, меньше зарегистрированного значения, блок 4 регистрирует вычисленное значение суммы (заменяет на него значение, зарегистриро- . ванное в предыдущих тактах работы), выдает его на свой выход текущего значения суммы и формирует импульс уровня логической единицы на своем выходе признака наличия экстремума. При этом блок 5 регистрирует по текущему адресу значения, установленные на его информационных входах, и выдает на свой информационный выход значение, поступившее по первому информационному входу (вес длиннейшего, кратчайшего из всех перечисленных ранее путей),Через время, достаточное для выполнения указанных операций, блок 1 синхронизации формирует импульс уровня логической единицы на своем первом выходе. При этом блок 2 проверяет возможность формирования очередного отличающегося от и редыдущих,марш рута.В том случае, если формирование маршрута возможно, блок 2 устанавливает (регистрирует) потенциалы уровня логической единицы на тех своих выходах признаков принадлежности дуг текущему маршруту, которые соответствуют очередному маршруту, соединяющему заданные начальную и конечную вершины графа при заданном наборе его дуг, и сохраняет потенциал уровня логического нуля на своем выходе признака исчерпания списка маршрутов,25 30 35 40 45 50 55Корректор Е.Папп Заказ 3386 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 Через время, достаточное для выполнения указанных операций, блок 1 синхронизации повторяет временную диаграммувыдачи сигналов на своих первом и второмвыходах. При этом работа устройства повторяется.В том случае, если формирование маршрута невозможно, блок 2 формирует импульс уровня логической единицы на своемвыходе признака исчерпания списка маршрутов, При этом блок 2 исключает маршрут,заданный по входам признаков принадлежности дуг исключаемому маршруту, из списка перечисляемых в последующих тактахего работы и возвращается в исходное состояние, при котором потенциалы уровнялогической единицы установлены на тех еговыходах признаков принадлежности дуг текущему маршруту, которые соответствуютдугам первого из маршрутов, соединяющихзаданные начальную и конечную вершиныграфа, блок 1 синхронизации увеличиваетна единицу текущее число перезапусков исравнивает его с заданным количествомциклов повторения работы.В том случае, если текущее число перезапусков превышает заданное, блок 1 синхронизации формирует сигнал уровнялогической единицы на своем выходе признака выполнения заданного количествациклов и прекращает выдачу импульсовсинхронизации на свои выходы, При этомработа устройства заканчивается,В том случае, если текущее число перезапусков не превышает заданное, блок 1синхронизации повторяет диаграмму выдачи сигналов на своих первом и втором выходах, предваряя ее одноразовой выдачейимпульса уровня логической единицы насвой третий выход. При этом блок 5 формирует адрес очередной ячейки регистрации.Формула изобретенияУстройство для решения задач на графах, содержащее блок синхронизации, регистрирующий блок перечислениямаршрутов, многоканальный блок регистрации, регистрирующий блок выбора экстремальной суммы и блок регистрации, причемвход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входурегистрирующего блока перечисления марСоставитель А.Редактор Т.Орловская Техред М,Морге 5 10 15 20 25 30 35 40 45 50 шрутов, выход признака принадлежности (К-М)-й дуги текущему маршруту которого (К = 1,2 В, М = 1, 2 В, где В - количество вершин в графе) подключен к (К,М)-му разряду первого информационного входа блока регистрации и к входу опроса (К,М)-го канала многоканального блока регистрации, информационный выход (К,М)-го канала которого подключен к входу (К,М)-го слагаемого регистрирующего блока выбора экстремальной суммы, выход признака наличия экстремума которого подключен к входу признака записи блока регистрации, а второй выход блока синхронизации - к тактовому входу регистрирующего блока выбора экстремальной суммы, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания), вход задания режима сортировки устройства подключен к входу выбора типа экстремума регистрирующего блока выбора экстремальной суммы, выход текущего значения суммы которого подключен к второму информационному входу блока регистрации, (К,М)-й разряд информационного выхода которого подключен к входу признака принадлежности (К,М)-й дуги исключаемому маршруту регистрирующего блока перечисления маршрутов, выход признака исчерпания списка маршрутов которого подключен к своему входу признака исключения маршрута и к входу повторного пуска блока синхронизации, третий выход которого подключен к входу признака смены адреса блока регистрации, вход начальной установки которого соединен с входом начальной установки, регистрирующего блока перечисления маршрутов и является входом начальной установки устройства, входы задания начальной вершины пути, конечной вершины пути и признака наличия (К,М)-й дуги которого подключены к одноименным входам регистрирующего блока перечисления маршрутов, вход задания количества сортируемых путей устройства подключен к входу задания числа повторений циклов работы блока синхронизации, выход признака выполнения заданного количества циклов которого является выходом признака окончания работы устоойства.