Устройство для определения экстремальных путей в графе

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союэ СоветскихСоцыалыстычесиихреспублик(22) Заявлено 1 б.02.77 (21) 245с присоединением заявки М 4134 18-24 П риоритет Опубликовано 05,02.80 Б Дата опубликования опис н етенн ллетень М 5ия 05.02.80(72) Авторы изобретения О. Г. Алексеев и В, Ю. Мержанов ная артнллерийная ордена Ленина Краснознаменная академия им,. М. И, Калинина аявмтель(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ В ГРАФЕ му Изобретение относится к вычислительнойтехнике и может быть использовано для реше.ння минимаксной задачи выбора,Известно устройство для моделированиязадач математического программирования, со.держащее блок измерения и управления, блокиоперационных усилителей, блоки трехполюсников и блоки питания 111.Известное устройство может быть использовано для приближенного решения комбинатор.ных задач, сформулированных в терминах ли.нейного программирования.Недостатком устройства является большоевремя 1 поиска решения комбннаторных задач,обусловленное резким возрастанием их размер.ности при переходе к линейным моделям иувеличением количества итераций вследствиевведения отсечений.Наиболее близким по технической сущностик предложенному изобретению является устройст.во для определения кратчайших путей в графе, со.держащее блоки индикации, первые выходы которых объединены и подключены к входукоммутатора (23. Известное устройство позволяет моделировать сетевые графы и может быть использовано для решения минимаксной задачи выбора в сетевой интерпретации. Однако вследствие неаддитивности целевой функции и комбинаторного характера указанной задачи при этом потребовалось бы моделировать и сопоставлять множество вариантов графов, обусловленное возможными разбиениями множества работ на подмножества назначений каждому исполнителю, Перебор множества вариантов приводит к боль шим затратам времени.Цель изобретения - ускорения процесса поиска решения.Поставленная цель достигаегся тем,чго в устройство введены блоки памяти и блок выделения экстремума,причем первые выходы блоков индикации объединены и подключены ко входу коммутатора, а вторые выходы блоков индикации соединены со входамн соответствующих блоков памяти, выходы которых соответственно соединены со вхоДами блока выделения экстреруктурная схема приведена на чертеж5 7в режим запоминания, причем его входнаяцепь разрывается, выход подключается ко вто.рому входу усилителя У 1, который вновьпереводится в малоинерцнонный режим, а навыходе усилителя У 2 и, следовательно, навтором входе усилителя У 1 блока 2 сохраняется напряжение, пропорциональное значениюС+. Реле РК 2 отпускает, его контакты разрывают цепь питания реле РКЗ и замыкаютцепьпитания искателя И коммутатора 4, Реле РКЗотпускает и своими размыкайщими контактами замыкает входные цепи блоков 21 - 2 п, 3,щетки искателя И перемещаются в следующееположение и происходит переход ко второму пвгу.решения.На втором шаге решения с выходов блоков11 - 1 и на входы блоков 2 - 2 п подаются напряжения, пропорциональные значениям С,Таким образом, на выходе усилителя У 1 бло.ка 2 установится напряжение, пропорциональное С +С , а на выходах блоков 2 - 2 днапряжении, пропорциональные значениям СС 2 п соответственно Аналогично тому, как этоосуществлялось на первом шаге решения вблоке 3 происходит выделение значенияп 1 и (С,и + С , С, ,С,), в одном изблоков 21 - 2, его запоминание, а в соответствующем блоке 1 - 1 - индикация выбранного варианта назначения работы с номером 2,В результате коммутации цепей устройства".щетки искателя И перемещаются в новое положение и пройсходит переход к следующемушагу решения,После выполнения в шагов через (а+1)-йконтакт поля искателя И образуется цепь питания реле РК 1 и транспаранта Л 1 коммутато.ра 4. Реле РК 1 срабатывает и своими размыкающими контактами разрывает цепи питанияреле Р 1 - Рп, РК 2, РКЗ, искателя И коммутатора 4 и входные цепи блока 3. 14421 6Загорание транспаранта Л 1 коммутатора 4сигнализирует об окончании процесса решения,Номера горящих транспарантов блоков 11-1 попределяют индексы значений С,ц, вошедших в 5 рещение, Показания вольтметров Ч 1-Чп бло.ков 2,1-2 п пропорциональны суммарным затратам соответствующего исполнителя.Для приведения схемы в исходное положе, ние снимается напряжение с шин питания, с 10 помощью кнопок в цепях обратной связи обнуляются выходы усилителей У 2 - У 2 блокови2 - 2 п и осуществляется возврат щеток искателя И и размыкание выключателя В коммутатора 4Благодаря введению новых блоков и связейускорился процесс поиска решения.Формула изобретения20Устройство для определения экстремальныхпутей в графе, содержащее блоки индикации,первые выходы которыхобъединейы и подключены ко входу коммутаторао т л и ч а ю 25щ е е с я тем, что, с целью ускорения процесса поиска решения, в него дополнительновведены блоки памяти и блок выделенияэкстремума, причем первые. выходы блоков индика.ции объедиены и подключены ко входу ком 30мутатора, а вторые выходы блоков индикациисоединены со входами соотве 1 ствующих блоковпамяти, выходы которых соответственно соединены со входами блока вьщеления экстремума.Источники информации,35принятые во внимание при экспертизе1. Васильев В. В. и др, Решение задач опти-мального планирования на электронных моделяхК "Наукова Думка", 1966, с. 36 - 38,402, Авторское свидетельство СССР Х 417802Экл. 6 О 6 6 7/48, 1974 прототип).714421 Составитель И. ЛебедеТехред М.Келемеш ректор , Г. Назаро Редактор Д. Зубов К аз 9291(4 ПодписноеСССР 1 ираж 751 ПНИИПИ Государственного комитета по делам юобретений и открытий 113035, Москва, Ж - 35, Раушская наб., д, 4