Устройство для определения кратчайшего пути на графах
Изобретение относится к области вычислительной техники и может быть использовано для решения широкого круга экстремальных транспортных задач. Цепью изобретения является повышение точности ofnpeделения кратчайшего пути. Поставленная цель достигается тем, что в устройство, содержащее элементы с падающим участком вольт-амперной характеристики , например газоразрядные приборы , индикатор и источник тока, введены элементы с отрицательным участком вольт-амперной характеристики релейного типа, например переключающие и управляемые диоды-тиристоры. Это позволяет повысить точность следующим образом. Как только произойдет выбор кратчайшего маршрута, наQ б пряжение на диодах-тиристорах падает до нуля, резко увеличивая раз (/) ность, напряжений между.включенным путем и близкими к нему неоптимальными путями t.что предотвращает включение других, близких к оптимальному, путей на сети. 1 з.п. ф-лы, 1 ил. 1чЭ ч1 СЛ 4 С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51)4 G 06 G 7/122 -»
1 °
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н ASTOPGHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3884688/24-24 (22) 12.04.85 (46) 07,12.86. Бюл, У 45 (71) Киевский автомобильно-дорожный институт им. 60-летия Великой Октябрьской социалистической револю" ции (72) Л, В, Федотов, Б, М,,Четверухин, Ю. И, Санников и В, И. Михайленко (53) 681.333(088,8) (56) Авторское свидетельство СССР
У 417802, кл. G 06 G 7/122 ° 1972.
Авторское свидетельство СССР
М 408334, кл, G 06 G 7/122, 1971. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ
КРАТЧАЙШЕГО ПУТИ НА ГРАФАХ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения широкого круга экстремальных транспорт„„SU„„1275480 А 1 ных задач, Целью изобретения является повьппение точности бпределення кратчайшего путы. Поставленная цель достигается тем, что в устройство, содержащее элементы с падающим участком вольт-амперной характеристики, например газоразрядные приборы, индикатор и источник тока, введены элементы с отрицательным участком вольт-амперной характеристики релейного типа, например переключающие и управляемые диоды-тиристоры, Это позволяет повысить точность следующим образом, Как только произойдет выбор кратчайшего маршрута, напряжение на диодах-тиристорах падает до нуля, резко увеличивая разность.напряжений между. включенным путем и близкими к нему неоптимальными путями .что предотвращает включение других, близких к оптимальному, путей на сети. 1 s.n, ф-лы, 1 ил, 1275480
Положительный полюс источника 6 тока соединен с одними выводами элементов 4 с отрицательным участком вольт-амперной характеристики релейного типа, другие выводы которых соединены с газораэрядными приборами 1 одноименных начальных ветвей, причем число элементов 4 равно числу ветвей, с6единенных с вершиной
2, Отрицательный полюс источника 6 тока соединен с одними выводами элементов 4 с отрицательным участком
40 вольт-амперной характеристики релейного типа, другие выводы которых соединены с гаэоразрядными приборами 1 одноименных ветвей графа, причем число элементов 4 равно числу ветвей, соединенных с.конечной вершиной графа. Индикатор 5 подключен параллельно источнику 6 тока. Полярность включения элементов 4 к источнику 6 тока должна быть согласована с полярностью источника 6 тока и обеспечить прохождение тока в цепи.
Устройство работает следующим образом, При включении источника 6 тока напряжение между его полюсами начинает возрастать, и в определенный момент времени происходит зажигание
Изобретение относится к вычислительной технике и может быть использовано для решения широкого круга экстремальных транспортных задач, Целью изобретения является повы- 5 шение точности определения кратчайшего пути, На чертеже изображена структурная схема устройства для определения кратчайшего пути. 10
Устройство содержит элемент с падающим участком вольт-амперной характеристики, например газораэрядный прибор 1„начальную и конечную вершины 2 и 3 исследуемого графа, 15 элементы 4 с отрицательным участком вольт-амперной характеристики релейного типа (например, переключающие и управляемые диоды-тиристоры) ° индикатор 5 и источник 6 тока, 20
Группы последовательно соединенных газоразрядных пр,иборов 1, число которых равно длине моделируемой ветви, соединены между собой в узлы согласно топологии моделируемого га- 25 за sa исключением ветвей, принадлежащих начальной 2 и конечной 3 вершинам графа. групп газоразрядных приборов 1, суммарное напряжение зажигания которых является минимальным из возможных сочетаний их подключения к источнику 6. При этом высвечивается оптимальный (кратчайший) путь сети. Индикатор 5, измеряющий напряжение между полюсами источника 6 тока, определяет в заданном масштабе длину включенного пути. Дополнительное подключение элементов 4 с отрицательным участком вольт-амперной характеристики релейного типа к всем выходящим из вершины2 и входящим в вершину 3 ветвям одинаково удлиняет все возможные маршруты на некоторую постоянную величину, пропорциональную величине 2, где U „„ - напряжение включения элемента 4. Как только произойдет выбор кратчайшего маршрута, напряжения на соответствующих включенных элементах 4 падают до нуля, резко увеличивая тем самым разность напряжений между включенным путем и близкими к нему неоптимальными путями на величину не менее 208 „, что предотвращает включение других, близких к оптимальному, путей на сети.
Поскольку при включении оптимального пути напряжение на включенных элементах 4 равно нулю, индикатор указывает истинную длину оптимального пути, соответствующую суммарному напряжению горения. включенных газоразрядных приборов.
Таким образом, применение элементов с отрицательным участком вольтамперной характеристики релейного типа в моделях для определения оптимального пути позволяет в момент решения задачи определения этого пути значительно увеличить разность между суммарным напряжением на оптимальном пути и напряжением включения близких к нему путей, что исключает неоднозначность определения пути, а следовательно, повышает точность определения кратчайшего пути, Формула изобретения
1. Устройство для определения кратчайшего пути на графах, содержащее модели ветвей, соединенные в соответствии с топологией исследуемого графа, источник тока и индикатор, причем каждая модель ветви включает группу последовательно соединенных
12754
Составитель Т. Сапунова
Редактор О. Юрковецкая Техред В.Кадаy
Корректор М. Пожо
Заказ 6564/43 Тираж 671
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб,, д. 4/5
Подписное
Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4 элементов с падающим участком вольтамперной характеристики, например гаэоразрядный прибор, источник тока и.индикатор соединены параллельно между собой и включены между начальной и.конечной вершинами исследуемого графа, о т л и ч а ю щ.е е с я .тем, что, с целью повышения точности, в каждую ветвь, соединенную с начальной вершиной графа, и в каждую ветвь,10 соединенную с конечной вершиной графа, введен элемент а отрицательным
4 участком вольт-амперной характеристики релейного типа, причем-sagMem с отрицательным участком вольт-амперной характеристики релейного типа включается между полюсом источника и элементом с падающим участком вольт-амперной характеристики.
2, Устройство по п, 1, о т л ич а ю щ е е с я тем, что элемент с отрицательным участком вольт-амперной характеристики релейного типа ,выполнен в виде диода-тиристора,
