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

 

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремального пути, в графе со взвешенными дугами. Устройство содержит блок 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 ма работы устройства подключен к входу выбора вида экстремума накапливающего блока выбора экстремальной суммы,

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

 

Похожие патенты:

Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами

Изобретение относится к вычислительной технике и может быть использовано для выполнения математических операций над частями графа

Изобретение относится к вычислительной технике и может быть использовано для анализа надежности систем, описываемых графами

Изобретение относится к вычислительной технике и технике связи и может быть использовано при проектировании устройств обработки данных и построении уз лов коммутации на сетях передачи дискретной информации

Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов

Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов

Изобретение относится к вычислительной технике и может быть использовано для анализа баз знаний и решения задач логического вывода

Изобретение относится к вычислительной технике и предназначено для обработки трехмерных сцен и является усовершенствованием изобретения по авт.св

Изобретение относится к вычислительной технике и может быть использовано для анализа стратегий матричной игры

Изобретение относится к технологическим средствам, обеспечивающим автоматизацию процесса трассировки соединений в интегральных схемах и печатных платах

Изобретение относится к вычислительной технике и может быть использовано для определения состава и веса критических путей в орграфе без петель

Изобретение относится к вычислительной технике и может быть использовано для исследования параметров систем, описываемых графами

Изобретение относится к вычислительной технике и может быть использовано при моделировании посредством сетей Петри

Изобретение относится к вычислительной технике и может быть использовано при разработке автоматизированных систем управления различными процессами и большими системами

Изобретение относится к области электротехники, в частности к матричным коммутаторам, и может быть использовано в системах управления и наблюдения

Изобретение относится к области вычислительной техники и может быть использовано для построения коммутационных средств мультипроцессорных вычислительных и управляющих систем

Изобретение относится к вычислительной технике и может быть использовано при построении средств коммутации мультипроцессорных систем

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта

Изобретение относится к вычислительной технике и может быть использовано для оценки состояния объекта по нескольким параметрам при нечетком задании степени принадлежности возможных параметров заданному состоянию объекта
Наверх