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

 

Изобретение относится к вычислительной технике и может быть использовано для решения на графах задач нахождения маршрутов минимальной длины, максимальной пропускной способности, минимальной стоимости. Изобретение позволяет повысить точность определения кратчайшего пути за счет идентификации образуюш,их его ветвей с большей. Это достигается за счет проверки высвеченных ветвей на принадлежность кратчайшему маршруту, а в случае наличия циклов, либо двух и более кратчайших маршрутов единичное состояние триггера 21 дает пользователю информацию о необходимости дальнейшего анализа полученного результата. Устройство для определения кратчайшего пути содержит генератор импульсов, размыкающий контакт, реле, выключатель, распределитель 4 импульсов, группу переключающих контактов, две группы триггеров, группу элементов ИЛИ, группу ключей, блок выбора максимум а, две группы элементов И, модели ветвей, источник тока, реле индикации, контрольное реле, замыкающий контакт, два элемента ИЛИ, элемент задержки и триггер. Каждая модель ветви содержит ключ и элемент индикации . 1 ил. с (Л to ел О) о 4 ю

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

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

РЕСПУБЛИК

„„SU„„1256042 А 1 (58 4 G 06 Г 15 20

1 ( 1

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

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3861123/24-24 (22) 21.02.85 (46) 07.09.86. Бюл. № 33 (72) В. В, Райский и В. В. Сергеев (53) 681.333(088.8) (56) Авторское свидетельство СССР № 417802, кл. G 06 G 7/48, 1972.

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

КРАТЧАЙШЕГО ПУТИ (57) Изобретение относится к вычислительной технике и может быть использовано для решения на графах задач нахождения маршрутов минимальной длины, максимальной пропускной способности, минимальной стоимости. Изобретение позволяет повысить точность определения кратчайшего пути за счет идентификации образующих его ветвей с большей. Это достигается за счет проверки высвеченных ветвей на принадлежность кратчайшему маршруту, а в случае наличия циклов, либо двух и более кратчайших маршрутов единичное состояние триггера 21 дает пользователю информацию о необходимости дальнейшего анализа полученного результата. Устройство для определения кратчайшего пути содержит генератор импульсов, размыкающий контакт, реле, выключатель, распределитель 4 импульсов, группу переключающих контактов, две группы триггеров, группу элементов ИЛИ, группу ключей, блок выбора максимума, две группы элементов И, модели ветвей, источник тока, реле индикации, контрольное реле, замыкающий контакт, два элемента ИЛИ, элемент задержки и триггер. Каждая модель ветви содержит ключ и элемент индикации. 1 ил.

1256042

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

При подаче сигнала на вход запуска устройства импульсы генератора 1 через контакт 2 реле 14 поступают на вход распределителя 4, который поочередно выдает импульсы на свои выходы. Импульс, поступающий íà S-вход триггера 6, перебрасывает его в единичное состояние, .единичный потенциал проходит через элемент ИЛИ

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

На его выходах напряжения не изменяются до тех пор, пока очередной импульс распределителя 4 не обусловит отключение от входа блока 9 наибольшего напряжения U„---«.

Тогда на i-м выходе блока 9 исчезает положительное и появляется отрицательное напряжение. Этот перепад проходит через 1-й элемент И 10, так как на первый вход этого элемента в это время поступает импульс с соответствующего выхода распределителя

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

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

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

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

Каждая модель 12 ветви содержит ключ 22 и элемент 23 индикации.

Первоначально на информационные входы устройства подают постоянные напря- 25 жения U;, i = 1, m (m — число ветвей графа), триггеры 6, 11, 21 устанавливают в нулевое состояние, при котором ключи 8 открыты, а ключи 22 закрыты. Предположим, что веса ветвей соответствуют их пропускной способности так, что кратчайший путь будет являться маршрутом наибольшей пропускной способности. Если на i-м информационном входе действует наибольшее, по сравнению с остальными, положительное напряжение

U;Maze, то на Всех выходах блока 9, .кроме i-го, присутствует отрицательное, а на

i-м выходе — положительное напряжение.

4 и перебрасывает соответствующий триггер 11 в единичное состояние.

В результате замыкается соответствующий ключ 22, подключая ветвь в топологию графа, единичный потенциал, поступая через элемент ИЛИ 7, закрывает соответствующий ключ 8, этим прекращается подача напряжения 14-- на соответствующий вход блока 9. Единичный сигнал, пройдя через элемент ИЛИ 17, возвращает в исходное нулевое состояние те триггеры 6, которые перешли до того в единичное состояние. Тем самым все ключи 8, кроме i-го, открываются, и блок 9 выбирает наибольшее напряжение среди оставшихся входных напряжений, в результате положительное напряжение появляется уже на другом выходе бл ока 9.

Далее очередной импульс распределителя 4 перебрасывает в единичное состояние соответствующий триггер 6, и работа устройства проходит аналогично. Наконец, после перехода в единичное состояние какогото триггера 11 и обусловленного этим открывания соответствующего ключа 22 образуется цепь для тока источника 13, в результате чего загораются элементы 23 ветвей кратчайшего пути, а в результате срабатывания реле 14 размыкается контакт 2, прекращая поступление импульсов генератора 1 на вход распределителя 4, а подвижные контакты группы 5 переключающих контактов замыкаются с вторыми неподвижными контактами, отключая выходы распределителя 4 от S-входов триггеров 6 и подключая их к вторым входам элементов И 19. При срабатывании реле 15 замыкается контакт

16.

Однако горящие элементы 23 правильно индицируют ветви кратчайшего маршрута, если эти ветви не образуют цикл или не принадлежат двум или более кратчайшим маршрутам; в противном случае высвечивается ложная информация о принадлежности ветвей единственному кратчайшему маршруту. Например, в графе с 5 вершинами, связанными ветвями (1, 2), (l, 3), (2, 4). (3, 4), (4, 5), причем вес ветви (4, 5) наименьший, ток через модели ветвей 12 потечет лишь после подключения в топологию графа всех ветвей. Соответственно будут индицированы все ветви как принадлежащие единственному кратчайшему маршруту, в то время как они принадлежат двум маршрутам: (i, 2), (2, 4), (4. 5) и (1, 3). (3, 4), (4, 5).

Для повышения точности высвеченной информации о ветвях кратчайшего пути замыкают выключатель 3 на небольшое время, однако достаточное для завершения хотя бы одного цикла работы распределителя 4, который под воздействием импульсов генератора 1 начинает выдавать импульсы поочередно на свои выходы. Каждый импульс через соответствующий контак 5 поступает!

256042

Зо

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

Составители T. Сап нова

Редактор С. П пр и< ва Техред И. Верее Корректор T. Колб

Заказ 4825 49 Тираж 671 П од|и«н« <ВНИИПИ Государственного комитета СССР но делам изобретений и открытий

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

Филиал ППП «Патент». г. Ужгород, ул Проектная, 4 на второй вход соответствующего элемента И 19, однако проходит на его выход лишь в случае, если соответствующий триггер 11 находится в единичном состоянии. В этом случае импульс поступает на R-вход триггера 11 и перебрасывает его в нулевое состояние, что обуславливает закрытие ключа 22 соответствующей модели ветви 12.

Если при этом цепь протекания тока разорвется, то реле 14 остается в прежнем положении, поскольку оно с самоблокиров- 10 кой, а реле 15 отпускает, вследствие чего контакт 16 размыкается, поэтому импульс с выхода элемента 20 задержки через него не проходит, а поступает на второй S-вход триггера 11, возвращая его в прежнее единичное состояние, обуславливающее открытие соответствующего ключа 22. Снова замыкается цепь протекания тока, реле 15 срабатывает и замыкает контакт 16.

Если же переход какого-то триггера 11 в нулевое состояние и закрытие соответствующего ключа 22 не приводят к размыканию цепи протекания тока, что возможно при наличии цикла или двух и более кратчайших маршрутов, то реле 15 не отпускает, контакт 16 остается замкнутым, и с выхода элемента 20 задержки импульс через элемент

ИЛИ 18 и контакт 16 проходит на единичный вход триггера 21, единичное состояние которого свидетельствует о том, что индицированные ветви не принадлежат единственному кратчайшему пути.

Устройство для определения кратчайшего пути, содержа1цее источник тока, реле индикации и группу моделей ветвей графа, 35 каждая модель ветви содержит элемент индикации, выход которого является выходом модели ветви графа группы, все модели ветвей графа группы соединены между собой в соответствии с топологией исследуемого графа, вход источника тока соединен с выхо40 дом начальной ветви графа, а выход — с первым выводом обмотки реле индикации, отличающееся тем, что, с целью повышения точности, в него введены генератор импульсов, выключатель, распределитель импульсов, 45 первая и вторая группы триггеров, группа элементов ИЛИ, группа ключей, первая и вторая группы элементов И, два элемента

ИЛИ, группа элементов задержки, блок выбора максимума, контрольное реле и триггер, в каждую модель ветви введен ключ, выход которого подключен к входу элемента индикации, информационные входы ключей моделей ветвей графа группы являются информационными входами моделей ветвей графа группы, а управляющие входы ключей управляющими входами моделей ветвей графа группы, информационные входы всех моделей ветвей графа группы являются установочными входами устройства, вход генератора импульсов является входом запуска устройства, выход генератора импульсов через размыкающий контакт, реле индикации соединен с входом распределителя импульсов, выходы которого через контакты группы реле индикации подключены к первым входам соответствующих элементов И первой группы и к входам установки в «!» соответствующих триггеров первой группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых подключены к управляющим входам соответствующих моделей ветвей графа группы, выходы ключей группы соединены с соответствующими входами блока выбора максимума, каждый из выходов которого подключен к второму входу соответствующего элемента И первой группы, выход каждого из элементов И первой группы подключен к первому входу установки в «!» соответствующего триггера второй группы, выходы триггеров второй группы соединены с вторыми входами соответствующих элементов ИЛИ группы, соответствующими входами первого элемента ИЛИ, первыми входами соответствующих элементов И второй группы и управляющими входами ключей соответствующих моделей ветвей графа группы, первый вывод обмотки контрольного реле подключен к выходу конечной модели ветви графа группы, а второй вывод обмотки -- к второму выводу обмотки реле индикации. выходы элементов И второй группы соединены с входами установки в «О», а через элементы задержки — с вторыми входами установки в «1» соответствующих триггеров второй группы, выход первого элемента ИЛИ подключен к входам установки в «О» триггеров первой группы, выходы элементов задержки соединены соответственно с входами второго элемента ИЛИ, выход которого через замыкающий контакт контрольного реле подключен к входу установки в

«!» триггера, выход генератора импульсов через выключатель подключен к входу распределителя импульсов.