Устройство для определения кратчайших путей на графе
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Номер патента: 552617
Автор: Холин
Текст
Вавссю пц И 2617 Союз СсветсиСвциалистичес ОБРЕТЕНИЯТОРСКОМУ СВИДЕТЕЛЬСТВУ еспубл К(23) ПриоритетОпубликовано 30 Гваударственный квмитет Свеета Министров СССР 3) УДК 681 14(088 8 Бюллетень1писания 11,04.77 в делам изобретений и открытий(71) Заявите ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХУТЕЙ НА ГРАФЕ 54) УСТРОЙСТ 2 яющая со согласно цепи, для которой 1 п. В э Изобретение относится к специализированной вычислительной технике и может быть ис пользовано при исследовании отдельных свойств графов, проектировании и распределении каналов на сетях связи и информационных сетях, разработке экономических вариантов транспортных перевозок и т. д,Известно устройство для определения кратчайших путей на графе, содержащее модели ветвей с источниками напряжения и диодами 11. Это устройство сложно, приводит к большим погрешностям измерений.Известно также наиболее близкое по технической сущности к изобретению устройство, содержащее модели ветвей, соединенные согласно топологии исследуемого графа 21. Недостатком его является сложность, обусловленная наличием в каждой модели ветви источников ЭДС, гальванически не связанных друг с другом.Цель изобретения - упрощение устройства.Это достигается тем, что в устройство введен источник напряжения, а модель ветви содержит тиристор с элементом упрзвления, резистор, соединенный последовательно с тиристором, и диоды, подключенные параллельно тиристору, а элемент управления тиристором подключен к источнику напряжения.На фиг. 1 показана принципиальная схема модели двунаправленной ветви; на фиг, 2 -общая схема устроиства, представлбой соединенные модели ветвей М 1топологии исследуемого графа.Схема модели ветви содержит тиристоры 1 5 и 1, элемент 2 управления тиристорами, диоды 3 и 3, шунтирующие один из тиристоров в зависимости от направления тока, протекающего в ветви Ц, резистор 4, сопротивление которого используется для индикации кратчай шего пути, а также источник 5 напряжения.Работает устройство следующим образом, Из моделей ветвей собирается схема топологии, аналогичная исследуемому графу фиг.2. С помощью потенциометров элемент 2 уп равления тиристорами устанавливает ток вуправляющей цепи тиристора, соответствующий заданному напряжению переключения, пропорциональному весу данной ветви.К исследуемым узлам графа, между кото рыми определяется кратчайший путь, подключается регулируемый источник ЭДС Е, При увеличении напряжения источника от 0 до Ео,в какой-то момент времени произойдет переключение тиристоров, принадлежацепи потечет ток, создающии падение напряжения на сопротивлении резистора 4, в ре зультатс чего будут отмечены ветви графа,3принадлежащие кратчайшему пути (элементы индикации на схеме не показаны).Применение в качестве порогового устройства тиристора, а также схемы, позволяющей моделировать двунаправленные ветви графа как с симметричными, так и с несимметричными весовыми коэффициентами, использование одного источника ЭДС для всех моделей ветви упрощает устройство. Формула изобретенияУстройство для определения кратчайших путей на графе, содержащее модели ветвей, 652617 соединенные согласно топологии исследуемого графа, отличающееся тем, что, с целью упрощения устройства, оно содержит источник напряжения, а модель ветви содержит ти ристор с элементом управления, резистор, соединенный последовательно с тиристором, и диоды, подключенные параллельно тиристору, а элемент управления тиристором подключен к источнику напряжения.10 Источники информации, принятые во внимание при экспертизе1. Авт. св.231903, кл. 6 060 7/48, 1970.2. Авт. св.344463, кл. 0 066 7/48, 1970ПодписиССР ипография, пр. Сапунова,Заказ 676/20 Изд.318 ЦНИИПИ Государственного по делам изо 113035, Москва, Ж
СмотретьЗаявка
2130380, 04.05.1975
ВОЙСКОВАЯ ЧАСТЬ 25871
ХОЛИН АЛЕКСЕЙ ВИКТОРОВИЧ
МПК / Метки
МПК: G06G 7/122
Метки: графе, кратчайших, путей
Опубликовано: 30.03.1977
Код ссылки
<a href="https://patents.su/3-552617-ustrojjstvo-dlya-opredeleniya-kratchajjshikh-putejj-na-grafe.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для определения кратчайших путей на графе</a>
Модель двунаправленной ветви
Номер патента: 736121
Опубликовано: 25.05.1980
Авторы: Додонов, Федоров, Федотов, Хаджинов, Шишмарев
МПК: G06G 7/122
Метки: ветви, двунаправленной, модель
..."пусковой импульс. Он проходит только тот апемент И, на котором в данный момент есть сигнап перепопнения с выхода счетчика.При переполнении счетчика 13 "пусковой"импульс проходит элемент И 3 иустанавпивает триггер 17 в единичное ссстояние,736 1 5При переполнении счетчика 14 пусковой импульс проходит элемент И 4 и устанавливает триггер 18 в единичное состояние. 10 Единичное состояние одного из триг геров 17 или 18 производит блокировку входа элемента И 3 или И 4 и, соответственно,поступает на вход 23 или 24 одного из формирователей 19 или 20 веса ветви. Тем самым производится подготовка одного из формирователей веса ветви в одном из направлений к работе, Если триггер 17 находится в единичном состоянии, то подготавливается формирователь 19...
Модель ветви графа
Номер патента: 470811
Опубликовано: 15.05.1975
МПК: G06F 15/173
...И 5 по выходу 25 поступает в блок автоматического формирования топологии 12 на один из входов группы входов 27 элемента ИЛИ 15, к остальным входам которого подсоединены одноименные выходы других моделей ветвей, не изображенных на чертеже. Пройдя через элемент ИЛИ 15, сигнал поступает на вход инвертора 21, который вырабатывает запрет на одном из входов элемента И 20, Второй вход элемента И 20 соединен со входом 31 и далее с выходом 36 генератора импульсов 14, поэтому серия импульсов ГИ, больше не поступает на вход 24 модели ветви 11. Одновременно с выхода элемента ИЛИ 15 на один из входов элемента И 19 поступает разрешение, и через элемент И 19, второй вход которого соединен со входом 32 и далее - с выходом 37 генератора импульсов...
Модель ветви графа
Номер патента: 583439
Опубликовано: 05.12.1977
Авторы: Васильев, Голованова, Додонов, Ралдугин, Фенюк
МПК: G06F 15/173
...регистр 4, триггеры Б,б,элементы И 7-12 и инвертор 13,Работу модели ветви рассмотрим, начи 5 ная с момента, когда сформирован 1-йузел с вероягностным выходом. йопустим,из-го узла выходят четыре ветви свероятностями реализации,Р =, гО,2, Рз 0,1 Р 4 0,8, емкость реги 0 ФФра Ю " 10, и реализуется алцгернитивный выбор одной из исходящих ветвей. Одиниз возможных способов занесенйя информации о вероятностях в разряды сдвиговыхрегистров приведен в табл.ФПример заполнения регистров Таблица,кончаяяиваетссдвига же,Обязательный выбор одной из ветвей по решаюг прохождение этого сигнала н 6 выхоии формирования-го узла обеспе-.ф ды элементов И 12 и на первые триггеры,я тем, что после каждого импульса которые устанавливаются в единичное состояна...
Модель ветви графа
Номер патента: 652566
Опубликовано: 15.03.1979
Авторы: Васильев, Голованова, Додонов
МПК: G06F 15/173
...Сигнал с выхода блока задания конечного адреса модели О-йветви поступает на выход 29 соответ20ствующей модели ветви, который соединен с одним из входов 31 элемента ИЛИ19, к остальным входам которого присоединены одноименные выходы всех моделей ветвей, и с выхода элемента ИЛИ2519, который соединен со входом элемен та ИЛИ 21, указанный сигнал поступаетна выход 38, и далее - на вход 27 рассматриваемой 1 -й модели ветви соеди 1ЗОненный со вторым входом элемента И 2,и на одноименные входы остальных ветвей, Так как третий вход элемента И 2соединен с нулевыМ выходом триггера11, находящегося в нулевом состоянии,35то сигнал с выхода блока задания на- .чального адреса 9 пройдет через элемент И 2 г. увеличит содержимое счетчика 8 на "1 ф. Выходной...
Модель ветви графа
Номер патента: 1012268
Опубликовано: 15.04.1983
Авторы: Влазнев, Додонов, Щетинин
МПК: G06F 15/173
...неисключениых ветвей и обязательный выбор одной из них. Анализ получаемых в . процессе моделирования гипотез на соответствие исходным данным задачи может выполнять специальное контро".: :лирующее устройство, входящее в состав блока управления, В его . функции входит выявление ветвей гра= фа, которые необходимо исключить на каждом этапе моделирования, и выдача (в момент ожидаемого прихода первого сдвигового импульса случайнойсерии) сигнала запрета на запрещающий вход каждой модели ветви, которая должна быть исключена из процесса моделирования, допустим, что сигналы запрета в указанный выше момент поступили. на запрещаю 6 7 8, 9 щие входы второй и третьей моделей ветви. Тогда, поскольку числосдвиговых импульсов случайно, могутиметь...
Предыдущий патент: Масштабный преобразователь
Следующий патент: Дифференцирующее устройство
Случайный патент: Устройство для поиска экстремума