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

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ МАРШРУТОВ, содержащее реле, группу реле, источник тока, подключенный через обмотку реле к начальной и конечной вершинам графа , модели ребер, соединенные согласно топологии графа, причем каждая модель ребра состоит из последовательно соединенных элемента индикации и замыкающего контакта соответствующего реле группы, отличающееся тем, что, с целью расширения функциональных возможностей путем нахождения двух и более экстремальных маршрутов одинакового веса, в устройство введены две группы ключейJ группа компараторов ,- две группы элементов индикации группа триггеров, распределитель импульсов, блок выделения максимального напряжения , элемент ШТЧ и группа элементов задержки, причем первые входы компараторов группы соединены с первыми выводами размыкающих контактов одноименных реле группы и являются информационными входами устройства, вторые входы компараторов соединены и являются входом задания веса эталонного ребра устройства , выходы компараторов подключены к входам одноименных элементов индикации первой группы, вторые выводы размыкающих контактов реле группы соединены с информационными входами одноименных ключей первой группы, выходы и управляющие входы которых подключены соответственно к одноименным входам блока . вьщеления максимального напряжения и выходам одноименных триггеров группы, R-входы которых соединены с I одноименными выходами распределителя импульсов, вход которого под (Л ключен к первому выводу размыкающего контакта реле, второй вьгеод ко .торого является входом запуска устройства, выходы блока вьщеления максимального.напряжения соединены с информационными входами одноименных ключей второй группы, управляющие входы которых подключены к одноименным входам распределителя импульсов , входы элемента ИЛИ соедисо нены с обмотками одноименных реле со группы и входами одноименных эле0д 00 ментов задержки группы и подключены к выходам одноименных ключей второй сд группы, S-входы триггеров группы соединены и подключены к выходу .элемента ИЛИ, выходы элементов задержки группы через одноименные замыкающие контакты реле группы соединены с входами одноименных элементов индикации второй группы.

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

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

РЕСПУБЛИК (19) (и) д1) 4 С 06 Г 15/20

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

fO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ВСЕСОН)ЗНАЯ и, (21) 3743192/24-24 (22) 17.05 ° 84 (46) 23.11.85. Бюл. Ф 43 (72) Г.С. Колесник (53) 681.33 (088.8) (56) Авторское свидетельство СССР

Р 851418, кл. G. 06 G 7/122, 1979.

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

Ф 553628, кл. С 06 С 7/122, 1975. (54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕМАЛЬНЫХ МАРШРУТОВ, содержащее реле, группу реле, источник тока,подключенный через обмотку реле к начальной и конечной вершинам графа, модели ребер, соединенные сог- ласно топологии графа, причем каждая модель ребра состоит из последовательно соединенных элемента индикации и замыкающего контакта соответствующего реле группы, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем нахождения двух и более экстремальных маршрутов одинакового веса, в устройство введены две группы ключей группа.компараторов,-две группы элементов индикации, группа триггеров, распределитель импульсов, блок выделения максимального напряжения, элемент ИЛЧ и группа элементов задержки, причем первые входы компараторов группы соединены с первыми выводами размыкающих контактов одноименных реле группы и являются информационными входами устройства, вторые входы компараторов соединены и являются входом задания веса эталонного ребра устройства, выходы компараторов подключены к входам одноименных элементов индикации первой группы, вторые выводы размыкающих контактов реле группы соединены с информационными входами одноименных ключей первой группы, выходы и управляющие входы которых подключены соответственно к одноименным входам блока .выделения максимального напряжения и выходам одноименных триггеров группы, -входы которых соединены с одноименными выходами распределителя импульсов, вход которого подключен к первому выводу размыкающего контакта реле, второй вывод ко.торого является входом запуска устройства, выходы блока выделения максимального. напряжения соединены с информационными входами одноименных ключей второй группы, управляющие входы которых подключены к одноименным входам распределителя импульсов, входы элемента ИЛИ соединены с обмотками одноименных реле группы и входами одноименных элементов задержки группы и подключены к выходам одноименных ключей второй группы, 5 -входы триггеров группы соединены и подключены к выходу ,элемента ИЛИ, выходы элементов задержки группы через одноименные замыкающие контакты реле группы соединены с входами одноименных элементов индикации второй группы.

1193685

55

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

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

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

Устройство содержит группу размыкающих контактов 1, первую группу ключей 2, группу компараторов 3, первую группу элементов 4 индикации, группу триггеров 5, "распределитель 6 импульсов, размыкающий контакт 7 реле, блок 8 выделения максимального напряжения, элемент ИЛИ 9, вторую группу ключей 10, группу реле 11, группу элементов 12 задержки, группу замыкающих контактов 13, вторую группу элементов 14 индикации, реле 15, источник 16 тока, модели ребер 17. Каждая модель ребра состоит из элемента 18 индикации и замыкающего контакта 19 соответствующего реле группы.

Работу устройства рассмотрим на нримере нахождения маршрутов максимальной пропускной способности.

Для приведения устройства в исходное положение триггеры 5 устанавливают в единичное состояние (цепи установки не показаны), на информационные входы устройства подают постоянные напряжения положительной полярности, воспроизводящие пропускную способность ребер графа. Эти напряжения через контакты 1 и открытые ключи 2 поступают на входы блока 8. Если среди входных напряжений наибольшим является приложенное к к-му входу напряжение U, то положительное напряжение присутствует на к-м, а отрицательное на остальных выходах блока 8.

Импульсы с входа запуска устройства через контакт 7 поступают на вход распределителя 6, который выда-, ет прямоугольные импульсы поочередно на первый, второй, и-й выходы, вследствие чего переходят в нулевое состояние триггеры 5, 5,...,5, и на время .действия импульсов открываются ключи 10, 10,..., 10д.

Переход триггера 5; в нулевое состояние обуславливает закрытие ключа 2 и тем самым, отключение напряжения

U от i-го входа блока 8. При выда1 че распределителем к-го импульса от входа блока 8 отключается максимальное напряжение U<. Вследствие этого напряжение на к-м выходе блока

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

11», которое замыкает контакт 19к и тем самым подключает к-е ребро в топологию графа, а также размыкает контакт 1, отключая напряжение U< от входа блока 8, во-вторых, импульс с выхода ключа 10 поступает через элемент ИЛИ 9 íà S-входы триггеров 5, переводя те из них, которые находились в нулевом состоянии, в единичное состояние. Все ключи 2 открываются, обеспечивая подачу входных напряжений, кроме напряжения 0„, на входы блока 8.

Дальнейшая работа устройства проходит аналогично, обуславливая подключение в топологию графа все большего числа ребер. Наконец, после срабатывания реле 10 и замыкания контакта 19 в модели j-ro ребра ,1 образуется цепь протекания тока. В случае замыкания цепи протекания тока между начальной и конечной вершинами графа зажегшиеся элементы 18 индикации идентифицируют .маршрут одинаковой пропускной способности с ранее найденным маршру» том.- Поскольку среди неподключенных ребер ни одно не имеет большую пропускную способность по сравнению с пропускной способностью подключенных в топологию графа ребер, то зажегшиеся элементы 18 индикации идентифицируют маршрут максимальной пропускной способности. При этом срабатывает реле 15, размыкая контакт 7 и тем самым исключая прохождение импульсов на вход распределителя 6, а также замыкая контакты 13 и обеспечивая прохождение импульса с выхода ключа 10 че—

3 рез элемент 121 задержки на элеФ мент 14 1 индикации, указывающий

1193685 4 параторы 3 срабатывают и выдают сигналы на одноименные элементы 4 индикации, которые идентифицируют ребра одинаковой пропускной способ5 ности с j-м ребром. Тогда отключают генератор импульсов от входа запуска устройства, а в модели ребер 17 отключат модель j-го ребра, вследствие чего разрывается цепь

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

< номер последнего (j ro) ребра, включенного в топологию графа.

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

ВНИИПИ Заказ 7317/53 Тираж 709 Подписное

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4