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

1

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

По основному авт. св. № 553628 кэ- j вестно устройство- Для определения кратча1 ших путей на графе, содержащее Две электронные граф-цепи, в каждой из кото ряых модели ветвей соединены между собой согласно топологии исследуемой се-20 ти, причем модели ветвей первой графцепи содержат соединенные последовательно переменный резистор и пороговый элемент , модели ветвей второй граф-иепи содержат соединенные последовательно элемент индикации и нор.1ально разсалкку- тые контакты порогового элемента соот ветствуюшей модели ветви первой гра4н цепи. Устройство также содержит рёгупвруолый источник напряжения, выводы кого рого подключаются к исследуемьад узловым точкам первой граф-цепи, источник тока и индикатор тока, которые, соединенные друг с другом . ПС следовательно, подключаются к исследуемым узловым точкам второй граф-цепи 1

Однако известное устройство предназва чено только для определения кратчайших путей между заданной парой узпав и не позволяет проводить анализ ветвей, вхо дяших в этот путь.

.

Цель взобретечия - расширеную . циональных возможностей устройства для определения кратчайших путей на графе за счет выявления ветви с наибольшим критерием резервирования в кpaтчaйш@vI |Пути. Поставленная цепь достигается тем, что в устройство введены формирователи одиночных сигналов, элементы И, усилители и дополнительные элементы индикации, управляющий выход порогового элемента каждой ветви через формирователь одиночных сигналов подключен к первому входу соответствующего элемента И, выход которого через усилитель соединен с входом дополнительного элемента индикаиии соответструющей ветви, выход индикатора тока через формирователь оданочного импульса подключен к .вторым входам всех элементов И. -На чертеже представлена функотональная схема устройства. На схеме показана первая граф-цепь АВСД N, вторая граф-цепь , эле-; мент 1 с регулируемым сопротивлением, пороговый элемент 2 ветви, нopv aльнo разомкнутый ключ 3, элемент 4 Индикации ветви, входящий в кратчайший путь, регулируемый источник 5 напряжения, источник б тока, индикатор 7 тока, нормально замкнутые контакты 8 индикатора тока, управляющее устройство 9., формирователь 10 .одиночного сигнала, элемент И 11, усилитель 12, дополнительный элемент 13 индикации. Устройство работает следующим обра ° - . В исходном состоянии величина выходного напряжения регулируемого источника 5 напряжения равна нулю. Все цепи обесточены, все ключи 3 разомкнуты, контакты 8 замкнуты. В элементах с регулируемым сопротивлением 1 устанавливают величины сопротивлений, соответствующие весовым коэффициентам соответ ствующих ветвей исследуемого графа. При этом соответствие между величиной сопротивления и весом ветви должно быть таким, чтобы увеличение сопроти&ления элемента 1 соответствовало уменьшешпо емкости ветви, уменьшению надежности, увеличению длины, стоимости и При плавном увеличении величины выходйого напряжения . ре1 улируемого источника 5 напряжения в моделях ветвей первой граф-цепи появляются токи, величина которых по отдельным ветвям определяет ся как топологией исследуемого графа, так и величинами сопротивлений элементов 1. По мере увеличения величины выходного напряжения величина тока в отдельных моделях ветвей первой граф-цепи досшгает значения Оср , где Зср- величи,яа тока срабатывания порогового элемен та 2. Соответствующие пороговые элементы 2 срабатывают, обеспечивая замыкание соответствующих им ключей 3 и подачу управляющего сигнала на входы соответствующих формирователей 1О одиночных импульсов, с выхода которых оди ночные импульсы поступают на входы элементов И 11. Однако пока замыкаюге ключей 3 не создаст замкнутую цепь для источника 6 тока, все элементы 4 индккации остаются выключенными, с обесточенного индикатора 7 тока не поступает управляющий сигнал на вторые входы элементов И 11, на выходах всех anw.teH-i тов И 11 отсутствует выходной сигнал, Как только срабатывает последний пороговый элеме.нт 2 модели 6, .в искомом кратчайшем Пути замыкание соответствующего ключа 3 образует для источника 6 тока замкнутую цепь. Протекание элекРрического тока источника 6 тока по моделям ветвей второй граф-цепи обеспечивает срабатывание соответствующих элементов 4 индикации, а следовательно, и индикацию искомого кратчайщего пути, и срабатывание индикатора 7 тока, который своими контактами разрывает цепь регулируемого источника 5 напряжения, предотвращая дальнейщее увеличение выходного . Сработавшие пороговые элемеиты 2 при этом остаются заблокирован - (блокировка на схеме не показана), индикатор 7 тока, сработав, подает управляющий сигнал на входы всех элементов И 11 управляющего устройст. ва 9. В это время на вход сЬответствук щего элемента И 11 с выхода формирователя 10 одиночных импульсов, соответ ствуК)Щего пороговому элементу 2, сработавшему последним, поступает одиночный импульс. Соответствующий элемент И 11 срабатывает и подает управляющий сигнал на вход соответствующего усилителя 12, последний обеспечивает срабатывание соответствующего элемента 13 индикации, Если под кратностью резервирования понимать отношение числа резервных элементов к общему числу резервируемых (рабочих) элементов объекта, то пороговый элемент, принадлежащий максимально резервируемой ветви, сработает при боль щей величине выходного напряжения регулируемого источника напряжения, т. е. последним. Следовательно, в устройстве сработает элемент 13 индикации, принадлежащий ветви с наибольщим критерием резервирования.