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

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

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

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

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

и управляемые диоды-тиристоры), индикатор 5 и источник 6 тока.

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

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

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

образом.

При вк11ючении И(;точника 6 тока напряжение между его полюсами начинает возрастать, и в определенный момент времени происходит зажигание

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

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

вершину 3 ветвям одинаково удлиняет все возможные маршруты на некоторую постоянную величину, пропорциональную величине 2, где - напряжение включения элемента 4. Как

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

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники и может быть использовано для решения широкого круга экстремальных транспортных задач. Цепью изобретения является повышение точности ofnpeделения кратчайшего пути. Поставленная цель достигается тем, что в устройство, содержащее элементы с падающим участком вольт-амперной характеристики, например газоразрядные приборы, индикатор и источник тока, введены элементы с отрицательным участком вольт-амперной характеристики релейного типа, например переключающие и управляемые диоды-тиристоры. Это позволяет повысить точность следующим образом. Как только произойдет выбор кратчайшего маршрута, наQ б пряжение на диодах-тиристорах падает до нуля, резко увеличивая раз(/) ность, напряжений между.включенным путем и близкими к нему неоптимальными путями t.что предотвращает включение других, близких к оптимальному, путей на сети. 1 з.п. ф-лы, 1 ил. 1чЭ ч1 СЛ 4 С