Устройство для определения кратчайшего пути Советский патент 1986 года по МПК G06G7/122 

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

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

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

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

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

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

При подаче сигнала на вход запуска устройства импульсы генератора 1 через кон- такт 2 реле 14 поступают на вход распределителя 4, который поочередно выдает импульсы на свои выходы. Импульс, по- ступаюш,ий на S-вход триггера 6, перебрасывает его в единичное состояние, .единичный потенциал проходит через элемент ИЛИ 7 на управляющий вход соответствующего ключа 8, закрывая его и тем самым прерывая поступление одного из входных напряжений на соответствующий вход блока 9. На его выходах напряжения не изменяются до тех пор, пока очередной импульс распределителя 4 не обусловит отключение от входа блока 9 наибольшего напряжения U.-axc. Тогда на i-м выходе блока 9 исчезает положительное и появляется отрицательное напряжение. Этот перепад проходит через i-й элемент И 10, так как на первый вход этого элемента в это время поступает импульс с соответствующего выхода распределителя

5

0 ,. 5

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

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

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

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

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

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

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

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

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

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

Составитель Т. (Сапунова Те.хред И. ВепесКорректно Т. Колб

Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий

13035, Москва, Ж-35, Раушская наб., д. 4;5

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

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

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