Устройство для решения задач на графах
Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремального пути, в графе со взвешенными дугами. Устройство содержит блок 1 задания матрицы смежности, блок 2 синхронизации, блокЗ перечисления маршрутов, многоканальный блок 4 памяти, накапливающий блок 5 выбора экстремальной суммы, блок 6 регистрации, вход 7 пуска устройства, вход 8 задания режима работы, устройства, входы 9 задания начальной вершины пути устройства, входы 10 задания конечной вершины пути устройства, выходы 11 и 12 блока 2 синхронизации, выход 13 веса экстремального пути в графе устройства , выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы. После завершения начальных установок в устройстве на его вход 7 пуска подают импульс уровня логической Г. При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 14 устройства будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 - вес этого пути. 1 ил. « Ј
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)ю G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
6 (кн/
1 (21) 4663139/24 (22) 15.03.89 (46) 07.10.91. Бюл, 3Ф 37 (72) А.Ю.Лапин (53) 681.333(088.8) (56) Авторское свидетельство СССР
М 1501095, кл. G 06 F 15/20, 1988.
Авторское свидетельство СССР
ЬЬ 1596344, кл, G 06.F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ
НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремального пути, в графе со взвешенными дугами, Устройство содержит блок 1 задания матрицы смежности, блок 2 синхронизации, блок 3 перечисления маршрутов, многоканальный блок 4 памяти, „„Ы „„1683037 Al накапливающий блок 5 выбора экстремальной суммы, блок 6 регистрации. вход 7 пуска устройства, вход 8 задания режима работы. устройства, входы 9 задания начальной вер,.шины пути устройства, входы 10 задания конечной вершины пути устройства, выходы
11 и 12 блока 2 синхронизации, выход 13 веса экстремального пути в графе устройства, выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы. После завершения начальных установок в устройстве на его вход 7 пуска подают импульс уровня логической "1". При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 14 устройства будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 — вес этого пути. 1 ил.
1683037
Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе.
Целью изобретения является расширение функциональных возможностей устрой- 5 ства за счет определения экстремального пути в графе со взвешенными дугами.
На чертеже представлена функциональная схема устройства.
Устройство содержит блок 1 задания 10 матрицы смежности, блок 2 синхронизации, блок 3 перечисления маршрутов, многоканальный блок 4 памяти, накапливающий блок 5 выбора экстремальной суммы, блок 6 регистрации, вход 7 пуска устройства, вход 15
8 задания режима работы устройства, входы
9 задания начальной вершины пути устройства, входы 10 задания конечной вершины пути устройства, выходы 11 и 12 блока 2 синхронизации. выход 13 веса экстремаль- 20 ного пути в графе устройства, выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы.
Устройство работает следующим абра- 25
ЗОМ, Перед началом работы в блок 1 заносят информацию о топологии графа, обнуляют накапливающий блок 5, устанавливают блок
3 перечисления маршрутов в исходное со- 30 стояние, по входам 9 и 10 задают номера начАльной и конечной вершин пути, по входу 8 задают режим работы устройства )определение кратчайшего (вид экстремума— минимум) или длиннейшего(вид экстрему- 35 ма — максимум) пути), в каналы блока 4 памяти заносят значения весов соответствующих дуг.
На вход 7 пуска подают импульс уровня логической "1". При этом блок 2 синхрони- 40 зации формирует последовательность импульсов, предусмотренную временной диаграммой его работы. Блок 2 формирует импульс уровня логической ".1" на своем выходе 11, При этом блок 3 формирует потен- 45 циалы уровня логической "1" на тех своих выходах, номера которых соответствуют номерам дуг (ребер), входящим в состав маршрута из начальной в конечную вершину графа, При этом опрошенные каналы блока 50
4 памяти выдают на свои выходы занесенные в них значения (т.е, значения весов дуг, входящих в состав текущего пути). Через время, достаточное для выполнения указанных операций, блок 2 синхронизации фор- 55 мирует импульс уровня логической "1" на выходе 12. При этом блок 5 суммирует все значения, поступившие на его входы слагаемых, сравнивает полученную сумму со значением, полученным в предыдущем такте работы и при выполнении условия экстремума (больше или меньше) фиксирует текущее значение суммы и формирует импульс уровня логической "1" на выходе соответствующего признака. При этом блок 6 регистрации фиксирует поступившую на его вход информацию (состав дуг (ребер) пути, принятого в данном такте за экстремаль ный). Через время, достаточное для выполнения указанных операций, блок 2 синхронизации формирует импульс уровня логической "1" на своем выходе 11, после чего работа устройства повторяется. После того как блок 3 закончит перечисление всех возможных маршрутов, потенциалом уровня логической "1" с его соответствующего выхода блок 2 синхронизации останавливается. При этом на выходах 14 будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 — вес
ЭТОГО пУти.
Формула изобретения
Устройство для решения задач íà графах, содержащее блок задания матрицы смежности, блок регистрации, накапливающий блок выбора экстремальной суммы и блок синхронизации, вход пуска которого является входом пуска устройства, о т л ич а ю щ е е с я тем, что, с целью расширения его функциональных возможностей за счет определения экстремального пути в графе со взвешенными дугами, в него введены блок перечисления маршрутов и многоканальный блок памяти, причем выход значения (К,M)-го элемента блока задания матрицы смежности(К = 1, ..., В; M =1, ..., В, где  — количество вершин е графе) подключен к входу признака наличия (К,M)-й дуги блока перечисления маршрутов, выход признака окончания списка маршрутов которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, первый выход которого подключен к тактовому входу блока перечисления маршрутов,. выход признака принадлежности (К,M)-й дуги множеству дуг текущего маршрута которого подключен в (К,M)-му разряду информационного входа блока регистрации и к входу опроса (К,М=го канала многоканального блока памяти, информационный выход (К,М)-го канала которого подключен к входу (К,М)-.го слагаемого накапливающего блока выбора экстремальной суммы, выход признака наличия экстремума которого подключен к входу признака записи блока регистрации, (К,М)-й разряд информационного выхода которого является выходом признака принадлежности(К,М)-ой дуги экстремальному пути в графе устройства. K-й
1683037
Составитель А.Мишин
Редактор Т.Юрчикова Техред М.Моргентал Корректор С.Черни
Заказ 3415 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35. Раушская наб., 4/5
Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 вход задания начальной вершины пути которого подключен к одноименному входу блока перечисления маршрутов, второй выход блока синхронизации подключен к тактовому входу накапливающего блока выбора экстремальной суммы, информационный выход которого является выходом веса экстремального пути в графе устройства, М-й вход задания конечной вершины пути которого подключен к одноименному входу блока перечисления маршрутов, вход режи5 ма работы устройства подключен к входу выбора вида экстремума накапливающего блока выбора экстремальной суммы,
