Устройство для решения экстремальных комбинаторных задач

(57) Изобретение относ тельной технике и може зовано для решения зад ра и др. Цель изобрете ние функциональных воз ройства за счет решени вояжера. Устройство со 1 напряжения и модели дая из которых содержи операционный усилитель мый делитель 3 напряже вый ключ 4, 2 ил..Ввфрид ельство СССР7/48, 1967.ьство СССР7/48, 1978.ЕНЕНИЯ ЭКСТРЕИ ЗАДАЧ СУДФРСТВЕННЫЙ КОМИТ ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГКНТ ССОф ПИСАНИЕ ИЗОввтсвснссвт свис Втовств(72) И.И.Бастриков и (53) 68 1.333 (088.8) (56) Авторское свиде У 231303, кл С 06 САвторское свидетел Р 750502, кл. С 06 С (54) УСТРОЙСТВО ДИ ИАЛЪНЦХ КОИБИНАТОРНЬ,80.17165 ится к вычислит быть испольачи коммивояжения - расширеюжностей устя задачи коммидержит источник дуг графа, кажт суммирующий2, регулируения и аналого. Изобретение относится к вычислительной технике и может быть использовано для решения задачи о коммивояжере и др.5Известно устройство для решениязадачи о коммивояжере по авт. св.СССР Р 231903, содержащее модели дуги источники изменения длин дуг. Иоделирование задач большого размера спомощью этого устройства ограниченомаксимально допустимой величиной напряжения между начальным и конечнымузлами устройства, необходимость регулирования источников изменения длин 15дуг в процессе поиска оптимальногорешения приводит к значительному. росту затрат времени на поиск оптимального решения, использование в моделяхдуг диодов снижает точность решенияиз-за неидеальности характеристикдиодовНаиболее близким. к предлагаемомуизобретению является устройство длярешения экстремальных комбинаторных 25задач по авт. св. СССР В 750502, Это. устройство содержит источник напряжения и модели дуг графа, каждая из которых содержит регулируемый делительнапряжения, суммирующий операционныйусилитель и аналоговый ключ, причемв каждой модели дуги, соединяющей -йузел графа с 3-м узлом графа, один извходов суммирующего операционногоусилителя через регулируемый делительнапряжения подключен к выходу источника напряжения, а инверсный выходсуммирующего операционного усилителячерез аналоговый ключ соединен с входами суммирующих операционных усилитепей моделей дуг, входящих в 1-йузел графа, и с входами суммирующихоперационных усилителей моделей дуг,выходящих из -го узла графа.Описанное устройство позволяет решать задачу о назначении. Невозмож 45ность обеспечения односвязности получаемого при решении графа ограничивает Функциональные возможности устройства при решении задачи о коммивояжере. 50Целью изобретения является расширение класса решаемых задач устройства,, Цель достигается тем, что в устройство для решения экстремальных 55комбинаторных задач, содержащее источник напряжения и модели дуг графа,каждая иэ которых содержит регулируе 171 б 548 4мый делитель напряжения, суммирующийоперационный усилитель и аналоговыйключ, причем в каждой модели дуги,соединяющей -й узел графа с 1-м узлом графа, один из входов суммирующего операционного усилителя черезрегулируемый делитель напряжения подключен к выходу источника напряжения,а инверсный выход суммирующего усилителя через аналоговый ключ соединенс входами суммирующих операционныхусилителей моделей дуг, входящих в1-й узел .графа, и с входами суммирующих операционных усилителей моделейдуг, выходящих из х-го узла графа,введены по идополнительных моделейдуг для всех дуг, кроме дуг, входящихв первый и выходящих из первого узлаграфа, причем инверсный выход суммирующего операционного усилителя Е-ймодели дуги, соединяющей -й узелграфа с 1-и узлом графа, через анало"говый ключ соединен с тремя входамисуммирующих операционных усилителейЕ-х моделей дуг графа, выходящих изх-го узла или входящих в 1-й узел, сдвумя входами суммирующих операционных усилителей 1 с-х модулей дуг графа,вхоцящих в -и узел или выходящих из1-го узла, с одним входом суммирующихоперационных усилителей остальных 1 с-хмоделей дуг графа, с двумя входамисуммирующих операционных усилителейЬ)-х моделей дуг графа, не входящих в д-й узел и выходящих из д-гоили из 1-го узла или входящих в 1-йузел, с одним входом суммирующих операционных усилителей остальных Ь)-хмоддлей дуг графа, не входящих в 1.-йузел, с двумя входами суммирующихоперационных усилителей +1)-х моделей дуг графа, не выходящих из 1-гоузла и входящих в х-й или в 1-й узелили выходящих из 3-го узла, с однимвходом суммирующих операционных усилителей остальных 5+1)-х моделей дугграфа, не выходящих из 3-го узла, содним входом суммирующих операционныхусилителей 1, 2 Ь), Ь+2) .п, и-х моделей дуг, входящих в 1-йили 1-й узлы графа и выходящих из1-го или 1-го узлов графа,Введенные дополнительные модели(дуг и их связи не обнаружены у известных технических решений и обеспечивают расширение функциональных возможностей заявляемого устройства, которое не совпадает со свойствами укззанннх источников и не равно их сумме. Это.позволяет сделать вывод о соответствии заявляемого решения критерию существенного отличия,На фиг,1 представлена модельд,-ик -5дуги графа, которая, как и в прототипе, содержит источник 1 напряжения,суммирующий операционный усилитель 2,делитель 3 напряжения и аналоговыйключ 4 1Инвертирующий выход операционногоусилителя 2 через аналоговый ключ 4соединен с входами соответствующихоперационных усилителей. Напряжениеснимаемое с регулируемого делителя 3напряжения пропорционально длине дук, фги ЙНа фиг.2 показан фрагмент графа,к,.содержащий дугу о;ф и дуги, моделикоторых не имеют непосредственныхксвязей с моделью дуги д;Устройство функционирует, исходяиз следующей постановки задачи о ком-,мивояжере. На полном графе без потерь, заданном узлами и матрицей расстояний между ними, отыскать гамильтонов цикл (цикл, проходящей черезвсе узлы графа по одному разу),.минимальной длины.30В устройстве после одновременногозамыкания аналоговых ключей образуйтся положительные обратные связи, чтообуславливает возникновение лавинообразного процесса опрокидывания в одноиз возможных устойчивых состояний.Каждое из устойчивых состояний устройства соответствует контуру обходавсех узлов графа при условии прохождения через каждый узел только одинраз и условии односвязанности полу 40ченного контура (соответствует гамильтонову циклу), т.е, удовлетворяет условиям задачи о коммивояжере.Направление развития лавинообраз, ного процесса опрокидывания определяется суммой напряжения, существующихна входах операционных. усилителей вмомент времени, предшествующий началу/ 50 образования лавинообразного процесса, и.соответствует оптимальному контуру обхода узлов графа, что следует из выражения (1), которое получено аналогично соответствующему выражению прототипа и определяет суммарное напряжение на входах суммирующих усилителей дуг, образующих возможный контур обхода узлов графа, т,е. кон- .Ь тур, удовлетворяющий условиям задачио коммивояжере1 КЯ ЗЛ= 70 - 7,.д, (1),1 5 11по г-му по расширен- по ш-муконтуруной матрице контуругде Б" О. - напряжения соответст квенно на выходе и вхо-де суммирующего операционного усилителя вмомент времени, предшествующий началу лавинообразного процес.са,д " - напряжение, снимаемое1со среднего вывода регулируемого делителянапряжения дуги,и - число узлов графа,сш - индекс разрешенногоконтура, т,е. контура,удовлетворяющего условиям задачи о коммивояжере.Устойчивое состояние устройствахарактеризуется тем, что на выходахи операционных усилителей дуг, образующих оптимальный контур, образуютсянапряжения +0 мдкс, определяемые амплитудной характеристикой усилителя, ина выходах остальных операционныхусилителей дуг образуются напряжения.-Б, с, причем для значений выходныхнапряжений в устойчивом состоянии выполняется условиег +11 максНмоксгде г - отношение числа дуг, входящихв разрешенный кентур, к числу дуг 1 невходящих в разрешенный контур. Дуги,операционные усилители которых в устойчивом состоянии имеют на выходахнапряжение +УМпС, определяют решение.задачи о коммивояжере.Анализ работы устройства аналоги-чен приведенному в прототипе,Благодаря введению новых связейграф решения, получаемого с помощьюзаявляемого устройства, удовлетворяет условию односвязности, что расширяет функциональные возможности устройства по сравнению с известными решениями,Формула изобретенияУстройство для решения экстремальных комбинаторных задач, содержащее источник напряжения и модели дуг графа, калдая из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющий -й узел графа с -м узлом граФа(1 = 1, 2 Н; 31, 2.М, где И - количество узлов в графе, М - индекс разрешенного контура в пути коммивояжера), один из входов суммирующего операционного усилителя через регулируемый делитель напряжения подключен к входу источника напряжения, а инверсный выход суммирующего операционного усилителя через 15 аналоговый ключ соединен с входами суммирующих операционных усилителей моделей дуг, входящих в 1-й узел графа, и с входами суммирующих операционных усилителей моделей дугу выхо О дящих из -го узла графа, о т л и - ч а ю щ е е с я. тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи коммивояжера, в него введены дополни тельные модели дуг, соединенные в соответствии с деревом возможных путей коммивояжера,.причем инверсный выход суммирующего операционного усилителя Е-й модели дуги, соединякщей х-й узел графа с 1-м узлом графа (к = 1, 2 Я), соединен через аналоговый ключ с тремя входами суммирующих операцион ных усилителей 1-х моделей дуг, соответствующих дугам, выходящим из -го или входящим в -й узел графа, с дву-, мя входами суммирующих операциоиных усилителей Е-х моделей дуг,соответствующихдугам,входящим в -й узелили выходящим из-го узла графа, с одним входом суммирующих операционнйх усилителей остальных Е-х моделей дуг, с двумя входами суммирующих операционных усилителей Ос)-х моделей дуг, соответствующих дугам, не входящим в х-й и выходящим из х-го или из 1-го или входящим в -й узел графа, с одним входом суммирующих операционных усилителей остальных Ь)-х моделей дуг, соответствущцих дугам, не входящим в -й узел, с двумя входами суммирующих операционных усилителей (к+1)-х моделей дуг, соответствующих дугам, не выходящим из -го узла и входящим в д-й или в -й или выходящим из х-го узла графа, с одним входом суммирующих операционных усилителей остальных (1+1)-х моделей дуг, соответствующих дугам, не выходящим из -го узла, с одним входом суммирующих операционных усилителей 1, 2. . . (1 с), Ь+2),И, Б-х моделей дуг, соответствунщих дугам, входящим в -й или -й узлы графа и выходящим из ьго или 1-го узлбв графа.1716548 в Составитель Ю.Бастридактор Т.Лошкарева Техред А,Кравчук гтор М. Самборс Заказ 615 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям пр 113035, Москва, 3-35, Раушская наб., д, 4/5 Г СССР. изводственно-издательский комбинат "Патент", г. Ужг Гагарина, 10