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

 

Изобретение относится к области аналоговой вычислительной техники, может быть использовано для решения задач поиска оптимальных путей на графе и позволяет находить кратчайшие пути, независимые по вершинам и ребрам. В устройство входят два источника 1 и 2 регулируемого напряжения, основные модели 3 ребер графа, дополнительные модели 4 ребер графа и модели 5 вершин графа. В каждой модели 3 имеется пороговый элемент 6, элемент 7 индикации и обмотка 8 реле. Модель 5 содержит включенные последовательно контакты 9 реле моделей 3 тех ребер графа, которые выходят из данной вершины . Пороговый элемент может быть выполнен , например, на базе тиристора 10, переменного резистора 11 и источника 12 постоянного напряжения. В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помош,ью переменных резисторов 1 I в моделях 3 и 4 устанавливают веса ребер графа. При плавном увеличении выходного напряжения источника 1 происходит переключение тиристоров 10 тех моделей 3, через которые проходит первый кратчайший путь, отображаемый элементами 7 индикации . Ток протекающий по обмоткам 8 моделей 3 кратчайшего пути, размыкает соответствующие контакты 9. Тем самым из топологии графа исключаются все модели 5 первого кратчайшего пути. Далее плавно увеличивают выходное напряжение источника 2, и аналогично находят второй кратчайший путь на графе. 1 ил. о (Л со со О5 О N

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

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

РЕСПУБЛИК

„„5U „„1336041 (so 4 G 06 G 7/122

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4049184/24-24 (22) 07.04.86 (46) 07.09.87. Бюл. № ЗЗ (72) В. А. Клишин, А. А. Лелис и Г. С. Полищук (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 913398, кл. G 06 G 7/122, 1979.

Авторское свидетельство СССР № 8514!8, кл. G 06 G 07/122,,1979. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ДВУХ НЕЗАВИСИМЫХ КРАТЧАЙШИХ

ПУТЕЙ НА ГРАФЕ (57) Изобретение относится к области аналоговой вычислительной техники, может быть использовано для решения задач поиска оптимальных путей на графе и позволяет находить кратчайшие пути, кезависимые по вершинам и ребрам. В устройство входят два источника 1 и 2 регулируемого напряжения, основные модели 3 ребер графа, дополнительные модели 4 ребер графа и модели 5 вершин графа. В каждой модели 3 имеется пороговый элемент 6, элемент 7 индикации и обмотка 8 реле. Модель 5 содержит включенные последовательно контакты 9 реле моделей 3 тех ребер графа, которые выходят из данной вершины. Пороговый элемент может быть выполнен, например, на базе тиристора 10, переменного резистора 11 и источника 12 постоянного напряжения. В исходном состоянии напряжение на выходе источников 1 и 2 равно кулю. С помощью переменных резисторов 11 в моделях 3 и 4 устанавливают веса ребер графа. При плавном увеличении выходного напряжения источника 1 происходит переключение тиристоров 10 тех моделей 3, через которые проходит первый кратчайший путь, отображаемый элементами 7 индикации. Ток протекающий по обмоткам 8 моделей 3 кратчайшего пути, размыкает соответствующие контакты 9. Тем самым из топологии графа исключаются все модели

5 первого кратчайшего пути. Далее плавно увеличивают выходное напряжение источника 2, и аналогично находят второй кратчайший путь на графе. 1 ил.

1336041

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

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

Редактор С. Г!атрушева Техред И. Верес Корректор С. Черни

За к аз 3805/46 Тираж 672 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

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

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

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

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

В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помощью переменных резисторов 11 в моделях 3 и 4 ребер устанавливают токи в управляющих цепях тиристоров 10, соответству1ощие заданным напряжениям их переключения, пропорциональным весам ребер.

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

Далее плавно увеличивают выходное напряжение источника 2, и при некоторой его величине во второй модели графа происходит подключение тиристоров 10 моделей 4, принадлежащих второму кратчайшему пути.

По этим моделям 4 протекает ток, благодаря чему элементы 7 индикации отображают второй кратчайший путь. Дальнейшее увеличение напряжения источника 2 не производится.

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