Устройство для поиска независимых кратчайших путей на графе, не имеющем параллельных участков

Устройство для поиска независимых кратчайших путей на графе, не имеющем параллельных участков

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН (19) (11) aCS1) G 06 G 7/122

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3637940/24-24 (22) 17.08.83 (46) 07.11.84. Бюл. Ф 41 (72) В.А. Кривенко и А.М. Кошель (53) 681. 333 (088. 8) (56) 1. Авторское свидетельство СССР

И-* 292164, кл. 6 06 6 7/48, 1969.

2. Авторское свидетельство СССР.

)) 913398, кл. Я 06 G 7/122, 1977 .(прототип).

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

1 1123

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

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

) пороговые элементы — газоразрядные лампы, стабилитроны, тиристоры (1) ..

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

Наиболее близким к. изобретенню Z0 по технической сущности является устройство для определения двух незави" симых кратчайших путей на графе, не имеющем параллельных участков, содержащее регулируемый источник напряже.- )5 ния, основную и первую дополнительную граф-цепи, образюущих две топологии исследуемой сети, каждая ветвь основной граф-цепи состоит из последовательно соединенных порогового элемента и переменного резистора, а каждая ветвь первой дополнительной граф-цепи состоит из последовательно соединенных элемента индикации, первоге нормально разомкнутого контакта соответствующего порогового элемента основной rpaA-цепи и порогового элемента, к начальному и конечному уз-. лам первой дополнительной граф-цепи подключены последовательно соединен- 40 ные источник тока и индикатор тока

Кроме того, устройство содержит вторуге основную граф-цепь и вторую дополнительную граф-цепь (2,».

l устройство, построенное i ïî та- 45 кой схеме, позволяет определять два независимых кратчайших пути в автоматическом режиме ..

Однако для поиска множества неза. висимых путей на графе необходимо вручную выполнить последовательно несколько операций, что приводит к существенному увеличению затрат времени. Создание устройства для поиска множества кратчайших путей на гра."55 фе известного устройства приводйт к значительному усложнению схемы, так

1 как для поиска двух путей предложено

035 2 создавать два аналогичных устройства, для поиска трех и более путей (без

;выполнения дополнительных операций) потребуется соответственно три и бо- лее аналогичных устройств.

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

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

0 независимых кратчайших путей на графе.

Поставленная цель достигается тем, что в устройство для поиска независимых кратчайших путей íà грайе, не имеющем параллельных участков, содержащее регулируемый источник напряжения и основную и первую дополнительную граф-цепи,(образующие две топологии исследуемой сети, каждая ветвь основной граф-цепи состоит из последовательно соединенных порогового элемента, выполненного в виде реле, и токозадающего переменного. резистора, а каждая ветвь первой дополнительной граф-цепи состоит иэ последовательно соединенных элемента индикации, первого нормально разомкнутого контакта соответствующего реле бсновиой граф-цепи И порогового элемента, выполненного в виде реле, к начальному и конечному узлам первой дополнительной граф-цепи подключены последовательно соединенные источник тока и индикатор тока, введены (Й -1) дополнительных граф-цепей, идентичных первой дополнительной граф-цепи, (Я -1) индикаторов тока и (Ц -1) источников тока, в кажДую ветвь основной граф-цепи последовательно с токозадающим переменным резистором подключены последовательно соединенные Й нормально замкнутых контактов реле соответствую цих ветвей дополнительных граф-цепей, 1123035 4

Ус тройство р або тае т следующим образом. в каждой ветви которых параллельно первому нормально разомкнутому контакту подключен второй нормально разомкнутый контакт реле, входящего в эту ветвь, к начальному и конечному узлам ч -й (ч =2,..., N ) дополнительной граф-цепи подключены последовательно соединенные источник тока, индикатор тока и нормально, разомкнутый:контакт индикатора тока !О (i -1)-й дополнительной граф-цепи, к начальному и конечному узлам основной граф-цепи подключены последовательно соединенные регулируемый ис- точник напряжения и нормально замкну-!5 тый контакт индикатора токай -й дополнительной граф-цепи.

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

Устройство содержит основную граф-5 цепь 1, первую дополнительную графцепь 2, и -1 дополнительных графцепей 3 и 4; каждая ветвь основной . .граф-цепи 1 состоит из порогового элемента 5, выполненного в виде ре-. ле, токозадающего переменного резистора б, нормально замкнутых контактов

7-9 соответствующих реле 10-12, Каж- дая ветвь первой дополнительной графцепи 2 состоит из порогового элемента 10, индикационного элемента 13, нормально разомкнутого контакта 14, реле. 10 и .нормально разомкнутого,кон- . такта 15 реле 5, каждая ветвь графцепи 3 состоит из порогового элемента

11, выполненного в виде реле индика- 4О ционного элемента t6, нормально разомкнутого контакта 17 реле 11 и нормально разомкнутого контакта 18 реле 5, каждая ветвь граф-цепи 4 состоит из порогового элемента 12, 45 индикационного элемента 19, нормально разомкнутого контакта 20 реле 12 и нормально разомкнутого контакта 21 реле 5. Кроме того, устройство содержит регулируемый источник 22 напряжения, нормально разомкнутый контакт 23, индикатор 24 тока, источник

25 тока, индикатор 26 тока, источник

27 тока, индикатор 28 тока, нормально разомкйутый контакт 29, индикатор тока 26, источник 30 тока, нормально

4 I разомкнутый контакт 31 индикатора

28 тока.

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

Регулируемыми резисторами б устанавливают "вес" ветвей (в зависимости от числа свободных каналов, приоритета, стоимости связывающих линий и т.п.) К исследуемым узлам графа, между которыми определяют кратчайшие пути, например точки 32 и 33 и соответственно точки 34-39, подключаются регулируемый источник 22 напряжения и источники 25, 27 и 30 тока.

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

Пороговые элементы 5 (реле), замыкающие свои контакты в соответствующих граф-цепях 2,3 и 4. Величина

ЭДС источника 22 увеличивается до тех пор, пока из элементов 13 индикации, пороговых элементов 10 и контактов 15 не будет создана электрическая цепь для источника 25 тока (для источников 27 и 30 тока цепи не будет ввиду разрыва.на контактах

29 и 31 соответственно). В результате ток потечет не по всем ветвям граф-цепи 2, а только по тем, которые создают сквозную цепь для источника

25 тока. Элементы 13 индикации отмечают основной кратчайший путь, а пороговые элементы 10 размыкают свои контакты 7 в граф-цепи 1, исключая !использование ветвей основного пути при нахождении резервных кратчайших путей и замыкают контакты 14, обеспечивая самоблокировку найденного пути пороговыми элементами 10. При этом

sa счет срабатывания порогового элемента 11 к исследуемым узлам графцепи 3 подключается источник 27 тока однако основной путь на.граф-цепи 3 отмечен не будет, так как соответствующие этому пути пороговые элементы 5 в граф-цепи 1 уже будут исключены контактами 7. Продолжая увеличивать напряжение источника 22, можно аналогично определить Н независимых кратчайших путей., После определения пути под номером Й пороговый элемент 5 отключа1123035

Составитель А. Яицков

Техред А.Бабинец

Редактор Н. Данкулич

Корректор О. Ти r op

Заказ 8141/40 Тираж 698

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Подписное

Филиал ППП "Патент", г ° Ужгород, ул. Проектная, 4 ет источник 22 от граф-цепи 1. Разблокировав пороговые элементы 10-12, устройство возвращают в исходное состояние, готовое для очередного использования.

В устройстве все найденные пути . будут высвечиваться полностью, так как пороговые элементы 5 в граф-цепи 1 не имеют блокировки. Блокиров10 ка пороговых элементов 10-12 осуществляется за счет источников 25, 27 и

30 соответственно и не требует дополнительных устройств.

Время поиска множества независи- 15 мых кратчайших путей на графах укаI занного типа практически равно поиску одного пути, что существенно повышает эффективность этого устройства.

При использовании в качестве зле- 20 ментов 5 в граф-цепи 1, например, электромагнитных реле РЭС-8 можно построить устройство для поиска ше.сти кратчайших независимых путей.

Кроме того, существенно повышается точность решения задачи поиска крат-. чайших путей по сравнению с известным устройством за счет того, что все пути определяются на одной граф- цепи, без дополнительных переключений источника 22. I

Упрощается ввод "весов", так как переменные резисторы 6 входят в состав только одной граф-цепи.

При использовании предлагаемого устройства для управления, например, действующими сетями связи повьш|ается качество управления, что в конечном. счете приводит к увеличению пропускной способности сетей, повышению эффективности их использовайия, улучшению вероятностно-временных характеристик сетей (надежности, живучести и т.д.).