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

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

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

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

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

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

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

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

выдача списка блоком 1 и сбрасывается текущее прерывание.

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

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

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

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

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