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

 

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

СОЮЭ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (s»s G 06 F 15/20

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР3

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4787521/24 (22) 30.01,90 (46) 23.05.93, Бюл. ¹ 19 (72) Д,О.Дробахин, Ю.Е,Кудрявцев и

А.Г.Шевчик (56) Авторское свидетельство СССР

¹ 1259281, кл. G 06 F 15/20, 1986.

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

N- 872954, кл, G 01 В 11/02, 1981, (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ НА ГРАФЕ (57) Изобретение относится к устройствам, . Ы 1817102 А1 характеризующимся оптическими средствами измерения, и может быть использовано для определения кратчайшего пути на графе. Цель изобретения — повышение быстродействия. Поставленная цель достигается тем, что устройство содержит источник 1 излучения, Н поляризаторов 2, где Н= 2К, К— число вершин исследуемого графа, Н фотоприемников 3, блок 4 формирования топологии графа, Н ключей 5, элемент ИЛИ 6, триггер 7, блок 8 выбора максимального сигнала и аналого-цифровой преобразователь

9.2ил, 0î с

О

181 10

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

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

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

1 излучения, группу 2 из N/räå N=2, где i— число вершин моделируемого графа (поляризаторов, группу 3 из N фотоприемников, блок 4 формирования топологии графа, содержащий i узлов топологии графа 4-I, группу 5 из Nключей,,элемент ИЛИ 6, триггер 7, блок 8 выбора максимального сигнала, аналого-цифровой преобразователь 9.

Узел 4-i топологии графа (фиг,2) блока 4 содержит первый узел 10 сопряжения оптических волноводов, узел 11 поворота плоскости поляризации луча и второй узел 12 сопряжения оптических волноводов.

Устройство для определения кратчайшего пути в графе работает следующим образом, Перед началом его работы на управляющие входы узлов блока 4 топологии графа подаются потенциалы, приводящие к тому, что при прохождении светового луча через узел 4-i топологии графа блока 4 происходит поворот плоскости поляризации луча на угол р= 2, Поляризаторы 2 установлены так, что плоскость пропускания поляризатора 2-и группы повернула на угол Q= n, Устройство запускается подачей импульса на его вход запуска. Триггер устанавливается в единичное состояние, источник излучения вырабатывает световой импульс поляризованного излучения с линейной поляризацией, который подается к первому информационному входу блока 4 формирования топологии графа.

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

При этом угол поворота К плоскости поляризации пришедшего импульса равен

y —.g 2

i=1 где M — множество узлов топологии графа, составляющих кратчайший путь в графе.

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

45

Пришедший импульс поступает на вход поляризаторов 7 группы. Г!ри этом на выходе

К-го поляризатора группы появляется светоRoA сигнал максимальной интенсивности, который преобразуется соответствующим фотоприемником 3-К группы в электрический. Этот сигнал через открытые ключи 5 группы поступает на входы блока 8 выбора максимального сигнала и проходит на входы аналого-цифрового преобразователя 9.

Этот же сигнал, пройдя через элемент ИЛИ

6, обнуляет триггер 7, который закрывает ключи 5 группы. Таким образом, через группу 5 ключей проходит только один сигнал, соответству1ощий первому зарегистрированному световому импульсу. Выделенный блоком 8 максимальный сигнал преобразуется в I-разрядное двоичное число аналогоцифровым преобразователем 9. Единица в

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

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

Устройство для определения кратчайшего пути на графе, содержащее источник излучения, первый поляризатор и первый фотоприемник, о тл и ча ю щее с я тем, что, с целью повышения быстродействия, оно содержит с второго по Н-й поляризаторы (где Н = 2; где К вЂ” число вершин моделик. руемого графа), с второго по Н-й фотоприемники, Н ключей, элемент ИЛИ, входу установки в "0" триггера и к входу включения источника излучения, выход которого подключен к первому информационному входу блока формирования топологии графа, выход блока формирования топологии графа подключен к входам поляризаторов с первого по Н-й выходы которых подключены соответственно к входам фотоприемников с первого по Н-й, выход а-го фотоприемника подключен к а-му входу элемента ИЛИ и к информационному входу а-го ключа, выход которого подключен к а-му входу блока выбора максимального сигнала, выход которого подключен к входу аналогоцифрового преобразователя, выходы которого подключены соответственно к выходам устройства, управляющие входы с первого по К-й которого подключены соответственно к управляющим входам блока формирования топологии графа, выход элемента

ИЛИ подклю«ен к входу установки в "0"

1817102

Составитель Д,Дробахин

Техред M,Ìîðãåíòàë Корректор О. Густи

Редактор Т,Иванова

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

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

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

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