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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 119) 111) 042 4 6 06 Г 15 20 г а,4 ПИСАНИЕ ИЗОБРЕТЕНИЯ ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ(57) Изобретение относится к вычислительной технике и может быть использовано для решения на графах задач нахождения маршрутов минимальной длины, максимальной пропускной способности, минимальной стоимости. Изобретение позволяет повысить точность определения кратчайшего пути за счет идентификации образующих его ветвей с большей. Это достигается за счет проверки высвеченных ветвей на принадлежность кратчайшему маршруту, а в случае наличия циклов, либо двух и более кратчайших маршрутов единичное состояние триггера 21 дает пользователю информацию о необходимости дальнейшего анализа полученного результата. Устройство для определения кратчайшего пути содержит генератор импульсов, размыкающий контакт, реле, выключатель, распределитель 4 импульсов, группу переключающих контактов, две группы триггеров, группу элементов ИЛИ, группу ключей, блок выбора максимума, две группы элементов И, модели ветвей, источник тока, реле индикации, контрольное реле, замыкающий контакт, два элемента ИЛИ, эле- Я мент задержки и триггер. Каждая модель ветви содержит ключ и элемент индикации. 1 ил.Устройство работает следующим образом, При подаче сигнала на вход запуска устройства импульсы генератора 1 через контакт 2 реле 14 поступают на вход распределителя 4, который поочередно выдает импульсы на свои выходы. Импульс, поступающий на 8-вход триггера 6, перебрасывает его в единичное состояние, .единичный потенциал проходит через элемент ИЛИ 7 на управляющий вход соответствующего ключа 8, закрывая его и тем самым прерывая поступление одного из входных напряжений на соответствующий вход блока 9. На его выходах напряжения не изменяются до тех пор, пока очередной импульс распределителя 4 не обусловит отключение от входа блока 9 наибольшего напряжения .),нана, Тогда на 1-м выходе блока 9 исчезает положительное и появляется отрицательное напряжение. Этот перепад проходит через 1-й элемент И 10, так как на первый вход этого элемента в это время поступает импульс с соответствующего выхода распределителя 40 45 50 55 Изобретение относится к вычислительнойтехнике и может быть использовано для решения на графах задач нахождения маршрутов минимальной длины, максимальной пропускной способности, минимальной стоимости.Цель изобретения - повышение точности определения кратчайшего пути.На чертеже изображена функциональнаясхема устройства для определения кратчайшего пути,1 ОУстройство содержит генератор 1 импульсов, размыкающий контакт 2 реле, выключатель 3, распределитель 4 импульсов, группу переключающих контактов 5, первую группу триггеров 6, группу элементов ИЛИ 7,группу ключей 8, блок 9 выбора максиму 15ма, первую группу элементов И 10, вторуюгруппу триггеров 11, модели ветвей 12, источник 13 тока, реле индикации 14, контрольное реле 15, замыкающий контакт 16,реле, первый элемент ИЛИ 1, второй элемент ИЛИ 18, вторую группу элементов И9,группу элементов 20 задержки и триггер 21.Каждая модель 12 ветви содержит ключ 22и элемент 23 индикации.Первоначально на информационные входы устройства подают постоянные напряжения А, 1= 1, гп (гп - число ветвей графа), триггеры 6, 11, 21 устанавливают в нулевое состояние, при котором ключи 8 открыты, а ключи 22 закрыты. Предположим, чтовеса ветвей соответствуют их пропускнойспособности так, что кратчайший путь будетявляться маршрутом наибольшей пропускнойспособности. Если на 1-м информационномвходе действует наибольшее, по сравнениюс остальными, положительное напряжениеАнак., то на всех од блока 9, .кроме 1-го, присутствует отрицательное, а на1-м выходе - положительное напряжение,4 и перебрасывает соответствующий триггер 1 в единичное состояние.В результате замыкается соответствующий ключ 22, подключая ветвь в топологию графа, единичный потенциал, поступая через элемент ИЛИ 7, закрывает соответствующий ключ 8, этим прекращается подаЧа НаПРЯжЕНИЯ Анаис На СоотВЕтетВуЮЩИй вход блока 9. Единичный сигнал, пройдя через элемент ИЛИ 17, возвращает в исходное нулевое состояние те триггеры 6, которые перешли до того в единичное состояние. Тем самым все ключи 8, кроме 1-го, открываются, и блок 9 выбирает наибольшее напряжение среди оставшихся входных напряжений, в результате положительное напряжение появляется уже на другом выходе блока 9.Далее очередной импульс распределителя 4 перебрасывает в единичное состояние соответствующий триггер 6, и работа уст. ройства проходит аналогично. Наконец, после перехода в единичное состояние какогото триггера 11 и обусловленного этим открывания соответствующего ключа 22 образуется цепь для тока источника3, в результате чего загораются элементы 23 ветвей кратчайшего пути, а в результате срабатывания реле 14 размыкается контакт 2, прекращая поступление импульсов генератора 1 на вход распределителя 4, а подвижные контакты группы 5 переключающих контактов замыкаются с вторыми неподвижными контактами, отключая выходы распределителя 4 от Я-входов триггеров 6 я подключая их к вторым входам элементов И 19. При срабатывании реле 15 замыкается контакт 16.Однако горящие элементы 23 правильно индицируют ветви кратчайшего маршрута, если эти ветви не образуют цикл или не принадлежат двум или более кратчайшим маршрутам; в противном случае высвечивается ложная информация о принадлежности ветвей единственному кратчайшему маршруту. Например, в графе с 5 вершинами, связанными ветвями (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), причем вес ветви (4, 5) наименьший, ток через модели ветвей 2 потечет лишь после подключения в топологию графа всех ветвей. Соответственно будут индицированы все ветви как принадлежащие единственному кратчайшему маршруту, в то время как Они принадлежат двум маршрутам: ( 1, 2), (2, 4), (4. 5) и (1, 3) . (3, 4), (4, 5).Для повышения точности высвеченной информации о ветвях кратчайшего пути замыкают выключатель 3 на небольшое время, однако достаточное для завершения хотя бы одного цикла работы распределителя 4, который под воздействием импульсов генера. тора 1 начинает выдавать импульсы поочередно на свои выходы. Каждый импульс через соответствующий контак 5 поступает1256042 30 Формула изобретения Составитель Т. Са нова Редактор С.1 атр и ва Техред И. Верее Корректор Т. Колб Заказ 4825 49 Тираж 6 Т 1 Подниснос ВНИИПИ Государственного комитета СССР ио делам изобретений и открытий 113035, Москва, Ж - 35, Рауиская наб., д. 45 Филиал ППГ Патент, г. Ужгород, ул Проектная, 4на второй вход соответствующего элемента И 19, однако проходит на его выход лишь в случае, если соответствующий триггер 11 находится в единичном состоянии. В этом случае импульс поступает на К-вход триггера 11 и перебрасывает его в нулевое состояние, что обуславливает закрытие ключа 22 соответствующей модели ветви 12.Если при этом цепь протекания тока разорвется, то реле 14 остается в прежнем положении, поскольку оно с самоблокиров- О кой, а реле 15 отпускает, вследствие чего контакт 16 размыкается, поэтому импульс с вьхода элемента 20 задержки через него не прохоЛит, а поступает на второй Я-вход триггера 11, возвращая его в прежнее единичное состояние, обуславливающее откры тие соответствующего ключа 22. Снова замыкается цепь протекания тока, реле 15 срабатывает и замыкает контакт 16.Если же переход какого-то триггера 11 в нулевое состояние и закрытие соответствующего ключа 22 не приводят к размыканию цепи протекания тока, что возможно при наличии цикла или двух и более кратчайших маршрутов, то реле 15 не отпускает, контакт 16 остается замкнутым, и с выхода элемента 20 задержки импульс через элемент 25 ИЛИ 18 и контакт 16 проходит на единичный вход триггера 21, единичное состояние которого свидетельствует о том, что индицированные ветви не принадлежат единственному кратчайшему пути. Устройство для определения кратчайшего пути, содержа 1 цее источник тока, реле индикации и группу моделей ветвей графа, 35 каждая модель ветви содержит элемент индикации, выход которого является выходом модели ветви графа группы, все модели ветвей графа группы соединены между собой в соответствии с топологией исследуемого графа, вход источника тока соелинен с выхо 40 дом начальной ветви графа, а выход - с первым выводом обмотки реле индикации, отличающееся тем, что, с целью повышения точности, в него введены генератор импульсов, выключатель, распределитель импульсов, 45 первая и вторая группы триггеров, группа элементов ИЛИ, группа ключей, первая и вторая группы элементов И, два элемента ИЛИ, группа элементов задержки, блок вь 1 бора максимума, контрольное реле и триггер,в каждую модель ветви введен ключ, выход которого подключен к входу элемента индикации, информационные входы ключей молелей ветвей графа группы являются информационными входами моделей ветвей графа группы, а управляющие входы ключей управляющими входами моделей ветвей графа группы, информационные входы всех моделей ветвей графа группы являются установочными входами устройства, вход генератора импульсов является входом запуска устройства, выход генератора импульсов через размыкающий контакт, реле индикации соединен с входом распределителя импульсов, выходы которого через контакты группы реле индикации подключены к первым входам соответствующих элементов И первой группы и к входам установки в 1 соответствующих триггеров первой группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ группы, выходы которых подключены к управляющим входам соответствующих моделей ветвей графа группы, выходы ключей группы соединены с соответствующими входами блока выбора максимума, каждый из выходов которого подключен к второму входу соответствующего элемента И первой группы, выход каждого из элементов И первой группы подключен к первому входу установки в 1 соответствующего триггера второй группы, выходы триггеров второй группы соединены с вторыми входами соответствующих элементов ИЛИ группы, соответствующими входами первого элемента ИЛИ, первыми входами соответствующих элементов И второй группы и управляющими входами ключей соответствующих моделей ветвей графа группы, первый вывод обмотки контрольного реле подключен к выходу конечной модели ветви графа группы, а второй вывод обмоткик второму выводу обмотки реле индикации, выходы элементов И второй группы соединены с входами установки в О, а через элементы задержки - с вторыми входами установки в 1 соответствующих триггеров второй группы, выход первого элемента ИЛИ подключен к входам установки в О триггеров первой группы, выходы элементов задержки соединены соответственно с входами второго элемента ИЛИ, выход которого через замыкающий контакт контрольного реле подключен к входу установки в 1 триггера, выход генератора импульсов через выключатель подключен к входу распределителя импульсов.