Устройство для определения кратчайшего пути на графе

(54) УСТРОЙСТВО ДЛЯ ОКРАТЧАЙШЕГО ПУТИ НА Г(57) Изобретение относится характеризующимся оп ми измерения, и может для определения кратч фе, Цель иэобретения - действия, Поставленна тем, что устройство со излучения, Н поляризат - число вершин исслед топриемников 3, блок 4 логии графа, Н ключей триггер 7, блок 8 выбора нала и аналого-цифров 9.2 ил,Е, Кудрявцев о СССР(ГОСПАТЕНТ СССР) И САНИЕ тическими средства- быть использовано айшего пути на граповышение быстроя цель достигается держит источник 1 оров 2, где Н=2 К, К- уемого графа, Н фоформирования топо, элемент ИЛИ 6, максимального сигой преобразовательИзобретение относится к области устройств, характеризующихся оптическими средствами измерения и может быть использовано для определения кратчайшего пути в графе,Цель изобретения - повышение быстродействия,На фиг,1 представлена электрическая структурная схема устройства, на фиг,2 - структурная схема узла топологии графа.Устройство для определения кратчайшего пути в графе(фиг,1) содержит источник1 1 излучения, группу 2 из й/где И=2, где 1 - число вершин моделируемого графа (поляризаторов, группу 3 из М фотоприемников, блок 4 формирования топологии графа, содержащий узлов топологии графа 4-1, группу 5 из 1 ч ключей, элемент ИЛИ б, триггер 7, блок 8 выбора максимального сигнала, аналого-цифровой преобразователь 9.Узел 4-1 топологии графа (фиг,2) блока 4 содержит первый узел 10 сопряжения оптических волноводов, узел 11 поворота плоскости поляризации луча и второй узел 12 сопряжения оптических волноводов,Устройство для определения кратчайшего пути в графе работает следующим образом,Перед началом его работы на управляющие входы узлов блока 4 топологии графа подаются потенциалы, приводящие к тому, что при прохождении светового луча через узел 4-1 топологии графа блока 4 происходит поворот плоскости поляризации луча на угол р= 2 , Поляризаторы 2 установлены так, что плоскость пропускания поляризатора 2-и группы повернула на уголи, Устройство запускается подачей импульса на его вход запуска. Триггер устанавливается в единичное состояние, источник излучения вырабатывает световой импульс поляризованного излучения с линейной поляризацией, который подается к первому информационному входу блока 4 формирования топологии графа.Поскольку распространение светового импульса происходит по всем оптическим волокнам, то на выходе блока 4 формирования топологии графа образуется поток импульсов. Первый из пришедших импульсов пройдет по узлам 4-т топологии графа блока 4, образующим кратчайший путь в графе, При этом угол поворота К плоскости поляризации пришедшего импульса равенМ2 ь 1=1 где М - множество узлов топологии графа,составляющих кратчайший путь в графе.10 35 триггер, блок выбора максимального сигнала, аналого-цифровой преобразователь и блок формирования топологии графа, содержащий К узлов топологии графа, при этом, вход запуска устройства подключен к 40 45 50 15 20 25 ЗО Пришедший импульс поступает на вход поляризаторов 2 руппы, Гри этом на выходе К-го поляризатора группы появляется световой сигнал максимальной интенсивности, который преобразуется соответствующим фотоприемником 3-К группы в электрический. Этот сигнал через открытые ключи 5 группы поступает на входы блока 8 выбора максимального сигнала и проходит на входы аналого-цифрового преобразователя 9. Этот же сигнал, пройдя через элемент ИЛИ 6, обнуляет триггер 7, который закрывает ключи 5 группы. Таким образом, через группу 5 ключей проходит только один сигнал, соответству 1 ощий первому зарегистрированному световому импульсу. Выделенный блоком 8 максимальный сигнал преобразуется в 1-разрядное двоичное число аналогоцифровым преобразователем 9. Единица в 1-м (1=1,) разряде полученного двоичного числа указывает на принадлежность 1-го узла кратчайшему пути в графе и, наоборот, если 1-й разряд равен нулю, то 1-й узел не входит в кратчайший путь.Формула изобретения Устройство для определения кратчайшего пути на графе, содержащее источник излучения, первый поляризатор и первый фотоприемник,отлича ющееся тем, что, с целью повышения быстродействия, оно содержит с второго по Н-й поляризаторы (где Н = 2; где К - число вершин моделик.руемого графа), с второго по Н-й фотоприемники, Н ключей, элемент ИЛИ,входу установки в "0" триггера и к входу включения источника излучения, выход которого подключен к первому информационному входу блока формирования топологии графа, выход блока формирования топологии графа подключен к входам поляризаторов с первого по Н-й выходы которых подключены соответственно к входам фотоприемников с первого по Н-й, выход а-го фотоприемника подключен к а-му входу элемента ИЛИ и к информационному входу а-го ключа, выход которого подключен к а-му входу блока выбора максимального сигнала, выход которого подключен к входу аналогоцифрового преобразователя, выходы которого подключены соответственно к выходам устройства, управляющие входы с первого по К-й которого подключены соответственно к управляющим входам блока формирования топологии графа, выход элемента ИЛИ подключен к входу установки в "0"1817102 Составитель Д,ДробахинТехред М,Моргентал Корректор О. Густи Редактор Т,Иванова Заказ 1723 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 триггера, выход которого подключен к управляющим входам ключей с первого по Н- й, при этом каждый узел топологии графа содержит первый и второй узлы сопряжения оптических волноводов и узел поворота плоскости поляризации луча, причем в каждом узле топологии графа его информационные входы подключены к входам первого узла сопряжения оптических волноводов,выход которого подключен к первому входу узла поворота плоскости поляризации луча, выход которого подключен к входу второго узла сопряжения оптических волноводов, 5 выходы которого подключены соответственно, к выходам узла топологии графа, управляющий вход которого подключен к второму входу узла поворота плоскости поляризации луча,10