Устройство для определения экстремальных маршрутов

) (И) 20 Со ВСЕСОВЗ ОПИСАНИЕ ИЗОБРЕТЕНИЯ 13,Ь У СВИДЕТЕЛЬСТВ,85, Бюл. Ф 43 Колесник 3 (088.8) иены с входаминтов индикации одноименных элевторой группы. ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ орское свидетельство СССР5 1 , кл. С. 06 С 7/122, 1979.Авторское свидетельство СССР В 553628, кл. С Об С 7/122, 1975. (54)(57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ МАРШРУТОВ, содержащее реле, группу реле, источник тока,. подключенный через обмотку реле к начальной и конечной вершинам графа, модели ребер, соединенные сог- ласно топологии графа, причем каждая модель ребра состоит из последовательно соединенных элемента индикации и замыкающего контакта соответствующего реле группы, о т - л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем нахождения двух и более экстремальных маршрутов одинакового веса, в устройство введены две группы ключей группа.компараторов, две группы элементов индикации, группа триггеров, распределитель импульсов, блок выделения максимального напряжения, элемент ИЛЧ и группа элементов задержки, причем первые входы компараторов группы соединены с первыми выводами размыкающих контактов одноименных реле группы и являются информационными входами устройства, вторые входы компараторов соединеныи являются входомзадания веса эталонного ребра устройства, выходы компараторов подключены к входам одноименных элементов индикации первой группы, вторые выводы размыкающих контактов реле группы соединены с информационными входами одноименных ключей первой группы, выходы и управляющиевходы которых подключены соответственно к одноименным входам блокавыделения максимального напряженияи выходам одноименных триггеровгруппы,-входы которых соединены содноименными выходами распределителя импульсов, вход которого подключен к первому выводу размыкающего контакта реле, второй вывод ко.торого является входом запускаустройства, выходы блока выделениямаксимального, напряжения соединеныс информационными входами одноименных ключей второй группы, управляющие входы которых подключены к одноименным входам распределителя импульсов, входы элемента ИЛИ соединены с обмотками одноименных релегруппы и входами одноименных элементов задержки группы и подключенык выходам одноименных ключей второйгруппы, 5 -входы триггеров группысоединены и подключены к выходуэлемента ИЛИ, выходы элементов задержки группы через одноименныезамыкающие контакты реле группы сое 1193685Изобретение относится к вычислительной технике, в частности к решению задач поиска маршрутов минимального или максимального веса(минимальной стоимости, максимальной пропускной способности и т.п.)на графах без циклов,Цель изобретения состоит в расширении функциональных возможностей путем нахождения двух и болееэкстремальных маршрутов одинаковоговеса.На чертеже представлена функциональная схема устройства.Устройство содержит группу размыкающих контактов 1, первую группу ключей 2, группу компараторов 3,первую группу элементов 4 индикации, группу триггеров 5, "распределитель б импульсов, размыкающий контактреле, блок 8 выделения максимального напряжения, элемент ИЛИ 9,вторую группу ключей 10, группу реле 11, группу элементов 12 задержки, группу замыкающих контактов 13,вторую группу элементов 14 индикации, реле 15, источник 16 тока, модели ребер 17. Каждая модель ребрасостоит из элемента 18 индикации изамыкающего контакта 19 соответствующего реле группы.Работу устройства рассмотримна нримере нахождения маршрутовмаксимальной пропускной способности.Для приведения устройства в исходное положение триггеры 5 устанавливают в единичное состояние (цепи установки не показаны), на информационные входы устройства подаютпостоянные напряжения положительнойполярности, воспроизводящие пропускную способность ребер графа. Эти напряжения через контакты 1 и открытые ключи 2 поступают на входыблока 8. Если среди входных напряжений наибольшим является приложенное к к-му входу напряжение Б,то положительное напряжение присутствует на к-м, а отрицательное наостальных выходах блока 8.Импульсы с входа запуска устройства через контакт 7 поступают навход распределителя б, который выда-,ет прямоугольные импульсы поочередно на первый, второй, и-й выходы,вследствие чего переходят в нулевоесостояние триггеры 5, 55 ь,и на время .действия импульсов открываются ключи 10, 10 10 п.35 40 4550 55 10 15 20 25 30 Переход триггера 5; в нулевое состояние обуславливает закрытие ключа 2и тем самым, отключение напряженияЮ от -го входа блока 8. При выдаче распределителем к-го импульсаот входа блока 8 отключается максимальное напряжение Б. Вследствиеэтого напряжение на к-м выходе блока8 скачком становится отрицательным, отрицательный импульс, образовавшийся после прохождения перепада напряжения через дифференцирующийинформационный вход ключа 10 к, поступает на выход ключа 10 и вызывает, во-первых, срабатывание реле11, которое замыкает контакт 19 ки тем самым подключает к-е ребро втопологию графа, а также размыкаетконтакт 1, отключая напряжение 0от входа блока 8, во-вторых, импульс с выхода ключа 10 поступаетчерез элемент ИЛИ 9 на Б-входытриггеров 5, переводя те из них,которые находились в нулевом состоянии, в единичное состояние. Всеключи 2 открываются, обеспечивая подачу входных напряжений, кроменапряжения , на входы блока 8.Дальнейшая работа устройства проходит аналогично, обуславливая подключение в топологию графа все большего числа ребер, Наконец, после срабатывания реле 10 и замыкания контакта 19 в модели 3-го ребра,1образуется цепь протекания тока, В случае замыкания цепи протекания тока между начальной и конечной вершинами графа зажегшиеся элементы 18 индикации идентифицируют маршрут одинаковой пропускной способности с ранее найденным маршру том Поскольку среди неподключенных ребер ни одно не имеет большую пропускную способность по сравнению с пропускной способностью подключенных в топологию графа ребер, то зажегшиеся элементы 18 индикации идентифицируют маршрут максимальной пропускной способности, При этом срабатывает реле 15, размыкая контакт 7 и тем самым исключая прохождение импульсов на вход распределителя 6, а также замыкая контакты 13 и обеспечивая прохождение импульса с выхода ключа 10че -3 рез элемент 12 задержки на элемент 14 1 индикации, указывающий1193685 4параторы 3 срабатывают и выдаютсигналы на одноименные элементы 4индикации, которые идентифицируютребра одинаковой пропускной способ 5 ности с 3-м ребром, Тогда отключают генератор импульсов от входа запуска устройства, а в модели ребер 17 отключат модель 3-го ребра,вследствие чего разрывается цепь1 О протекания тока между начальной иконечной вершинами графа и гаснутэлементы 18 индикации ранее найденного маршрута максимальной пропускной способности. Затем поочередно подключают модели ребер одинаковой пропускной способности с 3-мребром. номер последнего (3-го) ребра, включенного в топологию графа.Среди ребер, не включенных в топологию графа, некоторые могут иметь пропускную способность, равную пропускной способности 3-го ребра. Чтобы определить, имеются ли другие маршруты одинаковой пропускной способности с найденным маршрутом, напряжение 11, воспроизводя- ф щее пропускную способность 1-го ребра,.подают через соответствующий вход устройства на вторые входы компараторов 3, При наличии на первых входах тех или иных компараторов 3 напряжений, равных по величине напряжению П , соответствующие ком,1л ППП "Патент", г.ужгород, ул.Проектная, 4 ф ВНИИПИ Заказ 7317/53 Тираж 709 Подписно