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

 

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

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

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

Под "весом" ветви понимается определенная комбинация значений таких ее частных параметров, как пропускная способность, протяженность, стоимость, надежность и т.п.

Известны устройства для определения кратчайших путей на графе, содержащие в составе моделей ветвей пороговые элементы - стабилитроны [1], газоразрядные приборы [2-4]. Недостатком этих устройств является то, что в них невозможно плавное изменение весовых коэффициентов ветвей, что приводит к низкой точности моделирования исследуемых сетей.

В качестве прототипа данного изобретения выбрано "Устройство для определения кратчайших путей на графе" [5].

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

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

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

Для обоснования необходимости таких изменений рассмотрим фрагмент сети, состоящий из трех узлов, например A, B, C, и соединяющих из ветвей сети - AB, BC и AC.

Предположим, что, при прочих равных условиях, влияющих на величину "веса" ветвей (их протяженность, стоимость, надежность и т.п.), ветвь AB имеет один свободный исправный канал связи, а ветви BC и AC - по три. Если принять, что установленная величина напряжения "пробоя" порогового устройства с регулируемой нелинейной характеристикой ветви, имеющей один исправный свободный канал связи, будет составлять величину U_пр.1, то тогда величины напряжения "пробоя" пороговых устройств ветвей AB, BC и AC будет соответственно равны: где n - канальная емкость соответствующей ветви связи.

Пусть ставится задача определить кратчайший путь между узлами A и B.

Поскольку в данном случае величина напряжения "пробоя" порогового элемента ветви AB, т. е. прямого пути между узлами A и B, будет составлять U_пр.AB = U_пр.1, а составного пути ACB и так как то кратчайший путь между исследуемыми узлами A и B, показанный устройством-прототипом, "веса" моделей ветвей которого учитывают только собственные параметры и не учитывают возможность наличия транзитных соединений на сети, будет составной путь ACB, в то время как действительно кратчайшим путем между узлами A и B в рассматриваемом варианте является прямой путь AB.

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

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

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

Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием дополнительных элементов при соответствующем схемном решении. Таким образом, заявляемое устройство соответствует критерию изобретения "новизна".

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

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

Схема предлагаемого "Устройства для определения кратчайших путей на графе" представлена на чертеже, где обозначено: 1 - электрическая граф-цепь; A, B, C, D, ... N - узловые точки граф-цепи; 2 - пороговый элемент с регулируемой нелинейной характеристикой; 3 - элемент индикации;
4 - регулируемый источник напряжения;
5 - пороговый элемент с нелинейной характеристикой;
6 - многополюсный выключатель.

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

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

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

В исходном положении величина выходного напряжения регулируемого источника напряжения равна нулю. На пороговых элементах с регулируемой нелинейной характеристикой 2 устанавливается величина "пробоя", характеризующая собой обобщенный "вес" соответствующей ветви.

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

При плавном увеличении величины выходного напряжения регулируемого источника напряжения 4 наступит момент, когда его величины будет достаточно для "пробоя" пороговых элементов 2 и 5 моделей ветвей, составляющих путь между исследуемой парой узловых точек графа, для которых

т.е. ветвей, образующих искомый кратчайший путь,
где L - количество последовательно соединенных ветвей, образующих данный путь;
U_пр.l - установленная величина напряжения "пробоя" порогового элемента с регулируемой нелинейной характеристикой 2 в l-ой модели ветви;
2'(L-1) - количество незашунтированных пороговых элементов с нелинейной характеристикой 5, входящих в данный путь;
U_пр.тр. - величина напряжения "пробоя" порогового элемента с нелинейной характеристикой 5.

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

Рассмотрим значение имеющихся в составе предложенного устройства пороговых элементов с нелинейной характеристикой 5 и многополюсных выключателей 6.

Примем величину напряжения "пробоя" U_пр.тр. пороговых элементов с нелинейной характеристикой 5 равной половине напряжения пробоя порогового элемента с регулируемой нелинейной характеристикой 2, моделирующей ветвь емкостью в один канал связи, т.е.

U_пр.тр. = 0,5' U_пр.1.
Тогда, обращаясь к рассмотренному выше примеру, имеем:
U_пр.AB = U_пр.1;

Поскольку в этом случае
то предложенное устройство в качестве кратчайшего пути между узлами A и B покажет не обходной путь ACB, а прямой путь AB, т.е. действительно кратчайший путь.

Следовательно, предложенное устройство работоспособно.

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

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

А так как всегда R > = 2, то экономия времени на изменение "весов" моделей ветвей с учетом возможных транзитных соединений, обеспечиваемая предложенным устройством по сравнению с прототипом, всегда будет не менее 50%, поскольку

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

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

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

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

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

Источники информации
1. А.с. СССР N 417802, МКИ G 06 G 7/48, 1974, БИ N 8;
2. А.с. СССР N 408334, МКИ G 06 G 7/70, 1973, БИ N 47;
3. А.с. СССР N 1275480, МКИ G 06 G 7/122, 1986, БИ N 45;
4. А.с. СССР N 1325517, МКИ G 06 G 7/122, 1987, БИ N 27;
5. А.с. СССР N 552617, МКИ G 06 G 7/122, 1977, БИ N 12 (прототип).

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

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

РИСУНКИ

Рисунок 1