Устройство для решения задач на графах — SU 1626256 (original) (raw)
(51)5 О 06 1" 15/4 ГОСУДАРСТВЕННЬ ЙПО ИЗОБРЕТЕНИЯМГ)РИ ГКНТ СССР КОМИТЕТИ ОТКРЫТИ ПИСАНИЕ ИЗОБРЕТЕНИЯ(54) УСТРОЙСТВО НА ГРАФАХ(57) Изобретение о ной технике и можс исследования путе ными дугами, Цель расширение функ стей устройства эа чины экстремал Устройство содерж РЕШЕНИЯ ЗА тносится к вычислительт быть использовано для и в графах со взвешеню изобретения является циондльных возможно- счет определения велиьного пути в графе. ит блок 1 списка заходя 1 с) К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Институт проблем регистрации информации АН УССР и Специальное констру;- торско-технологическое бюро средств моделирования с опытным 1 роизводством Института проблем моделирования в энергетике АН УССР(56) Авторское свидетельство СССР М 1161951, кл. С 06 Г 15/20, 1983.Авторское свидетельство СССР М 1437674, кл, й 06 г 15/20, 1989,щих дуг, блок 2 проверки параметров списка, блок 3 памяти меток свершения вершин, блок 4 задания списков исходящих дуг, многоканальный таймер 5, блок 6 синхронизации, вход - выход 7 номера исполненной вершины устройства, вход 8 начальной установки устройства, вход 9 пуска устройства, тактовый выход 10 устройства, выход 11 номера исполненной дуги устройства и вход 12 режима рабо гы устройства, Перед началом работы в блоки 1 и 4 в виде списков заносят информацию о топологии графа, обнуляют ячейки блока 3 памяти, каналы таймера 5 загружают весами соответствующих им дуг, По входу 12 задают режим работы устройства (определение кратчайшего или длиннейшего пути), по входам 7, 8- нол 1 ер начальной вершины пути, На вход 9 пуска устройства подают импульс уровня логической "1", При этом блок 6 синхронизации формирует на своем выходе и выходе 11 устройства последовательность тактовых импульсов, Количество импульсов до появления на выходе 7 устройства номера какой-либо вершины со-, ответствует величине экстремального пути из выбранной начальной вершины в данную вершину. 1 ил.8 75 1 О1520 Перед началом работы в блоки 1 и 4 ввиде спискре заносят информацию о топологии графа(при этом номера списков соответствуют номерам вершин, а номера записей списков - номерам дуг графа), обнуляют ячейки блока 3 памяти меток свершения Вершин, каналы многоканального таймера 5 загружают весами соответствующих им дуг. По входу 12 задают режим работы устроиства (определение кратчайшего или длиннейшего пути). При этом блок 2 проверки параметров списка устанавливается в режим проверки наличия метки хотя бы у однсй записи, списка (при определении кратчайшего пути) или у всех записей спиаа (при определении длиннейшего пути в графе). На Вход 7 устройства подают номер начальной вершины пути, сопровождая его импульсом на Входе 8 начальной установки устройства При этом блок 4 выдает на свой Выход записи Выбранного списка (номера ветвей, исходящих из выбранной, например начальной, Вершины графа), При этом многоканальный таймер 5 переводит перечисленные каналы В рабочее состояние(запускает каналы). Через время, достаточное для окончания указанных процессов, на вход 9 пуска устройства подают импульс уровня логической единицы. При этом блок 6 синхронизации вырабатывает на своем выходе последовательность тактовых импульсов. При этом те каналы таймера 5, которые переведены в рабочее состояние (запущены), начиняют счет импульсов (тем самым моделируются дуги, исходящие из достигнутой вершины графа, в данном слу 2530 35 40 4550 55 Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах со взвешенными дугами,Целью изобретения является расширение функциональных возможностей устройства за счет определения величины экстремального пути В графе,На чертеже представлена функциональная схема предлагаемого устройства.УстройстВо содержит блок 1 заданиях списка заходящих дуг, блок 2 проверки параметров списка, блок 3 памяти меток свершения вершин, блок 4 задания списковисходящих дуг, многоканальный таймер 5,блок 6 синхронизации, вход - выход 7 номера испалненнои вершины устройства, вход,8 начальной усГаиовки устройства, вход 9 пуска устройства, тактовый выход 10 устройства, Выход 11 номера исполненной дуги устройства и вход 12 режима работа устройства.Устройство работает следующим образом,чае начальной вершины пути). Через время, достаточное для переполнения одного или нескольких каналов, таймер 5 снимает потенциал уровня логической единицы со своего выхода отсутствия прерываний (переполнений). При этом блок 6 синхронизации приостанавливает выдачу тактовых импульсов. Кроме того, таймер 5 выдает на свой выход (и на выход 11 устройства) номер переполнившегося канала (номер исполненной дуги), При этом блок 1 задания списков заходящих дуг отмечает обращение к заданной записи списка и выдает на один из своих выходов номер списка, к которому относится заданная запись (записи списка соответствует номер дуги, моделирование которой закончено, а номеру списка - номер вершины, в которую заходит дуга). При этом блок 3 памяти по адресу (номеру) списка выдает в прямом и инверсном виде хранимое (однобитовое) слово (признак того, что данная вершина уже исполнена в предыдущих циклах работы устройства). При нулевом значении слова (достигнутая вершина еще не исполнена) блок 1 выдает на свой выход все записи выбранного списка. При этом блок 2 проверки параметров списка в зависимости от режима работы устройства проверяет наличие отметки (об исполнении) хотя бы одной записи (дуги) списка (при поиске кратчайшего пути) или у каждой записи списка (при поиске длиннейшего пути). При соответствии параметров списка установленному режиму работы блок 2 формирует сигнал уровня логической единицы на своем выходе, При этом блок 4 выдает на свой выход все записи по номеру выбранного списка (т.е., выдает номера дуг, исходящих из вершины, номер которой совпадает с номером списка). При этом соответствующие каналы таймера 5 переводятся в рабочее состояние, Одновременно в блоке 3 устанавливается в единицу признак свершения вершины, По признаку конца списка таймер 5 снимает текущее прерывание (номер текущей исполненной дуги) и формирует номер следующего переполнившегося канала (исполненной дуги), если он есть, В том случае, если параметры списка не соответствуют режиму работы устройства на выходе признака отсутствия соответствия блока 2 проверки параметров списка появляется импульс уровня логической единицы. При этом таймер 5 сбрасывает текущее прерывание без приема нового списка рабочих каналов. Точно так же, при выборе из блока 3 памяти единичного информационного слова (достигнутая вершина уже исполнена в предыдущих циклах работы) запрещается1626256 Составитель А.МишинТехред М. Моргентал Корректор Т.Палий Редактор И.Горная Заказ 279 Тираж 405 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 выдача списка блоком 1 и сбрасывается текущее прерывание.После того, как все прерывания таймера 5 обработаны, последний снимает потенциал уровня логической единицы со своего 5 входа признака отсутствия прерываний, При этом блок 6 синхронизации возобновляет выдачу тактовых импульсов, изменяя частоту следования которых можно изменять (масштабировать) время модулирова ния. Количество тактовых импульсов, поступившее на тактовый выход 10 устройства до появления на его выходе,7 номера какой-либо вершины, при наличии сигнала уровня логической единицы на входе 8 уст ройства соответствует величине экстремального пути иэ выбранной начальной его вершины в данную вершину пути. Формула изобретения 20 Устройство для решения задач на графах, содержащее блок задания списков заходящих дуг, блок памяти меток свершения вершин, блок задания списков исходящих дуг, многоканальный таймер и блок синхро Риэации, причем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого является тактовым выходом устройства и подключен к тактовому входу многоканального таймера, выход признака 30 отсутствия прерываний которого подключен к входу разрешения работы блока синхронизации, отличающееся тем,что, с целью расширения функциональных воэможностей устройства за счет определения 35 величины экстремального пути в графе, в него введен блок проверки параметров списка, причем выход выдачи записей списка блока задания списков исходящих дуг подключен к входу задания номера запускаемого канала многоканального таймера, выход номера переполнившегося канала которого является выходом номера исполненной дуги устройства и подключен к входу задания записи адресуемого списка блока задания списков заходящих дуг, выход номера списка которого является входом - выходом номера исполненной вершины устройства, и подключен к входу задания номера списка блока задания списков исходящих дуг и к адресному входу блока памяти меток свершения вершин, прямой информационный выход которого подключен к входу опроса прерываний многоканального таймера, к выходу признака отсутствия соответствия блока проверки параметров и к входу блокировки выдачи списка блока задания списков заходящих дуг, выход выдачи записей списка которого подключен к входу приема записей списка блока проверки параметров списка, выход признака соответствия параметров которого подключен к входу начальной установки устройства, к входу разрешения выдачи списка блока задания списков исходящих дуг и к входу установки в "1" блока памяти меток свершения вершин, инверсный информационный выход которого подключен к входу разрешения выдачи списка и к входу опроса блока проверки параметров списка, вход выбора параметров которого является входом режима работы устройства,