Устройство для определения экстремальных маршрутов Советский патент 1985 года по МПК G06F15/173 

Изобретение относится к вычислительной технике, в частности к решению задач поиска маршрутов минимального или максимального веса (минимальной стоимости, максимальной пропускной способности и т.п.) на графах без циклов. Цель изобретения состоит в расширении функциональных возможностей путем нахождения двух и более экстремальных маршрутов одинаковог веса. На чертеже представлена функциональная схема устройства. Устройство содержит группу размыкающих контактов 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, 52,...,5h и на время действия импульсов откр ваются ключи 10, 10,..., Юп. 85Л Переход триггера в нулевое состояние обуславливает закрытие ключа 2 и тем самым, отключение напряжения и- от i-ro входа блока 8. При выдаче распределителем к-го импульса от входа блока 8 отключается максимальное напряжение U. Вследствие этого напряжение на к-м выходе блока 8 скачком становится отрицательным, отрицательный импульс, образовавшийся после прохождения перепада напряжэния через дифференцирующий информационный вход ключа Юк, поступает на выход ключа lOj. и вызывает, во-первых, срабатывание реле 1U, которое замыкает контакт 19к и тем самым подключает к-е ребро в топологию графа, а также размыкает контакт 1), отключая напряжение U)( от входа блока 8, во-вторых, импульс с выхода ключа 10| поступает через элемент ИЛИ 9 на S-входы триггеров 5, переводя те из них, которые находились в нулевом состоянии, в единичное состояние. Все ключи 2 открываются, обеспечивая подачу входных напряжений, кроме напряжения U, на входы блока 8. Дальнейшая работа устройства проходит аналогично, обуславливая подключение в топологию графа все большего числа ребер. Наконец, после срабатывания реле 10: и замыкания контакта 19; в модели j-ro ребра образуется цепь протекания тока. В случае замыкания цепи протекания тока между начальной и конечной вершинами графа зажегшиеся элементы 18 индикации идентифицируют маршрут одинаковой пропускной способности с ранее найденным маршру том. Поскольку среди неподключенных ребер ни одно не имеет большую пропускную способность по сравнению с пропускной способностью подключенных в топологию графа ребер, то зажегшиеся элементы 18 индикации идентифицируют маршрут максимальной пропускной способности. При этом срабатывает реле 15, размыкая контакт 7 и тем самым исключая прохождение импульсов на вход распределителя 6, а также замыкая контакты 13 и обеспечивая прохождение импульса с выхода ключа 10j через элемент 12j задержки на элемент 14j индикации, указывающий

3

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

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

3685

параторы 3 срабатывают и выдают сигналы на одноименные элементы 4 индикации, которые идентифицируют ребра одинаковой пропускной способности с J-M ребром. Тогда отключают генератор импульсов от входа запуска устройства, а в модели ребер 17 отключат модель j-ro ребра, вследствие чего разрывается цепь 10 протекания тока между начальной и конечной вершинами графа и гаснут элементы 18 индикации ранее найденного маршрута максимальной пропускной способности. Затем поочередно подключают модели ребер одинако15

вой пропускной способности с J-M ребром,

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