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

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

Иллюстрации

Показать все

Реферат

 

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

СОВХОЗ СОВЕТСКИХ сОциАпистических

РЕСПУБЛИК (51)5 G 06 Е15/419

ГОСУДДРСТВЕННЬ! Й КОМИТЕТ

t10 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4674990/24 (22) 13,02.89 (46) 07.02.91. Бгол, N". 5 (71) Институт проблел" регистрации информации АН УССР и Специальное констру;торско-технологическое бюро средств моделирования с опытным роизводством

Института проблем моделирования в энергетике АН УССР (72) А.Г, Додоноь. B.Ï, Прийма ук, H,iA. Cdсюк и А.М. Щети лин (53) 681.333(088. B) (56) АВТорсКое свидетельстве, СССР

М 1161951, кл. G 06 F 15/20, 1983.

Авторское свидетельство СССР

М 1437674, кл. 5 06 г 15/20, 1989. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и r: ожет быть использовано для исследования путей в графах со взвешенными дугами, Целью изобретения является расширение функциональных воэможностей устройства эа счет определения величины экстремального пути в графе.

Устройство содержит блок 1 списка заходя„„« А „„1626256 А1 щих дуг, блок 2 проверки параметров спика, блок 3 памяти меток свершения вершин, блок 4 задания списков исходящих дуг, многоканальный таймер 5, блок 6 синхронизации, вход — выход 7 номера исполненной вершины устройства, вход 8 начальной установки устройства, вход 9 пуска устройства, тактовый выход 10 устройства, выход 11 номера исполненной дуги устройства и вход 12 режима рабо гы устройства. Перед началом работы в блоки 1 и 4 в виде списков заносят

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

По входу 12 задают режим работы устройства (определение кратчайшего или длиннейшего пути), по входам 7, 8- номер начальной вершины пути. На вход 9 пуска устройства подают импульс уровня логической "1", При этом блок 6 синхронизации формирует на своем выходе и выходе 11 устройства последовательность тактовых импульсов, Количество импульсов до появления на выходе 7 устройства номера какой-либо вершины со-, ответствует величине экстремального пути из выбранной начальной вершины в данную вершину. 1 ил.

8 7

1626256

1О

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

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

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

Устройство содержит блок 1 заданиях списка заходящих дуг, блок 2 проверки параметров списка, блок 3 памяти меток свершения вершин, блок 4 задания списков исходящих дуг, многоканальный таймер 5, блок 6 синхронизации, вход — выход 7 номера испалненнои вершины устройства, вход, 8 начальной усгаиовки устройства, вход 9 пуска устройства, тактовый выход 10. устройства, Выход 11 номера исполненной дуги устройства и вход 12 режима работа устройства.

Устройство работает следующим образом.

Перед началом работы в блоки 1 и 4 в виде спискрВ заносят информацию о топологии графа (при этом номера списков соответствуют номерам вершин, а номера записей списков — номерам дуг графа), обнуляют ячейки блока 3 памяти меток свершения Вершин, каналы многоканального таймера 5 за. ружают весами соответствующих им дуг. По входу 12 задают режим работы устроиства (определение кратчайшего или длиннейшего пути). При этом блок 2 проверки параметров списка устанавливается в режим проверки наличия метки хотя бы у одной записи, списка (при определении кратчайшего пути) или у всех записей спижа (при определении длиннейшего пути в графе). На Вход 7 устройства подают номер начальной вершины пути, сопровождая его импульсом на Входе 8 начальной установки устройства При этом блок 4 выдает на свой

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

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

При этом таймер 5 сбрасывает текущее прерывание без приема нового списка рабочих каналов. Точно так же, при выборе из блока

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

1626256

Составитель А.Мишин

Техред М. Моргентал Корректор Т.Палий

Редактор И.Горная

Заказ 279 Тираж 405 Подписное

ВНИИПИ Государственного комитета Ilo изобретениям и открытиям при ГКНТ СССР

113035, Москва. Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 выдача списка блоком 1 и сбрасывается текущее. прерывание.

После того, как все прерывания таймера

5 обработаны, последний снимает потенциап уровня логической единицы со своего 5 входа признака отсутствия прерываний, При этом блок 6 синхронизации возобновляет выдачу тактовых импульсов, изменяя частоту следования которых можно изменять (масштабировать) время модулирова- 10 ния. Количество тактовых импульсов, поступившее на тактовый выход 10 устройства до появления ía его выходе,7 номера какой-либо вершины, при наличии сигнала уровня логической единицы на входе 8 уст- 15 ройства соответствует величине экстремального пути иэ выбранной начальной его вершины в данную вершину пути.

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

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

Риэации, причем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого является тактовым выходом устройства и подключен к тактовому входу многоканального таймера, выход признака 30 отсутствия прерываний которого подключен к входу разрешения работы блока синхронизации, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет определения 35 величины экстремального пути в графе, в него введен блок проверки параметров списка, причем выход выдачи записей списка блока задания списков исходящих дуг подключен к входу задания номера запускаемого канала многоканального таймера, выход номера переполнившегося канала которого является выходом номера исполненной дуги устройства и подключен к входу задания записи адресуемого списка блока задания списков заходящих дуг, выход номера списка которого является входом — выходом номера исполненной вершины устройства, и подключен к входу задания номера списка блока задания списков исходящих дуг v к адресному входу блока памяти меток свершения вершин, прямой информационный выход которого подключен к входу опроса прерываний многоканального таймера, к выходу признака отсутствия соответствия блока проверки параметров и к входу блокировки выдачи списка блока задания списков заходящих дуг, выход выдачи записей списка которого подключен к входу приема записей списка блока проверки параметров списка, выход признака соответствия параметров которого подключен к входу начальной установки устройства, к входу разрешения выдачи списка блока задания списков исходящих дуг и к входу установки в "1" блока памяти меток свершения вершин, инверсный информационный выход которого подключен к входу разрешения выдачи списка и к входу опроса блока проверки параметров списка, вход выбора параметров которого является входом режима работы устройства.