Устройство для поиска независимых кратчайших путей на графе,не имеющем параллельных участков Советский патент 1984 года по МПК G06G7/122 

Изобретение относится к устройствам электронного моделирования и может быть использова1}о при автомати зации управления потоками информации в сетях связи, потоками транспорта на дорогах, управления структурой йнформационйых сетей, а также при исследовании свойств сложнрраз- ветвленных графов. Известны устройства для нахождения кра чайших путей на графе, содер жащие в качестве моделей ветвей сети пороговые элементы - газоразрядные лампы, стабилитроны, тиристоры ij . Однако применение таких устройств для моделирования больших сетей за|труднено ввиду сложности схемы и длительного времени определения множества независимых путей на графе. Наиболее близким к- изобретению по технической сущности является уст ройство для определения двух неэависимых кратчайших путей на графе, не имеющем параллельных участков, содер жащее регулируемый источник напряжения, основную и первую дополнительную граф-цепи, образюущих две топологии исследуемой сети, каждая ветвь основной граф-цепи состоит из после:довательно соединенных порогового ;. ;элемента и переменного резистора, а каждая ветвь первой дополнительной граф-цепи состоит из последовательно соединенных элемента индикации, перв го- нормально разомкнутого контакта соответствующего порогового элемента основной граф-цепи и порогового элемента, к начальному и конечному узт лам первой дополнительной граф-цепи подключены последовательно соединенные источник тока и индикатор тока« Кроме того, устройство содержит вторую основную граф-цепь и вторую дополнительную граф-цепь {я} . . . , Устройство, построенное ПО такой схеме, позволяет определять два независимых кратчайших пути в автома тическом режиме.. Однако для поиска множества независимых путей на графе необходимо вручн1 ю выполнить последовательно несколько операций, что приводит к существенному увеличению затрат времени. Создание устройства для поиска множеств кратчайщих путей на гра фе известногоустройства приводит к значительному усложнению схемы, так как для поиска двух путей предложено создавать два аналогичных устройстваj для поиска трех и более путей (без i выполнения дополнительных операций) потребуется соответственно три и более аналогичных устройств. Кроме того, устройство обладает погрешностью в определении второго кратчайшего пути, так как переключение регулируемого источника напряжения, из исследуемых узлов первой основной граф-цепи в исследуемые узлы второй основной граф-цепи происходит, когда его напряжение отлично от нуля, и в момент переключения реактивные сопротивления пороговых элементов (электромагнитных реле) оказьшают существенное влияние на исход решения задачи поиска кратчайшего пути. Цель изобретения - расширение функциональньк возможностей устройства за счет одновременного поиска N независимых кратчайших путей на графе. Поставленная цель достигается тем, что в устройство для поиска независимых кратчайших путей на графе, не имеющем параллельных участков, содержащее регулируемый источзшк напряжения и основную и первую дололнИтельную граф-цепи,/образующие две топологии исследуемой сети, каждая ветвь основной граф-цепи состоит из последовательно соединенных порогового элемента, выполнейного в виде реле, и токозадающёго переменного резистора, а каждая ветвь первой дополнительной граф-цепи состоит из Последовательно соединенных элемента индикации, первого нормально разомкнутого контакта соответствующего реле бсновмой граф-цепи И порогового элемента, вьтолненного в виде реле, к начальному и конечному узлам первой дополнительной граф-цепи подключены последовательно соединенные источник тока и йндикато р тока, введены (N -1) дополнительных граф-цепей, идентичных первой дополнительной граф-цепи, (N -1) индикаторов тока и (Ц 0 источников тока, в кажДую ветвь основной граф-цепи последовательно с токозадакнцим перемен.ным резистором подключены последовательно соединенные N нормально замкнутых контактов реле соответствуюtpcx ветвей дополнительных граф-цепей. в каждой ветви которых параллельно первому нормально разомкнутому контакту подключен второй нормально разомкнутьй контакт реле, входящего в эту ветвь, к начальному и конечному узлам V -и (,...,N) дополнительной граф-цепи подключены последовательно соединенныеисточник тока, индикатор тока и нормально, разомкнутый контакт индикатора тока (| -1)-й дополнительной граф-цепи, к начальному и конечному узлам основ ной граф-цепи подключены последовательно соединенные регулируемый источник напряжения и нормально замкну тый контакт индикатора тока N -и дополнительной граф-цепи. На чертеже показана принципиальная электрическая схема предлагаемого устройства для поиска независиме кр атчайших путей на графе, не имеющем параллельных участков. Устройство содержит основную граф цепь 1, первую дополнительную графцепь 2, N -1 дополнительных графцепей 3 и 4/ ветвь основной .гр1аф-цепи 1 состоит из порогового элемента 5, вьтолненного в виде ре-, лё, токбзадающего переменного резис ра 6, нормально замкнутых контактов соответствующих реле 10-12, Каждая ветвь первой дополнительной граф цепи 2 состоит из порогового элемента 10, индикационного элемента 13, . нормально разЬмкнуто о контакта 14, реле 10 и нормально разомкнутого ,кон такта 15 реле 5J каждая ветвь графцепи 3 состоит из порогового элемент 11, вьтолненного в виде реле индикационного элемента 16, нормально разомкнутого контакта 17 реле 11 и . нормально разомкнутого контакта 18 реле 5, каждая ветвь граф-цепи 4 состоит из порогового элемента 12, индикационного элемента 19, нормально разомкнутого контакта 20 реле 12 и нормально разомкнутого контакта 2 реле 5. Кроме того, устройство содер жит регулируемый источник 22 напряжения, нормально разомкнутый контакт 23, индикатор 24 тока, источник 25 тока, индикатор 26 тока, источник 27тока, индикатор 8 тока, нормально разомкнутый контакт 29, индикатор тока 26, источник 30 тока, нормально разомкнутый контакт 31 индикатора 28тока. . 354 Устройство работает следующим бразом. На коммутационном табло из моделей ветвей собирается основная графцепь и N дополнительных граф-цепей. . Регулируемыми резисторами 6 устанавливают вес ветвей (в зависимости от числа свободных каналов, приоритета, стоимости связывающих линий и т.п.) К исследуемым узлам графа, между которыми определяют кратчайшие пути, например точки 32 и 33 и соответственно точки 34-39, подключаются регулируемый источник 22 напряжения и источники 25, 27 и 30 тока. При увеличении напряжения источ ика 22 токи в ветвях граф-цепи уве1йчиваются обратно пропорционально 2опротивлениям ветвей. В отдельных зетвях этой граф-цепи ток достигает значения, при котором срабатывают Пороговые элементы 5 (реле), замыкающие свои контакты в соответствующих граф-цепях 2,3 и 4. Величина ЭДС источника 22 увеличивается до тех пор, пока из элементов 13 индикации, пороговых элементов 10 и контактов 15 не будет создана электрическая цепь для источника 25 тока (для источников 27 и 30 тока цепи не будет ввиду разрьта-на контактах 29 и 31 соответственно). В результате ток потечет не по всем ветвям граф-цепи 2, а только по тем, которые создают сквозную цепь для источника 25 тока. Элементы 13 индикации отмечают основной кратчайший путь, а ПО роговые элементы 10 размыкают свои контакты 7 в граф-цепи 1, исключая использование ветвей основного пути при нахождении резервных кратчайших путей и замыкают контакты 14, обеспечивая самоблокировку найденного пути пороговыми элементами 10. При этом за счет срабатывания порогового элемента 11 к исследуемым узлам графцепи 3 подключается источник 27 тока однако основной путь на граф-цепи 3 отмечен не будет, так как соответствующие этому пути пороговые элементы 5 в граф-цепи 1 уже будут исключены контактами 7. Продолжая уве« личивать напряжение источника 22, можно аналогично определить N независимых кратчайщих путей , После определения пути под номером N пороговый элемент 5 отключает источник 22 от граф-цепи 1, Разблокировав пороговые элементы 10-12, устройство возвращают в исходное состояние, готовое дпя очередного использования. В устройстве все найденные пути. будут высвечиваться полностью, так как пороговые элементы 5 в граф-цепи 1 не имеют блокировки. Блокировка пороговыхэлементов 10-12 осзтцест вляется за счет источников 25, 27 и 30 соответственно и не требует допол нительных устройств. Время поиска множества независимых кратчайших путей на графах указанного типа практически равно поиску одного пути, что существенно повы шает эффективность Э.ТОГО устройства При использовании в качестве эле ментов 5 в граф-цепи 1, например, электромагнитных реле РЭС-8 можно построить устройство для поиска шёсти кратчайших независимых путей. Кроме того, существенно повышается точность рещения задачи поиска крат-чайших путей по сравнению с известным устройством за счет того, что -все пути определяются на одной граф-цепи, без дополнительных переключенийисточника 22. Упрощается ввод весов, так как переменные резисторы 6 входят в состав только одной граф-цепи. При использовании предлагаемого устройства для управления, например, действующими сетями связи повьштется качество управления, что в конечном, счете приводит к увеличению пропускной способности сетей, повышение эффективности их использования, улучшению вероятностно-временных характеристик сетей надежности, живучести и т.д.).

УСТРОЙСТВО ДЛЯ ПОИСКА НЕЗАВИСИМЫХ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ, НЕ ИМЕЩЕМ ПАРАЛЛЕЛЬНЫХ УЧАСТКОВ, содержащее регулируемый источник напряжения и основную и первую дополнительную граф-цепи, образующие две топологии исследуемой сети, каждая ветвь основной граф-цепи состоит из последовательно соединенных порогового элемента, выполненного в виде реле, и токозадающего переменного резистора, а каждая ветвь первой дополнительной граф-цепи состоит из последовательно соединенных элемента индикации, первого нормально разомкнутого контакта соответствующего реле основной граф-цепи и порогового элемента, вьтолненного в виде реле, к начальному и конечному узлам первой дополнительной граф-цепи подключены последовательно соединенные источник тока и индикатор тока, отличающееся тем, что, с целью расширения функциональных возможностей за счет одновременнЬго поистса незави- симых кратчайших путей, в Него введены .(V-1) дополнительных граф-цепей, идентичных первой дополнительной графцепи, (N -1) индикаторов тока и (N-1) источников тока, в каждую ветвь основ ной граф-цепи последовательно с токозадающим переменным резистором подключены последовательно соединенные N нормально замкнутых контактов ре-ле соответствующих ветвей дополнительных граф-цепей, в каждой ветви которых параллельно первому нормаль(Л но разомкнутому контакту подключен второй нормально разомкнутый контакт реле, входящего в эту ветвь, к начальному и конечному узлам -и (i 2, ..., N ) дополнительной графцепи подключены последовательно соединенные источник тока, индикатор тока и нормально разомкнутый контакт индикатора тока ( i -1)-й дополнитель о ной граф-цепи, к начальному и конеч- :АЭ :А9 ному узлам основной граф-цепи подклюгрены последовательно соединенные, регу лируемьй источник напряжения и нор:л мально замкнутый контакт индикатора тока N-и дополнительной граф-цепи.

7i,F

17