Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/419 

VI

О

ел

00 СА) СО

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

Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания).

На чертеже представлена функциональная схема устройства.

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

На вход пуска устройства подают импульс уровня логической единицы. При этом

0 блок 1 синхронизации формирует на своих первом и втором выходах последовательность сигналов, предусмотренную временной диаграммой его работы.

Блок 1 формирует импульс уровня логи5 ческой единицы на своем втором выходе. При этом блок 4 вычисляет сумму всех поступивших на его входы слагаемых и сравнивает ее (сумму) со значением, зарегистрированным в одном из предыду0 щих тактов работы. В том случае, если по входу выбора типа экстремума установлен выбор максимума, и значение суммы, вычисленное в дан ном такте работы, больше зарегистрированного значения или, если по

5 входу выбора типа экстремума установлен выбор минимума и значение суммы, вычисленное в данном такте работы, меньше зарегистрированного значения, блок 4 регистрирует вычисленное значение суммы

0 (заменяет на него значение, зарегистрированное в предыдущих тактах работы), выдает его на свой выход текущего значения суммы и формирует импульс уровня логической единицы на своем выходе признака

5 наличия экстремума. При этом блок 5 регистрирует по текущему адресу значения, установленные на его информационных входах, и выдает на свой информационный выход значение, поступившее по первому

0 информационному входу (вес длиннейшего, кратчайшего из всех перечисленных ранее путей),

Через время, достаточное для выполнения указанных операций, блок 1 синхрони5 зации формирует импульс уровня логической единицы на своем первом выходе. При этом блок 2 проверяет возможность формирования очередного отличающегося от предыдущих.маршрута.

0 В том случае, если формирование маршрута возможно, блок 2 устанавливает (регистрирует) потенциалы уровня логической единицы на тех своих выходах признаков принадлежности дуг текущему маршруту,

5 которые соответствуют очередному маршруту, соединяющему заданные начальную и конечную вершины графа при заданном наборе его дуг, и сохраняет потенциал уровня логического нуля на своем выходе признака исчерпания списка маршрутов.

Через время, достаточное для выполнения указанных операций, блок 1 синхронизации повторяет временную диаграмму выдачи сигналов на своих первом и втором выходах. При этом работа устройства повто- ряется.

В том случае, если формирование маршрута невозможно, блок 2 формирует импульс уровня логической единицы на своем выходе признака исчерпания списка марш- рутов. При этом блок 2 исключает маршрут, заданный по входам признаков принадлежности дуг исключаемому маршруту, из списка перечисляемых в последующих тактах его работы и возвращается в исходное со- стояние, при котором потенциалы уровня логической единицы установлены на тех его выходах признаков принадлежности дуг текущему маршруту, которые соответствуют дугам первого из маршрутов, соединяющих заданные начальную и конечную вершины графа, блок 1 синхронизации увеличивает на единицу текущее число перезапусков и сравнивает его с заданным количеством циклов повторения работы.

В том случае, если текущее число перезапусков превышает заданное, блок 1 синхронизации формирует сигнал уровня логической единицы на своем выходе признака выполнения заданного количества циклов и прекращает выдачу импульсов синхронизации на свои выходы, При этом работа устройства заканчивается.

В том случае, если текущее число перезапусков не превышает заданное, блок 1 синхронизации повторяет диаграмму выдачи сигналов на своих первом и втором выходах, предваряя ее одноразовой выдачей импульса уровня логической единицы на свой третий выход. При этом блок 5 форми- рует адрес очередной ячейки регистрации.

Формула изобретения

Устройство для решения задач на графах, содержащее блок синхронизации, регистрирующий блок перечисления маршрутов, многоканальный блок регистрации, регистрирующий блок выбора экстремальной суммы и блок регистрации, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход ко- торого подключен к тактовому входу регистрирующего блока перечисления марСоставитель А. Редактор Т.ОрловскаяТехред М.Морг

шрутов, выход признака принадлежности (КМ)-й дуги текущему маршруту которого (К

1,2В, М 1, 2В, где В - количество

вершин в графе) подключен к (К,М)-му разряду первого информационного входа блока регистрации и к входу опроса (К.М)-го канала многоканального блока регистрации, ин- формационный выход (К,М)-го канала которого подключен к входу (К,М)-го слагаемого регистрирующего блока выбора экстремальной суммы, выход признака наличия экстремума которого подключен к входу признака записи блока регистрации, а второй выход блока синхронизации - к тактовому входу регистрирующего блока выбора экстремальной суммы, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания), вход задания режима сортировки устройства подключен к входу выбора типа экстремума регистрирующего блока выбора экстремальной суммы, выход текущего значения суммы которого подключен к второму информационному входу блока регистрации, (К,М)-й разряд информационного выхода которого подключен к входу признака принадлежности (К,М)-й дуги исключаемому маршруту регистрирующего блока перечисления маршрутов, выход признака исчерпания списка маршрутов которого подключен к своему входу признака исключения маршрута и к входу повторного пуска блока син- хронизации, третий выход которого подключен к входу признака смены адреса блока регистрации, вход начальной установки которого соединен с входом начальной установки, регистрирующего блока перечисления маршрутов и является входом начальной установки устройства, входы задания начальной вершины пути, конечной вершины пути и признака наличия (К,М)-й дуги которого подключены к одноименным входам регистрирующего блока перечисления маршрутов, вход задания количества сортируемых путей устройства подключен к входу задания числа повторений циклов работы блока синхронизации, выход признака выполнения заданного количества циклов которого является выходом признака окончания работы устройства.

Корректор Е.Папп

Изобретение относится к области вычислительной техники и может быть исполь- зовано для анализа экстремальных (кратчайших и/или длиннейших) путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет сортировки экстремальных путей в графе в порядке их возрастания (убывания). Устройство содержит блок 1 синхронизации, регистрирующий блок 2 перечисления маршрутов, многоканальный блок 3 регистрации, регистрирующий блок 4 выбора экстремальной суммы, блок 5 регистрации, вход 6 пуска устройства, выход 7 признака окончания работы устройства, вход 8 задания количества сортируемых путей устройства, вход 9 задания начальной вершины пути устройства, вход 10 задания конечной вершины пути устройства, входы 11признаков наличия дуг устройства, вход 12начальной установки устройства, входы 13задания веса дуг устройства и вход 14 задания режима сортировки. Пусть необходимо определить в порядке убывания (возрастания) их веса несколько длиннейших (кратчайших) путей в графе между заданной парой вершин. Перед началом работы по входам 8, ..., 14 задают необходимые для работы исходные данные. На вход пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой в последовательно расположенных ячейках блока 5 регистрации фиксируются сортируемые пути. 1 ил. (/ С