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

 

Изобретение относится к вычислительной технике и может быть использовано для решения задачи коммивояжера и др. Цель изобретения - расширение функциональных возможностей устройства за счет решения задачи коммивояжера . Устройство содержит источник 1 напряжения и модели дуг графа, каждая из которых содержит суммирующий операционный усилитель 2, регулируемый делитель 3 напряжения и аналоговый ключ 4. 2 ил.

„,SU„„1716548

СОЮЗ COBETCHHX

ОЮЮ

РЕСПУБЛИК (1)5 G 06 G 7/48

ПРИ ГКНТ CCCP

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

N RS TOPCNOMIV CBHP gtEIKCT3IV

ГОСУДФРСТВЕННЫЙ КОМИТЕТ

fO ИЗОБРЕТЕНИЯМ И 0ТНРЫТИЯМ (21) 4657797/24 (22) 02.03.89 (46). 29.02.92. Бюл. К - 8 (71) Одесский политехнический институт (72) И.И.Бастриков и Л.В.Фрид (53) 681.333 (088.8) (56) Авторское свидетельство СССР

9 231303, кл.. G 06 G 7/48, 1967, Авторское свидетельство СССР

Р 750502, кл. G 06 G 7/48,, 1978. (54) УСТРОЙСТВО ДИ ГЕНЕНИЯ ЭКСТРЕИАЛЪНЦХ КОИБИНАТОРНЫХ ЗАДАЧ

2 (57) Изобретение относится к вычислительной технике и может быть использовано для решения задачи коммивояжера и др. Цель изобретения — расширение функциональных возможностей устройства за счет решения задачи коммивояжера. Устройство содержит источник

1 напряжения и модели дуг графа, каждая из которых содержит суммирующий операционный усилитель 2, регулируемый делитель 3 напряжения и аналоговый ключ 4. 2 ил .. Изобретение относится к вычислительной технике и может быть использовано для решения задачи о коммивояжере и др.

Известно устройство для решения задачи о коммивояжере по авт. св.

СССР Р 231903, содержащее модели дуг и источники изменения длин дуг. Иоделирование задач большого размера с помощью этого устройства ограничено максимально допустимой величиной напряжения между начальным и конечным узлами устройства, необходимость регулирования источников изменения длин 1 дуг в процессе поиска оптимального решения приводит к значительному, росту затрат времени на поиск оптимального решения, использование в моделях дуг диодов снижает точность решения из-за неидеальности характеристик диодов °

Наиболее близким. к предлагаемому изобретению является устройство для решения экстремальных комбинаторных задач по авт ° св. СССР 9 750502. Это . устройство содержит источник напряжения и модели дуг графа, каждая из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющей i-й узел графа с j-м узлом графа, один из

Ф входов суммирующего операционного усилителя через регулируемый делитель напряжения подключен к выходу источника напряжения, а инверсный выход суммирующего операционного усилителя через аналоговый ключ соединен с входами суммирующих операционных усили-! тепей моделей дуг, входящих в j-й узел графа, и с входами суммирующих операционных усилителей моделей дуг, выходящих из i-ro узла графа.

Описанное устройство позволяет решать задачу о назначении. Невозмож45 ность обеспечения односвязности получаемого при решении графа ограничивает функциональные возможности устройства при решении задачи о коммивояжере. 50

Целью изобретения является расширение класса решаемых задач устройства. . Цель достигается тем, что в устройство для решения экстремальных 55 комбинаторных задач, содержащее источник напряжения и модели дуг графа, кажцая иэ которых содержит регулируе1716548 4 мый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющей i-й узел графа с j-м узлом графа, один из входов суммирующего операционного усилителя. через регулируемый делитель напряжения подключен к выходу источника напряжения, а инверсный выход суммирующего усилителя через аналоговый ключ соединен с входами суммирующих операционных усилителей моделей дуг, входящих в

j-й узел .графа, и с входами суммирующих операционных усилителей моделей дуг, выходящих из i-ro узла графа, введены по и-3 дополнительных моделей дуг для всех дуг, кроме дуг, входящих в первый и выходящих из первого узла графа, причем инверсный выход суммирующего операционного усилителя k-й модели дуги, соединяющей i-й узел графа с j-и узлом графа, через анало" говый ключ соединен с тремя входами суммирующих операционных усилителей

k-х моделей дуг графа, выходящих из

i-ro узла или входящих в j-й узел, с двумя входами суммирующих операционных усилителей k-x модулей дуг графа, вхоцящих в i-и узел или выходящих из

j-ro узла, с одним входом суммирующих операционных усилителей остальных k-x моделей дуг rpaAa, с двумя входами суммирующих операционных усилителей (k-1)-х моделей дуг графа, не входящих в i-й узел и выходящих из i-го или из 1-го узла или входящих в 1-й узел, с одним входом суммирующих операционных усилителей остальных (k-i)-х моделей дуг графа, не входящих a i.-й узел, с двумя входами суммирующих операционных усилителей (k+1)-х моделей дуг графа, не выходящих из j-ro узла и входящих в i-й или в j-й узел или выходящих из j-го узла, с одним входом суммирующих операционных усилителей остальных (k+1)-х моделей дуг графа, не выходящих из j-го узла, с одним входом суммирующих операционных усилителей 1,2,..., (k- 2), (k+2),..., п-1, и-х моделей дуг, входящих в i-й или j-й узлы графа и выходящих из

i-ro или j-ro узлов графа.

Введенные дополнительные модели( дуг и их связи не обнаружены у известных технических решений и обеспечивают расширение функциональных возможностей заявляемого устройства, которое не совпадает со свойствами укз1716548 занннх источников и не равно их сумме. Это.позволяет сделать вывод о соответствии заявляемого. решения критерию существенного отличия.

На фиг.1 представлена модель d -и к -5 дуги графа, которая, как и в прототи-. пе, содержит источник i напряжения, суммирующий операционный усилитель 2, делитель 3 напряжения и аналоговый ключ 4>

Инвертирующий выход операционного усилителя 2 через аналоговый ключ 4 соединен с входами соответствующих операционных усилителей. Напряжение . снимаемое с регулируемого делителя 3 напряжения пропорционально длине дук, ги d;>, На фиг. 2 показан фрагмент графа, к,. содержащий дугу d; и дуги, модели. которых не имеют непосредственных к связей с моделью дуги с1

Устройство функционирует, исходя из следующей постановки задачи о ком- . мивояжере. На полном графе без потерь, заданном узлами и матрицей расстояний между ними, отыскать гамильтонов цикл (цикл, проходящей через все узлы графа по одному разу),.минимальной длины.

В устройстве после одновременного замыкания аналоговых ключей образуйтся положительные обратные связи, что обуславливает возникновение лавинообразного процесса опрокидывания в одно из возможных устойчивых состояний.

Каждое из устойчивых состояний устройства соответс гвует контуру обхода всех узлов графа при условии прохождения через каждый узел только один

p&3 H условии орНосВН33ННосТН п, у . 40 ченного контура (соответствует гамильтонову циклу), т.е. удовлетворяет условиям задачи о коммивояжере.

Направление развития лавинообраз, ного процесса опрокидывания определя- 45 ется суммой напряжения, существующих на входах операционных. усилителей в момент времени, предшествующий началу

50 образования лавинообразного процесса, и соответствует оптимальному контуру обхода узлов графа, что следу- ет из выражения (1), которое получено аналогично соответствующему выражению прототипа и определяет суммарное напряжение на входах суммирующих усилителей дуг, образующих возможный контур обхода узлов графа, т.е. кон- . тур удовлетворяющий усл 1виям задачи о коммивояжере к ° лк

QU" = 7+U; — 7+d... (1) 5 по rl-му по расширен- по m-му контуру ной матрице контуру где U" U ° ° — напряжения соответст к к венно на выходе и вхо- де суммирующего операционного усилителя в момент времени, предшествующий началу лавинообразного процесФ. са, d;" — напряжение, снимаемое со среднего вывода ре гулируемого делителя напряжения дуги, и — число узлов графа, с

m — индекс разрешенного контура, т.е. контура, удовлетворяющего усло-.виям задачи о коммивояжере.

Устойчивое состояние устройства характеризуется тем, что на выходах и операционных усилителей дуг, образующих оптимальный контур, образуются напряжения +U ä„, определяемые амплитудной характеристикой усилителя, и на выходах остальных операционных усилителей дуг образуются напряжения.

"макс. причем для значений выходных напряжений в устойчивом состоянии выполняется условие з +"макс "макс где z — отношение числа дуг, входящих в разрешенный контур, к числу дуг не входящих в разрешенный контур. Дуги, операционные усилители которых в устойчивом состоянии имеют на выходах напряжение +Нмакс, определяют решение. задачи о коммивояжере.

Анализ работы устройства аналоги- чен приведенному в прототипе.

Благодаря введению новых связей граф решения, получаемого с помощью заявляемого устройства, удовлетворяет условию односвязности, что расширяет функциональные возможности устройства по сравнению с известными решениями.

Формула изобретения

Устройство для решения экстремальных комбинаторных задач, содержащее источник напряжения и модели дуг гра1716548 фа, кажная из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющий i-й узел графа с

j-м узлом rpaha(i = 1, 2,..., N;

1, 2,. ° ., M, где N — количество узлов в графе, M — индекс разрешенного контура в пути коммивояжера), один из входов суммирующего операционного усилителя-через регулируемый делитель напряжения подключен к входу источника напряжения, а инверсный выход суммирующего операционного усилителя через 15 аналоговый ключ соединен с входами суммирующих операционных усилителей моделей дуг, входящих в j-й узел графа, и с входами суммирующих операционных усилителей моделей дуг, Выхо дящих из i--ro узла графа, о т л и - ч а ю щ е е с я. тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи коммивояжера, в него введены дополни- 25 тельные модели дуг, соединенные в соответствии с деревом возможных путей коммивояжера,.причем инверсный выход суммирующего операционного усилителя

k-й модели дуги, соединякщей i-й узел графа с j-м узлом графа (k = 1, 2,..., N), соединен через аналоговый ключ с тремя входами суммирующих операционI ных усилителей k-х моделей дуг, соответствующих дугам, выходящим из i-го или входящим в j-й узел графа, с дву-, мя входами суммирующих операциоиных усилителей Е-х моделей дуг,соответствующихдугам,входящим в i-й узелили выходящим из j -ro узла графа, с одним входом суммирующих операционнйх усилителей остальных k-х моделей дуг, с двумя входами суммирующих операционных усилителей

{k-1)-х моделей дуг, соответствующих дугам, не входящим в i-й и выходящим из i-го или из j-ro или входящим в

j-й узел графа, с одним входом суммирующих операционных усилителей остальных (k-1)-х моделей дуг, соответствукицих дугам, не входящим в -й узел, с двумя входами суммирующих операционных усилителей (k+1)-х моделей дуг, соответствующих дугам, не выходящим из i-ro узла и входящим в

i-й или в j-й или выходящим из i-го узла графа, с одним входом суммирующих операционных усилителей остальных (k+1)-х моделей дуг, соответствующих дугам, не выходящим из j-го узла, с одним входом суммирующих операционных усилителей 1, 2,..., (k-2), (k+2), N-1, N-х моделей дуг, соответствукщих дугам, входящим в i-й или j-й узлы графа и выходящим из i«ro или

j-ro узлбв графа.

1716548

° ° ф °

° . °

Ф

4 . °

Составитель Ю. Бастриков

Редактор Т.Лошкарева Техред A,Kðäö.,ó„ Корректор N. Самборская с т

Заказ 615 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР.

113035, Москва, -Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101