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

(21) 38846 (22) 12.04 (46) 07.12 (71) Киевс институт и тябрьской нияцелтво орожиыйй Оке волю" ИЧетверуВ, И, Михай едотов, анников АРСТВЕННЫЙ КОМИТЕТ СССРЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССР У 417802, кл. С 06 С 7122, 1972,Авторское свидетельство СССР У 408334, кл, С 06 С 7/122, 1971. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ НА ГРАФАХ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения широкого круга экстремальных транспортных задач, Целью изобретения является повьппение точности бпределекратчайшего путы, Поставленная ьдостигается тем, что в устройссодержащее элементы с падающимучастком вольт-амперной характеристики, например газоразрядные прибо"ры, индикатор и источник тока, введены элементы с отрицательным участком вольт-амперной характеристикирелейного типа, например переключающие и управляемые диоды-тиристоры,Это позволяет повысить точность следующим образом, Как только произойдет выбор кратчайшего маршрута, напряжение на диодах-тиристорах падает до нуля, резко увеличивая разность,напряжений между, включеннымпутем и близкими к нему неоптимальными путями.что предотвращает включение других, близких к оптимальному,путей на сети. 1 э,п. Ф-лы, 1 ил, 1275480Положительный полюс источника 6тока соединен с одними выводами элементов 4 с отрицательным участкомвольт-амперной характеристики релейного типа, другие выводы которыхсоединены с газораэрядными приборами 1 одноименных начальных ветвей,причем число элементов 4 равно числу ветвей, соединенных с вершиной2, Отрицательный полюс источника 6тока соединен с одними выводамиэлементов 4 с отрицательным участком40вольт-амперной характеристики релейного типа, другие выводы которыхсоединены с гаэоразрядными приборами 1 одноименных ветвей графа, причем число элементов 4 равно числуветвей, соединенных с.конечной вершиной графа. Индикатор 5 подключенпараллельно источнику 6 тока. Полярность включения элементов 4 к источнику 6 тока должна быть согласованас полярностью источника 6 тока иобеспечить прохождение тока в цепи.Устройство работает следующимобразом,При включении источника 6 токанапряжение между его полюсами начинает возрастать, и в определенныймомент времени происходит зажигание 45 Изобретение относится к вычислительной технике и может быть использовано для решения широкого кругаэкстремальных транспортных задач,Целью изобретения является повышение точности определения кратчайшего пути,На чертеже изображена структурнаясхема устройства для определениякратчайшего пути.Устройство содержит элемент спадающим участком вольт-амперной характеристики, например газораэрядный прибор 1 начальную и конечнуювершины 2 и 3 исследуемого графа, 15элементы 4 с отрицательным участкомвольт-амперной характеристики релейного типа (например, переключающиеи управляемые диоды-тиристоры)ин.шюкатор 5 и источник 6 тока, 20Группы последовательно соединенных газоразрядных приборов 1, числокоторых равно длине моделируемойветви, соединены между собой в узлысогласно топологии моделируемого газа за исключением ветвей, принадлежащих начальной 2 и конечной 3 вершинам графа. групп газоразрядных приборов 1, суммарное напряжение зажигания которыхявляется минимальным из возможныхсочетаний их подключения к источнику 6. При этом высвечивается оптимальный (кратчайший) путь сети. Индикатор 5, измеряющий напряжениемежду полюсами источника 6 тока, определяет в заданном масштабе длинувключенного пути. Дополнительноеподключение элементов 4 с отрицательным участком вольт-амперной характеристики релейного типа к всемвыходящим из вершины 2 и входящим ввершину 3 ветвям одинаково удлиняетвсе возможные маршруты на некоторуюпостоянную величину, пропорциональную величине 2, где 11- напряжение включения элемента 4. Кактолько произойдет выбор кратчайшегомаршрута, напряжения на соответствующих включенных элементах 4 падаютдо нуля, резко увеличивая тем самым.разность напряжений между включеннымпутем и близкими к нему неоптимальнымипутями на величину не менее 208, чтопредотвращает включение других,близких к оптимальному, путей на сети,Поскольку при включении оптимального пути напряжение на включенныхэлементах 4 равно нулю, индикаторуказывает истинную длину оптимального пути, соответствующую суммарномунапряжению горения. включенных газоразрядных приборов.Таким образом, применение элементов с отрицательным участком вольтамперной характеристики релейноготипа в моделях для определения оптимального пути позволяет в момент решения задачи определения этого путизначительно увеличить разность между суммарным напряжением на оптимальном пути и напряжением включенияблизких к нему путей, что исключаетнеоднозначность определения пути, аследовательно, повышает точность определения кратчайшего пути,Формула изобретения1. Устройство для определения кратчайшего пути на графах, содержащее модели ветвей, соединенные в соответствии с топологией исследуемого графа, источник тока и индикатор, причем каждая модель ветви включает группу последовательно соединенных12754 Составитель Т. Сапуноедактор О, Юрковецкая Техред В.Кадар Корректор М. П аказ 6564/43 Тираж 671 ВНИИПИ Государственного по делам иэобретений 113035, Москва, Ж, Раушодпи сн омитета СССРоткрытийая наб д. 4/5 роиэводственно-полиграфическое предприятие, г. Ужгород, ул. Проектна элементов с падающим участком вольтамперной характеристики, напримергаэораэрядный прибор, источник токаи.индикатор соединены параллельномежду собой и включены между начальной и.конечной вершинами исследуемогографа, о т л и ч а ю щ.е е с я .тем,что, с целью повышения точности, вкаждую ветвь, соединенную с начальной вершиной графа, и в каждую ветвь,0соединенную с конечной вершиной графа, введен элемент в отрицательным 804участком вольт"амперной характеристики релейного типа, причем-элемент с отрицательным участком вольт-амперной характеристики релейного типа включается между полюсом источника и элементом с падающим участком вольт-амперной характеристики.2, Устройство по п, 1, о т л ич а ю щ е е с я тем, что элемент с отрицательным участком вольт-амперной характеристики релейного типа ,выполнен в виде диода-тиристора,