Устройство для решения задач на графах
Изобретение относится к области вычислительной техники и может быть использовано для анализа экстремальных (кратчайших и/или длиннейших) путей в графах . Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания). Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3 регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации , вход 6 пуска устройства, выход 7 признака окончания работы устройства, вход 8 задания количества сортируемых путей устройства, вход 9 задания начальной вершины пути устройства, вход 10 задания конечной вершины пути устройства, входы 11признаков наличия дуг устройства, вход 12начальной установки устройства, входы 13задания веса дуг устройства и вход 14 задания режима сортировки. Пусть необходимо определить в порядке убывания (возрастания ) их веса несколько длиннейших (кратчайших) путей в графе между заданной парой вершин. Перед началом работы по входам 8, ..., 14 задают необходимые для работы исходные данные. На вход пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой в последовательно расположенных ячейках блока 5 регистрации фиксируются сортируемые пути . 1 ил. (/ С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ, К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4757399/24 (22) 09.11.89 (46) 30.09.92. Бюл. ¹- 36 (72) А.Ю.Лапин (56) Авторское свидетельство СССР
¹ 1444830, кл, G 06 G 7/122, 1987.
Авторское свидетельство СССР
¹ 1683037, кл, G 06 F 15/419, 15.03.89. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
НА ГРАФАХ (57) Изобретение относится к области вычислительнбй техники и может быть использовано для анализа экстремальных (кратчайших и/илидлиннейших) путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания). Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3 регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации, вход 6 пуска устройства, выход 7
„, Я2„„1765833 А1 признака окончания работы устройства, вход 8 задания количества сортируемых путей устройства, вход 9 задания начальной вершины пути устройства, вход 10 задания конечной вершины пути устройства, входы
11 признаков наличия дуг устройства, вход
12 начальной установки устройства, входы
13 задания веса дуг устройства и вход 14 задания режима сортировки. Пусть необходимо определить в порядке убывания (возрастания) их веса несколько длиннейших (кратчайших) путей в графе между заданной парой вершин. Перед началом работы по входам 8, ..., 14 задают необходимые для работы исходные данные. На вход пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой в последовательно расположенных ячейках блока 5 регистрации фиксируются сортируемые пути. 1 ил.
1765833
Изобретение относится к области вычислительной техники и может быть использовано для анализа экстремальных (кратчайших и/или длиннейших) путей в графах.
Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания).
На чертеже представлена функциональная схема устройства.
Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3 регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации, вход 6 пуска устройства, выход 7 признака окончания работы устройства, вход 8 задания количества сортируемых путей устройства, вход 9 задания начальной вершины пути устройства, вход 10 задания конечной вершины пути устройства, входы
11 признаков наличия дуг устройства, вход
12 начальной установки устройства, входы
13 задания веса дуг устройства и вход 14 задания режима сортировки.
Устройство работает следующим образом.
Пусть необходимо определить в порядке убывания (возрастания) их веса несколько длиннейших (кратчайших) путей в графе между заданной парой вершин.
Перед началом работы по входам 9, 10, 11 устройства соответственно задают начальную, конечную вершины графа и его топологию. По входу 8 устройства задают значение количества сортируемых путей.
При этом блок 1 синхронизации фиксирует допустимое количество своих перезапусков (повторных пусков). По входам 13 устройства задают веса дуг графа. При этом каналы блока 3 регистрируют поданные на них значения (веса дуг). По входу 14 задают режим сортировки (возрастание/убывание), При этом блок 4 регистрирует максимально возможное (при выборе минимума) или минимально возможное (при выборе максимума) значение, которое в дальнейшем будет использоваться в качестве исходного значения при выполнении операции сравнения.
На вход начальной установки устройства подают импульс уровня логической единицы. При этом блок 2 устанавливает (регистрирует) потенциалы уровня логической единицы на тех своих выходах признаков принадлежности дуг текущему маршруту, которые соответствуют дугам первого из маршрутов, соединяющего заданные начальную и конечную вершины графа при
55 заданном наборе его дуг, блок 5 устанавливает адрес своей первой регистрирующей ячейки. Одновременно многоканальный блок 3 регистрации выдает на выходы опрошенных каналов установленные ранее значения (веса дуг, входящих в текущий маршрут), На вход пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих первом и втором выходах последовательность сигналов, предусмотренную временной диаграммой его работы.
Блок 1 формирует импульс уровня логической единицы на своем втором выходе.
При этом блок 4 вычисляет сумму всех поступивших на его входы слагаемых и сравнивает ее (сумму) со значением, зарегистрированным в одном из предыдущих тактов работы. В том случае, если по входу выбора типа экстремума установлен выбор максимума, и значение суммы, вычисленное в данном такте работы, больше зарегистрированного значения или, если по входу выбора типа экстремума установлен выбор минимума и значение суммы, вычисленное в данном такте работы, меньше зарегистрированного значения, блок 4 регистрирует вычисленное значение суммы (заменяет на него значение, зарегистриро- . ванное в предыдущих тактах работы), выдает его на свой выход текущего значения суммы и формирует импульс уровня логической единицы на своем выходе признака наличия экстремума. При этом блок 5 регистрирует по текущему адресу значения, установленные на его информационных входах, и выдает на свой информационный выход значение, поступившее по первому информационному входу (вес длиннейшего, кратчайшего из всех перечисленных ранее путей), Через время, достаточное для выполнения указанных операций, блок 1 синхронизации формирует импульс уровня логической единицы на своем первом выходе. При этом блок 2 проверяет возможность формирования очередного отличающегося от предыдущих, маршрута.
В том случае, если формирование маршрута возможно, блок 2 устанавливает (регистрирует) потенциалы уровня логической единицы на тех своих выходах признаков принадлежности дуг текущему маршруту, которые соответствуют очередному маршруту, соединяющему заданные начальную и конечную вершины графа при заданном наборе его дуг, и сохраняет потенциал уровня логического нуля на своем выходе признака исчерпания списка маршрутов, 1765833
Мишин нтал
Корректор Е.Папп
Заказ 3386 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101
Через время, достаточное для выполнения указанных операций, блок 1 синхронизации повторяет временную диаграмму выдачи сигналов на своих первом и втором выходах. При этом работа устройства повторяется.
В том случае, если формирование маршрута невозможно, блок 2 формирует импульс уровня логической единицы на своем выходе признака исчерпания списка маршрутов, При этом блок 2 исключает маршрут, заданный по входам признаков принадлежности дуг исключаемому маршруту, из списка перечисляемых в последующих тактах
его работы и возвращается в исходное состояние, при котором потенциалы уровня логической единицы установлены на тех его выходах признаков принадлежности дуг текущему маршруту, которые соответствуют дугам первого из маршрутов, соединяющих заданные начальную и конечную вершины графа, блок 1 синхронизации увеличивает на единицу текущее число перезапусков и сравнивает его с заданным количеством циклов повторения работы.
В том случае, если текущее число перезапусков превышает заданное, блок 1 синхронизации формирует сигнал уровня логической единицы на своем выходе признака выполнения заданного количества циклов и прекращает выдачу импульсов синхронизации на свои выходы, При этом работа устройства заканчивается.
В том случае. если текущее число перезапусков не превышает заданное, блок 1 синхронизации повторяет диаграмму выдачи сигналов на своих первом и втором выходах, предваряя ее одноразовой выдачей импульса уровня логической единицы на свой третий выход. При этом блок 5 формирует адрес очередной ячейки регистрации.
Формула изобретения
Устройство для решения задач на графах, содержащее блок синхронизации, регистрирующий блок перечисления маршрутов, многоканальный блок регистрации, регистрирующий блок выбора экстремальной суммы и блок регистрации, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу регистрирующего блока перечисления марСоставитель А.
Редактор Т.Орловская Техред M.Ìoðãå
50 шрутов, выход признака принадлежности (К-М)-й дуги текущему маршруту которого (К
= 1,2,..., В, М = 1, 2,..., В, где B — количество вершин в графе) подключен к (К,M)-му разряду первого информационного входа блока регистрации и к входу опроса (К,М)-го канала многоканального блока регистрации, информационный выход (К,M)-ro канала которого подключен к входу (К,M)-ro слагаемого регистрирующего блока выбора экстремальной суммы, выход признака наличия экстремума которого подключен к входу признака записи блока регистрации, а второй выход блока синхронизации — к тактовому входу регистрирующего блока выбора экстремальной суммы, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания), вход задания режима сортировки устройства подключен к входу выбора типа экстремума регистрирующего блока выбора экстремальной суммы, выход текущего значения суммы которого подключен к второму информационному входу блока регистрации, (К,М)-й разряд информационного выхода которого подключен к входу признака принадлежности (К, M)-й дуги искл ючаемому маршруту регистрирующего блока перечисления маршрутов, выход признака исчерпания списка маршрутов которого подключен к своему входу признака исключения маршрута и к входу повторного пуска блока синхронизации, третий выход которого подключен к входу признака смены адреса блока регистрации, вход начальной установки которого соединен с входом начальной установки, регистрирующего блока перечисления маршрутов и является входом начальной установки устройства, входы задания начальной вершины пути, конечной вершины пути и признака наличия (К,М)-й дуги которого подключены к одноименным входам регистрирующего блока перечисления маршрутов, вход задания количества сортируемых путей устройства подключен к входу задания числа повторений циклов работы блока синхронизации, выход признака выполнения заданного количества циклов которого является выходом признака окончания работы устройства.
